ACM ICPC World Finals 2012 - Takeover Wars

ACM ICPC World Finals 2012 Problem L - 문제 링크

성질 1. 두 개의 원소를 합한 결과가 상대방의 가장 큰 원소보다 크지 않다면 의미가 없다.

성질 2. 상대방의 원소를 제거할거면 가장 큰 원소를 제거하는 수 밖에 없다.

성질 3. 성질 1에 의해서 두 개의 원소를 합할 때에, 가장 큰 두 원소를 합할 수 밖에 없다.

위의 성질들로 아래와 같은 코드를 작성하여 AC.

int f(int n, int m, long long A, long long B, int k) {

if (n == 0) return 0;

if (m == 0) return 1;

if (n <= 1 && A <= B) return 0;

if (n > 1) {

long long x = A;

long long y = a[k][n - 1];

if (x + y > B) {

int res = f(m, n - 1, B, x + y, !k);

if (!res) return 1;

}

}

if (A > B) {

int res = f(m - 1, n, a[!k][m - 1], A, !k);

if (!res) return 1;

}

return 0;

}

int main() {

int T = 1;

while (scanf("%d%d", &N, &M) == 2) {

long long x;

for (int i = 0; i < N; i++) scanf("%lld", &x), a[0][i + 1] = x;

for (int i = 0; i < M; i++) scanf("%lld", &x), a[1][i + 1] = x;

sort(a[0] + 1, a[0] + N + 1);

sort(a[1] + 1, a[1] + M + 1);

int res = f(N, M, a[0][N], a[1][M], 0);

printf("Case %d: %s\n", T++, res ? "Takeover Incorporated" : "Buyout Limited");

}

}