TCO12 R1A - 606등 -_-;;

Problem Solving/TopCoder logs 2012. 4. 1. 03:41
TopCoder Open 2012 첫판..
예전에는 Qual 라운드부터 시작했는데.. 이번에는 처음부터 1 Round 이다..

600등 안에 들어야 다음 라운드 진출인데.. 606등 -_-;; 어처구니 없음.. ㅠㅠ
250점은 쉬운건데 문제 이해도 잘 못했고 코딩하다 말리고.. 어쨋든..
500점짜리가 의외로 쉬워서 잘 풀긴했는데.. 아쉽게 탈락했다..
두문제 풀고도 탈락하다니.. 이런..

근데.. yellow 1차 방어는 성공했다.. rating 변화가 없음.. -_-




Level1 -  EllysJuice 


자신의 차례가 되면 남은 음료수의 반을 마신다.. 가장 많이 마신 사람이 winner 인데..
list 순서를 임의로 변경했을 때 winner 가 될 수 있는 사람 모두 찾기..

문제 자체는 간단한데 코딩에서 삽질하는 바람에 매우 늦게 풀었다..
모든 permutation 을 다 구해서 확인..

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <string>
  6 #include <set>
  7 #include <map>
  8 #include <cmath>
  9 using namespace std;
 10 //#define min(x, y) ((x) > (y) ? (y) : (x))
 11 //#define max(x, y) ((x) > (y) ? (x) : (y))
 12 //#define INF 999999999
 13 //#define EPS 1e-14
 14
 15 class EllysJuice {
 16 public:
 17
 18 vector <string> getWinners(vector <string> players)
 19 {
 20     int n, m;
 21     int i, j, k;
 22     int max_idx;
 23     double juice[2];
 24     string str;
 25     map<string, double> score;
 26     map<string, double>::iterator it;
 27     double max1;
 28     set<string> ss;
 29     vector<string> p;
 30     vector<string> res;
 31
 32     for (i = 0; i < players.size(); i++) {
 33         if (ss.find(players[i]) == ss.end()) {
 34             ss.insert(players[i]);
 35             p.push_back(players[i]);
 36         }
 37     }
 38     n = players.size();
 39     sort(players.begin(), players.end());
 40     ss.clear();
 41 //printf("n = %d, m = %d\n", n, m);
 42     do {
 43         for (i = 0, j = 0; i < n; i++, j++) {
 44             j %= m;
 45             if (players[i] != players[j])
 46                 break;
 47         }
 48         if (i == n || 1) {
 49 /*
 50 for (j = 0; j < n; j++) {
 51 printf("player[%d] = %s\n", j, players[j].c_str());
 52 }
 53 printf("\n");
 54 */
 55             juice[0] = 1;
 56             juice[1] = 1;
 57             score.clear();
 58             k = 0;
 59             for (j = 0; j < n; j++, k++) {
 60                 k %= 2;
 61                 score[players[j]] += (juice[k] * 0.5);
 62                 juice[k] /= 2.0;
 63             }
 64             max1 = 0;
 65             for (it = score.begin(); it != score.end(); it++) {
 66                 if (max1 < it->second)
 67                     max1 = it->second;
 68             }
 69             k = 0;
 70             max_idx = -1;
 71             str = "";
 72             for (it = score.begin(); it != score.end(); it++) {
 73                 if (fabs(it->second-max1) < 1e-12) {
 74                     k++;
 75                     str = it->first;
 76                 }
 77             }
 78             if (k == 1) {
 79                 //res.push_back(str);
 80                 ss.insert(str);
 81             }
 82         }
 83     } while (next_permutation(players.begin(), players.end()));
 84
 85     set<string>::iterator it2;
 86 for (it2 = ss.begin(); it2 != ss.end(); it2++) {
 87 res.push_back(*it2);
 88 cout << "..." << *it2 << endl;
 89 }
 90
 91     return res;
 92 }
 93
 94 };



Level2 - EllysFractions


분자 분모가 서로소이고 분자*분모가 N! 이 되는 경우의 수..

잘 생각해보면 N 을 factoring 해서 각 소수를 분자와 분모로 나눌 수 있는 경우의 수가 된다..

예를들어 N = 4 라고 하면
4! = 24 = 2^3 * 3

소수는 2, 3 밖에 없으므로 2와 3을 분자와 분모로 분배할 수 있는 경우의 수 = 4가지
여기서 분모가 분자보다 무조건 커야하므로 경우의 수가 반이되므로 2가지가 된다.

근데 2^3 이기때문에 2가 3개 있지만 얘네들은 모두 같은쪽으로 가야된다..
왜냐하면 분자와 분모가 서로소가 되어야 하므로.. 그래서 그냥 하나라고 생각하면 된다..

  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 is_prime[301];
 13 int prime_cnt;
 14
 15 void sieve()
 16 {
 17     int i, j;
 18     memset(is_prime, -1, sizeof(is_prime));
 19     is_prime[0] = is_prime[1] = 0;
 20     for (i = 2; i <= 300; i++) {
 21         if (is_prime[i]) {
 22             for (j = 2; i*j <= 300; j++) {
 23                 is_prime[i*j] = 0;
 24             }
 25         }
 26     }
 27 }
 28
 29 class EllysFractions {
 30 public:
 31
 32 long long getCount(int N)
 33 {
 34     int i, j;
 35     long long f[300];
 36     long long cnt;
 37     long long sum;
 38     sieve();
 39     f[0] = 0;
 40     f[1] = 0;
 41     f[2] = 1;
 42     f[3] = 2;
 43     for (i = 4; i <= N; i++) {
 44         cnt = 0;
 45         for (j = 2; j <= i; j++) {
 46             if (is_prime[j]) {
 47                 cnt++;
 48             }
 49         }
 50         f[i] = (1LL << (cnt-1));
 51     }
 52     sum = 0;
 53     for (i = 0; i <= N; i++) {
 54         sum += f[i];
 55     }
 56     return sum;
 57 }
 58
 59 };




저작자표시

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

TCO13 Round 1C 생명연장 매치  (0) 2013.03.10
SRM 529  (0) 2012.01.15
SRM 521  (0) 2011.10.24
SRM 511  (0) 2011.07.04
TCO11 R1 - 탈락  (0) 2011.06.23
SRM 509 !!  (0) 2011.06.09
SRM 507 - 나이스!  (0) 2011.05.30
TCO11 Qual2  (0) 2011.05.20
TCO11 Qual1  (2) 2011.05.15
SRM 504 - unrated event  (0) 2011.04.27
  • By helloneo

to Top

티스토리툴바