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

Problem Solving/TopCoder logs 2010. 8. 16. 15:40

토->일 새벽에 열린 매치.. 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 도 안나고.. 탑코더 좋은데..?

Level2 - TheAirTripDivOne

to be updated..

Level3 - TheBoardingDivOne

to be upated..

근데 문제가 드럽게 나와서 다들 고생이 많았다..

나는 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 };

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 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 |

SRM 470 (0) | 2010.05.28 |