어제 있었던 구글 코드잼 퀄 라운드에서 1문제 풀고 가볍게 통과했다.. -_-;

작년에는 3문제 다 풀고 99점 맞고 통과했는데..
이거 문제가 어려워지는건지 내가 점점 못하는건지.. 쩝..

어쨋든 한문제 풀고나니 pass 는 한거같어서 그냥 접었다..~




A번 문제는 easy 에 대해서는 그냥 시키는데로 brute force 로 해결..
large 에 대해서는 도저히 시간안에 나올것같지 않아서 고민하던중..
2^n 번 snap 을 수행하면 모든 snapper 가 OFF OFF OFF ... OFF 로 초기화된다는 사실 발견..
간단하게 풀리는 문제였다..~~

내가짯던 코드나 좀 남겨둬야지..~


  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 }




to Top