크리스마스를 맞아 바이텍은 검은 추 n개, 회색 추 n개, 매우 가벼운 저울 n개로 이루어진 장난감 세트를 받았습니다.
새 장난감을 받고 기뻐 바이텍은 재빠르게 장난감 세트로 조형물을 만들었습니다. 우선 바닥에 저울 하나를 놓고 검은 추 하나를 저울 한쪽에 놓고 반대쪽에는 다른 저울 하나를 올린 후, 다음 저울에도 한쪽에는 검은 추를 놓고 반대쪽에는 다음 저울을 놓는 과정을 반복합니다. 마지막 n번째 저울에는 한쪽에 마지막 검은 추를 놓고 반대쪽은 빈 채로 둡니다.
바이텍은 퍼즐을 하나 고안했습니다. 마지막 빈 공간에는 아무 회색 추나 올릴 수 있습니다. 이후 어떤 저울이 평형을 이룬다면, 그 저울과 위에 있는 모든 것은 가능한 경우 같은 질량의 회색 추 하나로 바꿀 수 있습니다. 저울의 질량은 무시할 수 있을 정도로 작다고 가정합시다.
바이텍은 조형물을 친구인 비토아시에게 편하게 보낼 수 있도록 가능한 적은 추를 남기고 싶어합니다. 바이텍이 조형물에 남길 수 있는 추의 최소 개수를 찾읍시다.
입력
표준 입력 첫 줄에 저울의 수를 나타내는 하나의 정수 n이 주어집니다 (1 <= n <= 1 000 000). 두 번째 줄에는 하나의 공백으로 구분된 n개의 정수 ci가 주어지는데 (1 <= ci <= 1018), 순서대로 저울에 올라가 있는 검은 추의 질량을 나타냅니다. 셋째 줄에는 하나의 공백으로 구분된 n개의 정수 sj가 주어지는데 (1 <= sj <= 1018), 회색 추의 질량을 나타냅니다.
ez_code 2년 전 3
문제
크리스마스를 맞아 바이텍은 검은 추 n개, 회색 추 n개, 매우 가벼운 저울 n개로 이루어진 장난감 세트를 받았습니다.
새 장난감을 받고 기뻐 바이텍은 재빠르게 장난감 세트로 조형물을 만들었습니다. 우선 바닥에 저울 하나를 놓고 검은 추 하나를 저울 한쪽에 놓고 반대쪽에는 다른 저울 하나를 올린 후, 다음 저울에도 한쪽에는 검은 추를 놓고 반대쪽에는 다음 저울을 놓는 과정을 반복합니다. 마지막 n번째 저울에는 한쪽에 마지막 검은 추를 놓고 반대쪽은 빈 채로 둡니다.
바이텍은 퍼즐을 하나 고안했습니다. 마지막 빈 공간에는 아무 회색 추나 올릴 수 있습니다. 이후 어떤 저울이 평형을 이룬다면, 그 저울과 위에 있는 모든 것은 가능한 경우 같은 질량의 회색 추 하나로 바꿀 수 있습니다. 저울의 질량은 무시할 수 있을 정도로 작다고 가정합시다.
바이텍은 조형물을 친구인 비토아시에게 편하게 보낼 수 있도록 가능한 적은 추를 남기고 싶어합니다. 바이텍이 조형물에 남길 수 있는 추의 최소 개수를 찾읍시다.
입력
표준 입력 첫 줄에 저울의 수를 나타내는 하나의 정수 n이 주어집니다 (1 <= n <= 1 000 000). 두 번째 줄에는 하나의 공백으로 구분된 n개의 정수 ci가 주어지는데 (1 <= ci <= 1018), 순서대로 저울에 올라가 있는 검은 추의 질량을 나타냅니다. 셋째 줄에는 하나의 공백으로 구분된 n개의 정수 sj가 주어지는데 (1 <= sj <= 1018), 회색 추의 질량을 나타냅니다.
출력
표준 출력은 정확히 하나의 정수를 출력해야 합니다 - 구조물에 남는 추의 수입니다.