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

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




Level1 - TheCoffeeTimeDivOne

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[44777778];
 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
SRM 491 - Blue 복귀..  (0) 2010.12.21
SRM 490 - Yellow 1차 방어전 성공..  (0) 2010.12.09
SRM 483 - 처음으로 Petr 이겨본 매치..~  (0) 2010.09.26
SRM 482  (0) 2010.09.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
SRM 470  (0) 2010.05.28

to Top