SRM 479 - 광복절 새벽에 삽질..

토->일 새벽에 열린 매치.. Div1 에만 무려 700명 넘게 참가했다..
근데 문제가 드럽게 나와서 다들 고생이 많았다..
나는 250 을 매우 늦게 풀었는데도 풀구하고 rating 이 올랐다..~
근데.. 아깝게 4점 차이로 yellow 등극 실패.. ㅠ_ㅠ

470번대 마지막 매치라서 그런지 문제 description에 47 이 자주 등장한다.. -_-;  Level1 - TheCoffeeTimeDivOne

more..

1부터 n 까지 일렬로 있고 커피와 티는 0 번 위치에 있다.. tea 를 원하는 승객이 주어지고 나머지는 다 coffee 를 원할때 스튜어디스가 모두 serve 하는데 드는 비용 최소화하기.. 스튜어디스는 한번에 coffee 또는 tea 중에 하나만 가지고 이동할수 있고 최대 7명까지 serve 할 수 있다.. 그 이상 serve 하기 위해서는 다시 0번으로 돌아와서 coffee 또는 tea 를 채워야한다.. 블라블라.. 문제 뭐이리 복잡하냐..

많은 사람들을 안드로로 보냈다..~ challenge 도 많았지만.. system test fail 도 상당히 많았다..
이번에 문제출제자 도대체 누구여..~

이 문제는 greedy + simulation 으로 풀었다..~
일단 tea 부터 다 serve 하고 그담에 coffee 를 serve 하는데.. 마지막에 돌아오는 거리를 최소화하기 위해
가장 뒤에서부터 serve 한다..~

loop 를 4천만번 넘게 돌아도 TLE 안나고.. 배열 4천만개 잡고 MLE 도 안나고.. 탑코더 좋은데..?

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 char check;
13
14 class TheCoffeeTimeDivOne {
15 public:
16
17 long long find(int n, vector <int> tea)
18 {
19     int size;
20     int i, j, fl;
21     int cur;
22     long long sum;
23     size = tea.size();
24     sort(tea.begin(), tea.end());
25     sum = 0;
26     cur = 0;
27     j = 0;
28     fl = 0;
29     memset(check, 0, sizeof(check));
30     for (i = size-1; i >= 0; i--) {
31         if (!fl) {
32             sum += 47;
33             fl++;
34         }
35         check[tea[i]] = 1;
36
37         if (cur == 0) {
38             sum += tea[i] + 4;
39         }
40         else {
41             sum += cur - tea[i] + 4;
42         }
43         j++;
44         cur = tea[i];
45         if (j == 7) {
46             cur = 0;
47             sum += tea[i];
48             j = 0;
49             fl = 0;
50         }
51     }
52     sum += cur;
53 cout << "sum1 = " << sum << endl;
54
55     if (size == n) {
56         return sum;
57     }
58
59     fl = 0;
60     cur = 0;
61     j = 0;
62     for (i = n; i >= 1; i--) {
63         if (check[i])
64             continue;
65         if (!fl) {
66             fl++;
67             sum += 47;
68         }
69         if (cur == 0) {
70             sum += i + 4;
71         }
72         else {
73             sum += cur - i + 4;
74         }
75         j++;
76         cur = i;
77         if (j == 7) {
78             sum += i;
79             cur = 0;
80             j = 0;
81             fl = 0;
82         }
83     }
84     sum += cur;
85     cur = 0;
86 cout << "sum2 = " << sum << endl;
87     return sum;
88 }
89
90 };

Level2 - TheAirTripDivOne

더보기

to be updated..

Level3 - TheBoardingDivOne

더보기

to be upated..

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

 SRM 496  (2) 2011.02.02 2010.12.21 2010.12.09 2010.09.26 2010.09.16 2010.08.16 2010.08.08 2010.07.29 2010.07.20 2010.06.07 2010.05.28