Goodbye GCJ 2011

얼마전에 열렸던 GCJ 2011 Round 1B, 1C 를 차례로 참가했지만
둘다 1000 등 안에 못들어서 결국 2라운드 진출에 실패했다..

1B 는 제주도에서 돌아오자마자 피곤한 상태에서 문제 보다가 그냥 쓰러졌고.. (1793등)
1C 는 문제 해석과 코딩에서 말리는바람에.. 너무 늦게 풀어서 아쉽게 탈락했다.. (1057등)

아.. 문제 드럽게 어렵네.. OTL
올해는 뭔가 알고리즘을 잘 떠올려서 깔끔하게 푼 문제가 하나도 없다..
좀 아쉽지만 내년을 기약해야겠다..


Round 1B

A. RPI (small, large)

그냥 문제에서 시키는데로 했다.. 문제 해석이 복잡한만큼 코드도 복잡하다.. ㅠ_ㅠ;

  1 #include <stdio.h>
  2 #include <string.h>
  3 char map[110][110];
  4 int n;
  5 double wp[110], owp[110], oowp[110];
  6 int main()
  7 {
  8     int tc, cn;
  9     int i, j, k;
 10     int g, w, l, cnt;
 11     double wpsum;
 12     scanf("%d", &tc);
 13     for (cn = 1; cn <= tc; cn++) {
 14         scanf("%d", &n);
 15         for (i = 0; i < n; i++) {
 16             scanf("%s", map[i]);
 17         }
 18         for (i = 0; i < n; i++) {
 19             wp[i] = owp[i] = oowp[i] = 0;
 20         }
 21
 22         for (i = 0; i < n; i++) {
 23             g = 0;
 24             w = 0;
 25             l = 0;
 26             for (j = 0; j < n; j++) {
 27                 if (map[i][j] == '.')
 28                     continue;
 29                 else if (map[i][j] == '1') {
 30                     g++;
 31                     w++;
 32                 }
 33                 else {
 34                     g++;
 35                     l++;
 36                 }
 37             }
 38             wp[i] = (double)w / (double)g;
 39
 40             /* throw out i */
 41             cnt = 0;
 42             wpsum = 0.0;
 43             for (j = 0; j < n; j++) {
 44                 if (j == i)
 45                     continue;
 46                 if (map[j][i] == '.')
 47                     continue;
 48                 g = 0;
 49                 w = 0;
 50                 l = 0;
 51                 for (k = 0; k < n; k++) {
 52                     if (i == k)
 53                         continue;
 54                     if (map[j][k] == '.')
 55                         continue;
 56                     g++;
 57                     if (map[j][k] == '1') {
 58                         w++;
 59                     }
 60                     else {
 61                         l++;
 62                     }
 63                 }
 64                 if (g) {
 65                     cnt++;
 66                     wpsum += (double)w / (double)g;
 67                 }
 68             }
 69             owp[i] = wpsum / (double)cnt;
 70         }
 71
 72         for (i = 0; i < n; i++) {
 73             cnt = 0;
 74             for (j = 0; j < n; j++) {
 75                 if (map[i][j] != '.') {
 76                     oowp[i] += owp[j];
 77                     cnt++;
 78                 }
 79             }
 80             oowp[i] /= (double)cnt;
 81         }
 82         printf("Case #%d:\n", cn);
 83         for (i = 0; i < n; i++) {
 84             printf("%.10lf\n", 0.25*wp[i] + 0.50*owp[i] + 0.25*oowp[i]);
 85         }
 86     }
 87     return 0;
 88 }

Round 1C

A. Square Tiles (small, large)

Greedy 전략으로 풀었다.. '#' 을 만날경우 가 옆, 아래, 대각선아래는 무조건 '#' 이어야 한다..
정말 greedy 로 되나.. 한참 고민했음..

  1 #include <stdio.h>
  2 #include <string.h>
  3 int n, m;
  4 char map[110][110];
  5 int main()
  6 {
  7     int tc, cn;
  8     int i, j, k;
  9     scanf("%d", &tc);
 10     for (cn = 1; cn <= tc; cn++) {
 11         scanf("%d%d", &n, &m);
 12         memset(map, 0, sizeof(map));
 13         for (i = 0; i < n; i++) {
 14             scanf("%s", map[i]);
 15         }
 16         printf("Case #%d:\n", cn);
 17         for (i = 0; i < n; i++) {
 18             for (j = 0; j < m; j++) {
 19                 if (map[i][j] == '#') {
 20                     if (map[i][j+1] == '#' && map[i+1][j] == '#' && map[i+1][j+1] == '#') {
 21                         map[i][j] = '/';
 22                         map[i][j+1] = '\\';
 23                         map[i+1][j] = '\\';
 24                         map[i+1][j+1] = '/';
 25                     }
 26                     else {
 27                         goto X;
 28                     }
 29                 }
 30             }
 31         }
 32         for (i = 0; i < n; i++) {
 33             for (j = 0; j < m; j++) {
 34                 printf("%c", map[i][j]);
 35             }
 36             printf("\n");
 37         }
 38         continue;
 39 X:
 40         printf("Impossible\n");
 41     }
 42     return 0;
 43 }

B. Space Emergency (small)

