## SRM 476 - GOOD

Problem Solving/TopCoder logs 2010. 7. 20. 15:19

지난주 토->일 새벽에 열린 매치..

그동안 시간이 안맞아서 SRM을 세개나 참가 못했는데..

오랜만에 참가해서 좋은 성적이 나와 다행이다..

매우 쉬운 250 과 난해한 550, 1000 이 나오면서 챌 하나로 순위가 급상승했다..

이번 SRM 은 sponsored by Facebook 인데.. 550 문제 description 이 좀..;;

예전에는 쉬운문제가 나오면 240이 넘기도 하고 그랬는데..

이제는 아무리 빨리 풀어도 간신히 200이 넘는수준이니.. 코딩 속도가 왜이리 무뎌졌지..;;

문제 해석이 난해한데 대해 불만이 많은 1인.. 음.. 그 심정은 이해하겠는데.. -_-;;

Level1 - Badgers

badger 라는 애는 기본적으로 hunger 만큼을 먹는데.. 다른 badger 가 먹는걸 보면 1마리당 greed 만큼을 더 먹는다.. totalFood 만큼의 음식이 있을때 최대 몇마리의 badger 를 키울 수 있는지..

brute force 로 풀었다..

k 마리를 키운다고 가정하면 각 badger 당 필요한 food 는 hunger[i] + (k-1) * greed[i]

이 값에 대해서 sort 한 후 앞에 k 개의 합이 totalFood 안에 들어오면 가능

Level2 - FriendTour

to be updated..

Level3 - SpaceshipEvacuation

to be updated..

그동안 시간이 안맞아서 SRM을 세개나 참가 못했는데..

오랜만에 참가해서 좋은 성적이 나와 다행이다..

매우 쉬운 250 과 난해한 550, 1000 이 나오면서 챌 하나로 순위가 급상승했다..

이번 SRM 은 sponsored by Facebook 인데.. 550 문제 description 이 좀..;;

예전에는 쉬운문제가 나오면 240이 넘기도 하고 그랬는데..

이제는 아무리 빨리 풀어도 간신히 200이 넘는수준이니.. 코딩 속도가 왜이리 무뎌졌지..;;

문제 해석이 난해한데 대해 불만이 많은 1인.. 음.. 그 심정은 이해하겠는데.. -_-;;

Level1 - Badgers

badger 라는 애는 기본적으로 hunger 만큼을 먹는데.. 다른 badger 가 먹는걸 보면 1마리당 greed 만큼을 더 먹는다.. totalFood 만큼의 음식이 있을때 최대 몇마리의 badger 를 키울 수 있는지..

brute force 로 풀었다..

k 마리를 키운다고 가정하면 각 badger 당 필요한 food 는 hunger[i] + (k-1) * greed[i]

이 값에 대해서 sort 한 후 앞에 k 개의 합이 totalFood 안에 들어오면 가능

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 comp(const void* x, const void* y)

13 {

14 int* a = (int*)x;

15 int* b = (int*)y;

16 return *a - *b;

17 }

18

19 class Badgers {

20 public:

21

22 int feedMost(vector <int> hunger, vector <int> greed, int totalFood)

23 {

24 int n, i;

25 int cnt, cur;

26 int sum[100];

27 n = hunger.size();

28 for (cnt = n; cnt >= 1; cnt--) {

29 for (i = 0; i < n; i++) {

30 sum[i] = hunger[i] + (cnt-1) * greed[i];

31 }

32 qsort(sum, n, sizeof(int), comp);

33 cur = 0;

34 for (i = 0; i < cnt; i++) {

35 if (cur + sum[i] > totalFood)

36 break;

37 cur += sum[i];

38 }

39 if (i == cnt)

40 return cnt;

41 }

42 return 0;

43 }

44

45 };

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 comp(const void* x, const void* y)

13 {

14 int* a = (int*)x;

15 int* b = (int*)y;

16 return *a - *b;

17 }

18

19 class Badgers {

20 public:

21

22 int feedMost(vector <int> hunger, vector <int> greed, int totalFood)

23 {

24 int n, i;

25 int cnt, cur;

26 int sum[100];

27 n = hunger.size();

28 for (cnt = n; cnt >= 1; cnt--) {

29 for (i = 0; i < n; i++) {

30 sum[i] = hunger[i] + (cnt-1) * greed[i];

31 }

32 qsort(sum, n, sizeof(int), comp);

33 cur = 0;

34 for (i = 0; i < cnt; i++) {

35 if (cur + sum[i] > totalFood)

36 break;

37 cur += sum[i];

38 }

39 if (i == cnt)

40 return cnt;

41 }

42 return 0;

43 }

44

45 };

Level2 - FriendTour

to be updated..

Level3 - SpaceshipEvacuation

to be updated..

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

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 |

TCO10 Qual3 - 이런 젠장 (0) | 2010.05.25 |

TCO10 Qaul2 (2) | 2010.05.13 |

SRM 469 (0) | 2010.05.05 |