지난주 토->일 새벽에 열린 매치..
그동안 시간이 안맞아서 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 };



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

to Top