SRM 482
Problem Solving/TopCoder logs 2010. 9. 16. 23:20
어제 밤 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 |