Goodbye GCJ 2011
Problem Solving/GCJ logs 2011. 5. 27. 00:10
얼마전에 열렸던 GCJ 2011 Round 1B, 1C 를 차례로 참가했지만
둘다 1000 등 안에 못들어서 결국 2라운드 진출에 실패했다..
1B 는 제주도에서 돌아오자마자 피곤한 상태에서 문제 보다가 그냥 쓰러졌고.. (1793등)
1C 는 문제 해석과 코딩에서 말리는바람에.. 너무 늦게 풀어서 아쉽게 탈락했다.. (1057등)
아.. 문제 드럽게 어렵네.. OTL
올해는 뭔가 알고리즘을 잘 떠올려서 깔끔하게 푼 문제가 하나도 없다..
좀 아쉽지만 내년을 기약해야겠다..
Round 1B
A. RPI (small, large)
그냥 문제에서 시키는데로 했다.. 문제 해석이 복잡한만큼 코드도 복잡하다.. ㅠ_ㅠ;
Round 1C
A. Square Tiles (small, large)
Greedy 전략으로 풀었다.. '#' 을 만날경우 가 옆, 아래, 대각선아래는 무조건 '#' 이어야 한다..
정말 greedy 로 되나.. 한참 고민했음..
B. Space Emergency (small)
문제 해석이 열라 복잡함.. 해석하는데 한참 걸렸다.. 코딩까지 말리면서 좌절한 문제..
이문제만 좀 빨리풀었으면 2라운드 진출이었는데.. ㅠ_ㅠ;;
small input 에 대해서만 풀었는데.. l 이 최대 3이므로 case by case 로 풀었다..
boost 를 각 path 마다 다 시도해보고 그중 최소값..!
C. Perfect Harmony (small)
모든 범위안의 수에 대해서 다 시도.. large 를 풀기 위해선 number theory 에 대한 개념이 좀 필요할까..?
둘다 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 }
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 }
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 }
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 }
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 }
'Problem Solving > GCJ logs' 카테고리의 다른 글
| GCJ 2017 Qualification Round (0) | 2017.04.13 |
|---|---|
| Google Code Jam 2016 - Qualification Round (0) | 2016.04.23 |
| Google Code Jam Korea 2012 본선 라운드 - 역대 최고성적? (0) | 2012.03.03 |
| Google Code Jam Korea 2012 Qual. (0) | 2012.03.01 |
| GCJ 2011 Qual (0) | 2011.05.19 |
| Google Code Jam 2010 Round 1 (0) | 2010.05.23 |
| GCJ 2010 Qual1 가볍게(?) 통과..~ (0) | 2010.05.11 |
| Google Code Jam 2010 is in Dublin! (0) | 2010.03.01 |
| Goodbye GCJ 2009..~~ (0) | 2009.09.29 |
| Google Code Jam 2009 Round 1 (2) | 2009.09.12 |