GCJ 2010 Qual1 가볍게(?) 통과..~
Problem Solving/GCJ logs 2010. 5. 11. 15:30
어제 있었던 구글 코드잼 퀄 라운드에서 1문제 풀고 가볍게 통과했다.. -_-;
작년에는 3문제 다 풀고 99점 맞고 통과했는데..
이거 문제가 어려워지는건지 내가 점점 못하는건지.. 쩝..
어쨋든 한문제 풀고나니 pass 는 한거같어서 그냥 접었다..~
A번 문제는 easy 에 대해서는 그냥 시키는데로 brute force 로 해결..
large 에 대해서는 도저히 시간안에 나올것같지 않아서 고민하던중..
2^n 번 snap 을 수행하면 모든 snapper 가 OFF OFF OFF ... OFF 로 초기화된다는 사실 발견..
간단하게 풀리는 문제였다..~~
내가짯던 코드나 좀 남겨둬야지..~
A. Snapper Chain (small)
1 #include <iostream>
2 #include <cstdio>
3 #include <algorithm>
4 using namespace std;
5 int n, k;
6 int main()
7 {
8 int tc, cn;
9 int i, j;
10 int fl;
11 int state;
12 scanf("%d", &tc);
13 for (cn = 1; cn <= tc; cn++) {
14 scanf("%d%d", &n, &k);
15 state = 0;
16 for (i = 0; i < k; i++) {
17 fl = 1;
18 for (j = 0; j < n && fl; j++) {
19 if (((1 << j) & state) == 0) {
20 fl = 0;
21 state |= (1 << j);
22 }
23 else {
24 state -= (1 << j);
25 }
26 }
27 }
28 if (state == (1 << n) - 1) {
29 printf("Case #%d: ON\n", cn);
30 }
31 else {
32 printf("Case #%d: OFF\n", cn);
33 }
34 }
35 return 0;
36 }
1 #include <stdio.h>
2 #include <string.h>
3 int n, k;
4 int main()
5 {
6 int tc, cn;
7 int i, j;
8 int fl;
9 int state;
10 scanf("%d", &tc);
11 for (cn = 1; cn <= tc; cn++) {
12 scanf("%d%d", &n, &k);
13 i = (1 << n);
14 j = i;
15 fl = 0;
16 while (j-1 <= k) {
17 if (k == j-1) {
18 fl = 1;
19 break;
20 }
21 j += i;
22 }
23 if (fl) {
24 printf("Case #%d: ON\n", cn);
25 }
26 else {
27 printf("Case #%d: OFF\n", cn);
28 }
29 }
30 return 0;
31 }
'Problem Solving > GCJ logs' 카테고리의 다른 글
| Google Code Jam Korea 2012 본선 라운드 - 역대 최고성적? (0) | 2012.03.03 |
|---|---|
| Google Code Jam Korea 2012 Qual. (0) | 2012.03.01 |
| Goodbye GCJ 2011 (0) | 2011.05.27 |
| GCJ 2011 Qual (0) | 2011.05.19 |
| Google Code Jam 2010 Round 1 (0) | 2010.05.23 |
| 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 |
| Google Code Jam 2009 Qualification Round 후기..~ (2) | 2009.09.06 |
| GCJ 2라운드에서 끝내 좌절.. ㅠ_ㅠ (0) | 2008.08.03 |