어제 밤 12시에 열린 매치..
지난번에 어이없이 야근하느라 참가 못하는거 해보려다가 문제만 열고 참가 못했다.. -_-;;
덕분에 rating만 대박 깎이고.. ㅠ_ㅠ
지난번 매치를 약간이나마 복수해서 다행이다..
뭐 잘 푼건 아닌데.. 그래도 rating이 48점 올랐네..




Level1 - LockersDivOne
1 ~ n 까지의 locker 가 있는데 처음엔 다 잠겨있다..
첫번째 잠겨있는 locker 부터 시작해서 매 2번째 잠겨있는 locker를 open 한다..
그다음엔 첫번째 잠겨있는 locker 부터 또 매 3번째 잠겨있는 locker를 open 한다..
이짓을 계속 반복할 때, 맨 마지막에 열게되는 locker 구하기..

n 이 무려 2000000 이라서 brute force로 풀면 TLE 날꺼같아서.. 뭔가 좋은방법을 찾아보려다 결국 실패.. ㅠ_ㅠ
에라모르겠다.. 그냥 simulation 했는데.. pass 해버렸네.. -_-;;

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <string>
  6 using namespace std;
  7 //#define min(x, y) ((x) > (y) ? (y) : (x))
  8 //#define max(x, y) ((x) > (y) ? (x) : (y))
  9 //#define INF 999999999
 10 //#define EPS 1e-14
 11
 12 int check[2000000];
 13
 14 class LockersDivOne {
 15 public:
 16
 17 int lastOpened(int N)
 18 {
 19     int i;
 20     int skip;
 21     int size;
 22     vector<int> num, temp;
 23
 24     if (N == 1)
 25         return 1;
 26     memset(check, 0, sizeof(check));
 27     for (i = 1; i <= N; i++) {
 28         num.push_back(i);
 29     }
 30     skip = 2;
 31     while (num.size() != 1) {
 32         size = num.size();
 33         for (i = 0; i < size; i += skip) {
 34             check[i] = skip;
 35         }
 36         for (i = 0; i < size; i++) {
 37             if (check[i] != skip) {
 38                 temp.push_back(num[i]);
 39             }
 40         }
 41         num = temp;
 42         temp.clear();
 43         skip++;
 44     }
 45 printf("return %d\n", num[0]);
 46     return num[0];
 47 }
 48
 49 };



Level2 - HanoiGoodAndBad


to be updated..



Level3 - BalancingAct


to be updated..



'Problem Solving > TopCoder logs' 카테고리의 다른 글

SRM 498 - WTF!!  (0) 2011.02.27
SRM 496  (2) 2011.02.02
SRM 491 - Blue 복귀..  (0) 2010.12.21
SRM 490 - Yellow 1차 방어전 성공..  (0) 2010.12.09
SRM 483 - 처음으로 Petr 이겨본 매치..~  (0) 2010.09.26
SRM 479 - 광복절 새벽에 삽질..  (0) 2010.08.16
SRM 478  (2) 2010.08.08
SRM 477  (0) 2010.07.29
SRM 476 - GOOD  (0) 2010.07.20
SRM 472 - 현충일 새벽에 삽질..  (0) 2010.06.07

to Top