인수 전쟁
시간 제한1초메모리 제한128 MB
두 회사가 번갈아 자기 자회사를 합치거나 더 작은 상대 자회사를 흡수할 때, 최적으로 플레이하면 어느 회사가 이기는지 판정한다.
문제
두 대기업 Takeover Incorporated와 Buyout Limited가 인수 전쟁을 벌이고 있습니다. 각 기업은 여러 개의 자회사를 거느리며, 모든 자회사에는 정해진 시장 가치가 있습니다. 이 전쟁의 목표는 상대 기업을 시장에서 완전히 몰아내는 것입니다.
각 기업은 자신의 차례에 인수를 정확히 한 번 수행하며, 인수는 우호적 인수 또는 적대적 인수 중 하나입니다.
- 우호적 인수. 같은 기업에 속한 자회사 두 개를 하나로 합칩니다. 합쳐진 자회사의 시장 가치는 두 자회사 가치의 합이며, 두 자회사의 크기에는 아무런 제약이 없습니다.
- 적대적 인수. 한 기업의 자회사 가 상대 기업의 자회사 를 흡수합니다. 이는 의 시장 가치가 의 시장 가치보다 엄격히 클 때에만 가능합니다. 인수가 성사되면 는 시장에서 사라지고, 의 가치는 변하지 않습니다(의 자산을 흡수해 얻는 이득이 인수 비용과 정확히 상쇄되기 때문입니다).
시장 가치는, 전쟁이 어떻게 전개되더라도 서로 다른 기업에 속한 두 자회사의 시장 가치가 결코 같아지지 않도록 주어진다고 가정해도 됩니다.
두 기업은 번갈아 수를 두며 Takeover Incorporated가 먼저 시작합니다. 각 기업은 자신의 차례에 가능한 인수가 있으면 반드시 인수를 해야 하고, 가능한 인수가 하나도 없을 때에만(즉, 자회사가 하나뿐이고 그 자회사가 상대의 어떤 자회사도 흡수할 수 없을 때) 아무것도 하지 않습니다. 어떤 기업의 자회사가 모두 인수당하는 순간 그 기업은 전쟁에서 패배합니다.
두 기업이 모두 최적으로 행동할 때 어느 기업이 반드시 승리하는지 구하세요.
이해를 돕기 위해 첫 번째 예제를 살펴봅시다. Takeover Incorporated는 가치 의 자회사를, Buyout Limited는 가치 짜리 자회사 두 개를 가집니다. Takeover는 가치 인 자회사로 상대의 가치 자회사 하나를 흡수하고, 이후 가치 인 자회사 하나를 적대적 인수로 잃더라도 남은 가치 자회사마저 흡수해 승리합니다. 두 번째 예제에서 Takeover는 을, Buyout은 를 가집니다. Takeover에는 보다 큰 자회사가 없어 우호적 인수만 반복할 수밖에 없는데, Buyout은 두 자회사를 합쳐 가치 을 만들 수 있으므로 결국 Buyout이 승리합니다.
입력
입력은 여러 개의 테스트 케이스로 이루어지며 파일의 끝에서 종료됩니다. 각 테스트 케이스는 세 줄로 주어집니다.
- 첫째 줄에는 두 정수 과 이 주어집니다(). 각각 Takeover Incorporated와 Buyout Limited의 자회사 수입니다.
- 둘째 줄에는 Takeover Incorporated의 자회사 개의 시장 가치 가 주어집니다().
- 셋째 줄에는 Buyout Limited의 자회사 개의 시장 가치 가 주어집니다().
출력
각 테스트 케이스마다 한 줄에 Case k: X 형식으로 출력합니다. 여기서 는 부터 시작하는 테스트 케이스 번호이고, 는 두 기업이 최적으로 행동할 때 전쟁에서 승리하는 기업으로 Takeover Incorporated 또는 Buyout Limited 중 하나입니다.