문제 해석이 열라 복잡함.. 해석하는데 한참 걸렸다.. 코딩까지 말리면서 좌절한 문제..
이문제만 좀 빨리풀었으면 2라운드 진출이었는데.. ㅠ_ㅠ;;

small input 에 대해서만 풀었는데.. l 이 최대 3이므로 case by case 로 풀었다..
boost 를 각 path 마다 다 시도해보고 그중 최소값..!

  1 #include <stdio.h>
  2 #include <string.h>
  3 int l, n, c;
  4 long long t;
  5 long long num[1010];
  6 long long aa[1010];
  7 long long cum[1010];
  8 int main()
  9 {
 10     int tc, cn;
 11     int i, j, k;
 12     int p1, p2;
 13     long long left;
 14     long long sum, min1;
 15     scanf("%d", &tc);
 16     for (cn = 1; cn <= tc; cn++) {
 17         scanf("%d%I64d%d%d", &l, &t, &n, &c);
 18         for (i = 0; i < c; i++) {
 19             scanf("%I64d", &aa[i]);
 20         }
 21         for (i = 0, j = 0; i < n; i++, j++) {
 22             num[i] = aa[i%c];
 23         }
 24         sum = 0;
 25         p1 = p2 = -1;
 26         for (i = 0; i < n; i++) {
 27             if (sum + num[i]*2 == t) {
 28                 p1 = i+1;
 29                 p2 = i+1;
 30                 break;
 31             }
 32             else if (sum + num[i]*2 > t) {
 33                 p1 = i;
 34                 p2 = i+1;
 35                 break;
 36             }
 37             else {
 38                 sum += num[i]*2;
 39             }
 40         }
 41         if (p1 == n)
 42             p1 = -1;
 43         if (p2 == n)
 44             p2 = -1;
 45         if (p1 >= 0 && p2 == -1)
 46             l = 1;
 47         if (p1 == -1 && p2 == -1)
 48             l = 0;
 49         sum = 0;
 50         for (i = 0; i < n; i++) {
 51             sum += num[i];
 52         }
 53         cum[0] = num[0];
 54         for (i = 1; i < n; i++) {
 55             cum[i] = cum[i-1] + num[i];
 56         }
 57
 58         if (l == 0) {
 59             printf("Case #%d: %I64d\n", cn, sum*2);
 60         }
 61         else if (l == 1) {
 62             min1 = cum[n-1] * 2;
 63             for (i = p1; i < n; i++) {
 64                 sum = 0;
 65                 for (j = 0; j < i; j++) {
 66                     sum += num[j] * 2;
 67                 }
 68                 left = t - sum;
 69                 for (j = i+1; j < n; j++) {
 70                     sum += num[j] * 2;
 71                 }
 72
 73                 if (p2 != -1 && i >= p2) {
 74                     sum += num[i];
 75                 }
 76                 else {
 77                     sum += left;
 78                     left = num[i]*2 - left;
 79                     sum += left / 2;
 80                 }
 81                 if (sum < min1) {
 82                     min1 = sum;
 83                 }
 84             }
 85             printf("Case #%d: %I64d\n", cn, min1);
 86         }
 87         else if (l == 2) {
 88             min1 = cum[n-1] * 2;
 89             for (i = p1; i < n; i++) {
 90                 for (j = i+1; j < n; j++) {
 91                     sum = 0;
 92                     for (k = 0; k < i; k++) {
 93                         sum += num[k]*2;
 94                     }
 95                     left = t - sum;
 96                     for (k = i+1; k < n; k++) {
 97                         if (k == j)
 98                             sum += num[k];
 99                         else
100                             sum += num[k]*2;
101                     }
102                     if (i >= p2) {
103                         sum += num[i];
104                     }
105                     else {
106                         sum += left;
107                         left = num[i]*2 - left;
108                         sum += left / 2;
109                     }
110                     if (min1 > sum) {
111                         min1 = sum;
112                     }
113                 }
114             }
115             printf("Case #%d: %I64d\n", cn, min1);
116         }
117     }
118     return 0;
119 }

C. Perfect Harmony (small)

모든 범위안의 수에 대해서 다 시도.. large 를 풀기 위해선 number theory 에 대한 개념이 좀 필요할까..?

  1 #include <stdio.h>
  2 #include <string.h>
  3 int n;
  4 int l, h;
  5 int num[10010];
  6 int main()
  7 {
  8     int tc, cn;
  9     int i, j, k;
 10     scanf("%d", &tc);
 11     for (cn = 1; cn <= tc; cn++) {
 12         scanf("%d%d%d", &n, &l, &h);
 13         for (i = 0; i < n; i++) {
 14             scanf("%d", &num[i]);
 15         }
 16         for (i = l; i <= h; i++) {
 17             for (j = 0; j < n; j++) {
 18                 if (num[j] % i != 0 && i % num[j] != 0)
 19                     break;
 20             }
 21             if (j == n) {
 22                 break;
 23             }
 24         }
 25         if (i == h+1) {
 26             printf("Case #%d: NO\n", cn);
 27         }
 28         else {
 29             printf("Case #%d: %d\n", cn, i);
 30         }
 31     }
 32     return 0;
 33 }