GCJ 2011 Qual

올해도 어김없이 구글 코드잼이 열리고있는데..
며칠전에 qualifcation round 가 끝났다..
25점 이상이면 다음 라운드로 advance 한다..

한국사람 참가 결과는 아래에..
http://ahmed-aly.com/CodeJamTools/Country.jsp?GoogleID=975485&Country=South+Korea
http://www.go-hero.net/jam/11/regions/South%20Korea


올해 문제는 참 쇼킹했다.. 퀄 라운드 문제가 왜이리 어려워..!!!
어쨋든.. 대충 몇개 풀다보니 25점은 충분히 넘어서 그냥 끄고 잤다.. ㅎㅎ
마지막 문제는 읽어보지도 못했음..

일단 내가 짠 코드는 남겨놔야지..~


A. Bot Trust (small, large)

이 문제는 문제 해석이 문제 푸는것보다 오래걸리는 문제이다.. -_-;;
일단 문제 해석만 되면 그냥 simulation..

  1 #include <stdio.h>
  2 #include <string.h>
  3 #define max(x, y) ((x) > (y) ? (x) : (y))
  4 #define min(x, y) ((x) > (y) ? (y) : (x))
  5 typedef struct _d {
  6     int no;
  7     char bot[4];
  8 } DATA;
  9 DATA data[110];
 10 int n;
 11 int main()
 12 {
 13     int tc, cn;
 14     int i, j, k;
 15     int po1, po2;
 16     int ti1, ti2;
 17     int temp;
 18     scanf("%d", &tc);
 19     for (cn = 1; cn <= tc; cn++) {
 20         scanf("%d", &n);
 21         for (i = 0; i < n; i++) {
 22             scanf("%s%d", data[i].bot, &data[i].no);
 23         }
 24         ti1 = ti2 = 0;
 25         po1 = po2 = 1;
 26         for (i = 0; i < n; i++) {
 27             if (data[i].bot[0] == 'O') {
 28                 temp = ti1 + abs(po1-data[i].no);
 29                 temp = max(temp, ti2);
 30                 ti1 = temp + 1;
 31                 po1 = data[i].no;
 32             }
 33             else {
 34                 temp = ti2 + abs(po2-data[i].no);
 35                 temp = max(temp, ti1);
 36                 ti2 = temp + 1;
 37                 po2 = data[i].no;
 38             }
 39         }
 40         printf("Case #%d: %d\n", cn, max(ti1, ti2));
 41     }
 42     return 0;
 43 }

B. Magica (small, large)

이문제 역시 문제 해석이 문제 코딩보다 오래걸리는 문제..
역시 simulation 했다..

  1 #include <stdio.h>
  2 #include <string.h>
  3 char crule[100][10];
  4 char drule[100][10];
  5 char str[1000];
  6 int c, d, n;
  7 char buf[1000];
  8 int len;
  9 int main()
 10 {
 11     int tc, cn;
 12     int i, j, k;
 13     int fl;
 14     scanf("%d", &tc);
 15     for (cn = 1; cn <= tc; cn++) {
 16         scanf("%d", &c);
 17         for (i = 0; i < c; i++) {
 18             scanf("%s", crule[i]);
 19         }
 20         scanf("%d", &d);
 21         for (i = 0; i < d; i++) {
 22             scanf("%s", drule[i]);
 23         }
 24         scanf("%d", &n);
 25         scanf("%s", str);
 26         len = 0;
 27         for (i = 0; i < n; i++) {
 28             buf[len++] = str[i];
 29             buf[len] = 0;
 30             if (len < 2) {
 31                 continue;
 32             }
 33             fl = 0;
 34             for (j = 0; j < c; j++) {
 35                 if ((buf[len-2] == crule[j][0] && buf[len-1] == crule[j][1]) ||
 36                     (buf[len-2] == crule[j][1] && buf[len-1] == crule[j][0])) {
 37                     buf[len-2] = crule[j][2];
 38                     buf[len-1] = 0;
 39                     len--;
 40                     goto X;
 41                 }
 42             }
 43             for (j = 0; j < d; j++) {
 44                 for (k = 0; k < len-1; k++) {
 45                     if (buf[k] == drule[j][0] && buf[len-1] == drule[j][1]) {
 46                         len = 0;
 47                         goto X;
 48                     }
 49                     if (buf[k] == drule[j][1] && buf[len-1] == drule[j][0]) {
 50                         len = 0;
 51                         goto X;
 52                     }
 53                 }
 54             }
 55 X: ;
 56         }
 57
 58         printf("Case #%d: [", cn);
 59         for (i = 0; i < len; i++) {
 60             if (i == 0)
 61                 printf("%c", buf[i]);
 62             else
 63                 printf(", %c", buf[i]);
 64         }
 65         printf("]\n");
 66     }
 67     return 0;
 68 }

C. Candy Spliting (small)

이 문제는 small input 에 대해서만 풀었다..
모든 partition 가능한 경우를 다 구해서 확인해 보았다.. O(2^n)

  1 #include <stdio.h>
  2 #include <string.h>
  3 int n;
  4 int num[1010];
  5 int main()
  6 {
  7     int tc, cn;
  8     int i, j, k;
  9     int max1, sum1, sum2;
 10     int val1, val2;
 11     scanf("%d", &tc);
 12     for (cn = 1; cn <= tc; cn++) {
 13         scanf("%d", &n);
 14         for (i = 0; i < n; i++) {
 15             scanf("%d", &num[i]);
 16         }
 17         max1 = -1;
 18         for (i = 0; i < (1 << n); i++) {
 19             sum1 = sum2 = 0;
 20             val1 = val2 = 0;
 21             for (j = 0; j < n; j++) {
 22                 if (i & (1 << j)) {
 23                     sum1 = sum1 + num[j];
 24                     val1 = val1 ^ num[j];
 25                 }
 26                 else {
 27                     sum2 = sum2 + num[j];
 28                     val2 = val2 ^ num[j];
 29                 }
 30             }
 31             if (val1 == val2 && sum1 != 0 && sum2 != 0) {
 32                 if (sum1 > max1) {
 33                     max1 = sum1;
 34                 }
 35             }
 36         }
 37         printf("Case #%d: ", cn);
 38         if (max1 == -1)
 39             printf("NO\n");
 40         else
 41             printf("%d\n", max1);
 42     }
 43     return 0;
 44 }

large input 에 대한 해법을 보고 어이 없었음.. -_-;;
일단 모든 수를 다 bitwise xor 해서 0이 아니면 답이 없다는 건 알 수 있는데..
그렇지 않은경우 항상 답이 있고, 모든 조합을 다 시도하더라도 가능하다..
뭔말이냐하면 가장 작은 쪼가리를 상대방한테 넘겨주면 된다능.. -_-;;;;


이렇게 해서 1라운드 진출한듯한데.. (왜 email 않오지..?)
작년에는 2라운드까지는 진출했는데.. 올해는 좀 힘들것 같다..
3차에 걸쳐 열리는 1라운드는 나는 1번밖에 참가 못할것 같다.. 흠..

뭔가.. 갈수록 어려워지는거 같어..


http://code.google.com/codejam