인수 전쟁

시간 제한1초메모리 제한128 MB

요약
두 회사가 번갈아 자기 자회사를 합치거나 더 작은 상대 자회사를 흡수할 때, 최적으로 플레이하면 어느 회사가 이기는지 판정한다.
난이도

어려움10점 중 8점

유형
그리디, 정렬, 게임 이론, 구현
정답자
아직 제출이 없습니다

문제

두 대기업 Takeover Incorporated와 Buyout Limited가 인수 전쟁을 벌이고 있습니다. 각 기업은 여러 개의 자회사를 거느리며, 모든 자회사에는 정해진 시장 가치가 있습니다. 이 전쟁의 목표는 상대 기업을 시장에서 완전히 몰아내는 것입니다.

각 기업은 자신의 차례에 인수를 정확히 한 번 수행하며, 인수는 우호적 인수 또는 적대적 인수 중 하나입니다.

  • 우호적 인수. 같은 기업에 속한 자회사 두 개를 하나로 합칩니다. 합쳐진 자회사의 시장 가치는 두 자회사 가치의 합이며, 두 자회사의 크기에는 아무런 제약이 없습니다.
  • 적대적 인수. 한 기업의 자회사 AA가 상대 기업의 자회사 BB를 흡수합니다. 이는 AA의 시장 가치가 BB의 시장 가치보다 엄격히 클 때에만 가능합니다. 인수가 성사되면 BB는 시장에서 사라지고, AA의 가치는 변하지 않습니다(BB의 자산을 흡수해 얻는 이득이 인수 비용과 정확히 상쇄되기 때문입니다).

시장 가치는, 전쟁이 어떻게 전개되더라도 서로 다른 기업에 속한 두 자회사의 시장 가치가 결코 같아지지 않도록 주어진다고 가정해도 됩니다.

두 기업은 번갈아 수를 두며 Takeover Incorporated가 먼저 시작합니다. 각 기업은 자신의 차례에 가능한 인수가 있으면 반드시 인수를 해야 하고, 가능한 인수가 하나도 없을 때에만(즉, 자회사가 하나뿐이고 그 자회사가 상대의 어떤 자회사도 흡수할 수 없을 때) 아무것도 하지 않습니다. 어떤 기업의 자회사가 모두 인수당하는 순간 그 기업은 전쟁에서 패배합니다.

두 기업이 모두 최적으로 행동할 때 어느 기업이 반드시 승리하는지 구하세요.

이해를 돕기 위해 첫 번째 예제를 살펴봅시다. Takeover Incorporated는 가치 7,1,17, 1, 1의 자회사를, Buyout Limited는 가치 55짜리 자회사 두 개를 가집니다. Takeover는 가치 77인 자회사로 상대의 가치 55 자회사 하나를 흡수하고, 이후 가치 11인 자회사 하나를 적대적 인수로 잃더라도 남은 가치 55 자회사마저 흡수해 승리합니다. 두 번째 예제에서 Takeover는 3,3,3,33, 3, 3, 3을, Buyout은 5,55, 5를 가집니다. Takeover에는 55보다 큰 자회사가 없어 우호적 인수만 반복할 수밖에 없는데, Buyout은 두 자회사를 합쳐 가치 1010을 만들 수 있으므로 결국 Buyout이 승리합니다.

입력

입력은 여러 개의 테스트 케이스로 이루어지며 파일의 끝에서 종료됩니다. 각 테스트 케이스는 세 줄로 주어집니다.

  • 첫째 줄에는 두 정수 NN과 MM이 주어집니다(1≤N,M≤1051 \le N, M \le 10^5). 각각 Takeover Incorporated와 Buyout Limited의 자회사 수입니다.
  • 둘째 줄에는 Takeover Incorporated의 자회사 NN개의 시장 가치 aia_i가 주어집니다(1≤ai≤10121 \le a_i \le 10^{12}).
  • 셋째 줄에는 Buyout Limited의 자회사 MM개의 시장 가치 bjb_j가 주어집니다(1≤bj≤10121 \le b_j \le 10^{12}).

출력

각 테스트 케이스마다 한 줄에 Case k: X 형식으로 출력합니다. 여기서 kk는 11부터 시작하는 테스트 케이스 번호이고, XX는 두 기업이 최적으로 행동할 때 전쟁에서 승리하는 기업으로 Takeover Incorporated 또는 Buyout Limited 중 하나입니다.

예제1

  1. 예제 1

    입력
    3 2
    7 1 1
    5 5
    4 2
    3 3 3 3
    5 5
    
    예상 출력
    Case 1: Takeover Incorporated
    Case 2: Buyout Limited