Google Code Jam Korea 2012 본선 라운드 - 역대 최고성적?

GCJ Korea 본선 라운드..
오늘 학교에서 후배들이랑 오프라인으로 모여서 같이 참가했다..~

결국 15등으로 마감~
아마도 내가 지금까지 GCJ 참가한것중에 가장 좋은 성적이 아닐까 생각한다..
12등 안에 들면 구글 사무실에서 오프라인으로 결승전 하는데.. 간발의 차이로 아쉽게 됐다.. ㅠㅠ

GCJ Korea 대회는 처음 열리는 거라서 그런지 진행상에 문제가 많았다..
처음 등록때부터 오류로인해 재등록 하는 일도 있었고..
본선 진출하고도 확정 이메일을 본선라운드 바로전날 알려주는등..
더더욱 가장 큰 문제는 문제 description 및 test case 에 오류가 있는 문제가 몇개 있었다.. <--- 아주 치명적인 문제..
뭐.. 내년부터는 좀 더 나아지겠지..

점수판 :  http://code.google.com/codejam/contest/1378488/scoreboard 

내 등수가 맨 첫페이지에 보인다.. 대박!!! ㅎㅎ 
근데.. 50등 안에 들었으니깐 티셔츠 주겠지 설마????


A - 생존자 (small)

어떤 순서로 식량을 먹어야하는지.. 모든 permutation 에 대해서 다 시도해보았다..
아주 무식한 방법.. n 이 10 이하이기때문에 가능..

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

typedef struct _d {

int p, s;

} DATA;

DATA data[100000];

int n;

int main()

{

int tc, cn;

int i, j, k;

int perm[1000];

int cur, max1;

DATA d1;

scanf("%d", &tc);

for (cn = 1; cn <= tc;cn++) {

scanf("%d", &n);

for (i = 0; i < n; i++) {

scanf("%d%d", &data[i].p, &data[i].s);

}

for (i = 0; i < n; i++) {

perm[i] = i;

}

max1 = 0;

do {

cur = 0;

for (i = 0; i < n; i++) {

d1= data[perm[i]];

//printf("d1.p = %d, d1.s = %d\n", d1.p, d1.s);

if (d1.p < cur) {

continue;

}

cur += d1.s;

}

if (i == n) {

if (cur > max1) {

max1 = cur;

}

}

} while (next_permutation(perm, perm+n));

printf("Case #%d: %d\n", cn, max1);

}

return 0;

}

A - 생존자 (large)

dp[i][j] = i 번째 식량까지 고려서해 j 일까지 살아남아서 하나의 식량을 다 먹은순간 (?)

뭔가 말이 좀 이상하지만.. 문제 자체도 좀 이상하다.. ㅋㅋ
어쨋든 DP 로 풀었음..

#include <stdio.h>

#include <string.h>

typedef struct _d {

int p, s;

} DATA;

DATA data[1010];

int n;

int dp[1010][110001];

int comp(const void* x, const void* y)

{

DATA* a = (DATA*)x;

DATA* b = (DATA*)y;

/*

if (a->p != b->p)

return a->p - b->p;

return a->s - b->s;

*/

return (a->p+a->s) - (b->p+b->s);

}

int main()

{

int tc, cn;

int i, j, k;

int cur, max1;

int limit;

DATA d1;

scanf("%d", &tc);

for (cn = 1; cn <= tc;cn++) {

scanf("%d", &n);

for (i = 1; i <= n; i++) {

scanf("%d%d", &data[i].p, &data[i].s);

}

qsort(data+1, n, sizeof(DATA), comp);

memset(dp, 0, sizeof(dp));

dp[0][0] = 1;

max1 = 0;

limit = data[n].s + data[n].p;

for (i = 1; i <= n; i++) {

for (j = 0; j <= limit; j++) {

dp[i][j] = dp[i-1][j];

if (j-data[i].s >= 0 && j-data[i].s <= data[i].p) {

if (dp[i-1][j-data[i].s]) {

//printf("(%d,%d) = 1\n", i, j);

dp[i][j] = 1;

}

}

}

}

max1 = 0;

for (i = 0; i <= limit; i++) {

if (dp[n][i])

max1 = i;

}

printf("Case #%d: %d\n", cn, max1);

}

return 0;

}

D - 한강

이거는 문제 description 은 난해하지만.. 별거 없다..
그냥 1~1000000 까지 수의 약수 개수 구하고.. 그중에 가장 작은 약수 구하면 된다..

#include <stdio.h>

#include <string.h>

#include <stdio.h>

#include <string.h>

#define MAXN 1000001

char is_prime[MAXN];

int prime[MAXN];

int prime_cnt;

char check[MAXN];

void sieve()

{

    int i, j;

    memset(is_prime, -1, sizeof(is_prime));

    prime_cnt = 0;

    is_prime[0] = is_prime[1] = 0;

    for (i = 2; i < MAXN; i++) {

        if (is_prime[i]) {

            for (j = 2; i * j <= MAXN; j++) {

                is_prime[i*j] = 0;

            }

            prime[prime_cnt++] = i;

        }

    }

}

int n_divisor(int n)

{

    int i, cnt, sum;

    sum = 1;

    for (i = 0; i < prime_cnt && prime[i]*prime[i] <= n; i++) {

        if (n % prime[i] == 0) {

            cnt = 0;

            while (n % prime[i] == 0) {

                cnt++;

                n /= prime[i];

            }

            sum *= cnt+1;

        }

    }

    if (n != 1)

        sum *= 2;

    return sum;

}

int get_sm(int n)

{

int i;

for (i = 0; i < prime_cnt && prime[i]*prime[i] <= n; i++) {

if (n % prime[i] == 0) {

return prime[i];

}

}

return n;

}

int main()

{

int tc, cn;

int n, m;

int i, j, k;

int c1, c2;

int cnt;

sieve();

scanf("%d", &tc);

for (cn = 1; cn <= tc; cn++) {

scanf("%d%d", &n, &m);

c1 = n_divisor(n);

memset(check, 0, sizeof(check));

for (i = 2; i <= n; i++) {

if (is_prime[i]) {

check[i] = 0;

continue;

}

if (i <= m) {

check[i] = 0;

continue;

}

if (get_sm(i) >= m) {

check[i] = 1;

}

else {

check[i] = 0;

}

}

cnt = 0;

for (i = 2; i < n; i++) {

if (check[i]) {

c2 = n_divisor(i);

if (c1 == c2) {

cnt++;

}

}

}

printf("Case #%d: %d\n", cn, cnt);

}

return 0;

}