어제 새벽에 열린 매치..~
이번에도 쉬운문제를 못풀면서.. 어려운 매치가 됐다.. 젠장..
그래도 다행히 챌 하나를 성공시켜서 rating 은 소폭 하락에 그쳤다..
요즘들어서 계속 250 을 못푸는데.. 이거 좀 공부좀 해야겠는데..




Level1 - LotteryCheating

임의의 숫자가 주어질때 약수의 개수가 홀수개가되도록 바꾸고 싶다.. digit 을 최소 몇개를 바꿔야 할까..?

약수의 개수가 홀수개가 되려면 n^2 꼴인 수만 가능하다.. -_-;;
이 사실을 코딩시간 종료 직전에 눈치채는바람에 결국 못풀었다..

왜 그렇게 되는지는 약수의 개수 구하는 공식을 생각해보면 된다..
어떤수를 소인수분해했을때 p1^a1 * p2^a2 * ... * pn^an 일때
약수의 개수 = (a1 + 1) * (a2 + 1) * ... * (an + 1) 가 되는걸 초등학교때 배운것같다.. -_-
따라서 약수의 개수가 홀수가 되려면 a1, a2, ..., an 이 모두 짝수이어야 한다..

위 사실을 알았으면..
일단 미리 n^2 꼴의 수를 모두 저장 해놓고.. input 과 가장 비슷한 수를 brute force 로 찾으면 되겠다..

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <string>
  6 #include <set>
  7 using namespace std;
  8 //#define min(x, y) ((x) > (y) ? (y) : (x))
  9 //#define max(x, y) ((x) > (y) ? (x) : (y))
 10 //#define INF 100
 11 //#define EPS 1e-14
 12
 13 class LotteryCheating {
 14 public:
 15
 16 int minimalChange(string ID)
 17 {
 18     int res;
 19     int i, j, k;
 20     int len;
 21     char buf[100];
 22     long long x;
 23
 24     len = ID.size();
 25     res = 10;
 26     for (x = 0; x < 100000; x++) {
 27         string str;
 28         sprintf(buf, "%lld", x*x);
 29         str = buf;
 30         if (str.size() > len)
 31             continue;
 32         while (str.size() < len) {
 33             str = '0' + str;
 34         }
 35         k = 0;
 36         for (j = 0; j < len; j++) {
 37             if (ID[j] != str[j])
 38                 k++;
 39         }
 40         if (k < res)
 41             res = k;
 42     }
 43 printf("res = %d\n", res);
 44     return res;
 45 }
 46
 47 };




Level2 - LotteryPyaterochka


n by 5 짜리 board 에 1 ~ 5*n 까지 번호가 적혀있다..
random 하게 5개 수를 뽑았을 때, 그 중 3개의 숫가 임의의 한 row 에 있으면 win 이다..
win 할 확률 구하기..

임의의 숫자 5개를 뽑았을 때, 임의의 row 에 3개의 숫자가 걸릴 확률 =
정답중에 3개를 뽑는 가지수 * 정답 아닌거중에 2개를 뽑는 가지수 / 전체중에 임의의 5개 뽑는 가지수
가 된다..

이런걸 조건부 확률 이라는거 같음..

위에 식을 기본으로.. 3개뿐만 아니라, 4개, 5개가 걸릴 경우의 수도 더해주면 된다..
그리고 각 row 에 대해서 확률이 같으므로.. 모든 row 의 개수 n 을 곱해준다..

역시.. 확률은 어렵구만.. ㅠ_ㅠ

  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 #define MAXN 502
 13 /* combi[n][r] = n C r */
 14 long long combi[MAXN][MAXN];
 15 void get_combi()
 16 {
 17     int i, j;
 18     for (i = 0; i < MAXN; i++) {
 19         combi[i][i] = 1;
 20         combi[i][0] = 1;
 21     }
 22     for (i = 0; i < MAXN; i++) {
 23         for (j = 1; j < i; j++) {
 24             combi[i][j] = combi[i-1][j-1] + combi[i-1][j];
 25         }
 26     }
 27 }
 28
 29 class LotteryPyaterochka {
 30 public:
 31
 32 double chanceToWin(int N)
 33 {
 34     double res;
 35     if (N == 1)
 36         return 1.0;
 37     get_combi();
 38
 39     res = (double)(N * (combi[5][3]*combi[5*N-5][2] + combi[5][4]*combi[5*N-5][1] + combi[5][5]*combi[5*N-5][0])) / (double)combi[5*N][5];
 40     return res;
 41 }
 42
 43 };




Level3 - DrawingBlackCrosses



to be updated..


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

SRM 470  (0) 2010.05.28
TCO10 Qual3 - 이런 젠장  (0) 2010.05.25
TCO10 Qaul2  (2) 2010.05.13
SRM 469  (0) 2010.05.05
[SRM 468] 보람이 없구만..  (0) 2010.04.21
SRM 466  (0) 2010.04.05
TopCoder Open 2010 일정..  (0) 2010.03.31
SRM 464  (0) 2010.03.18
TopCoder SRM 463  (2) 2010.03.06
TopCoder SRM 459 Div 1  (0) 2010.01.20
TopCoder SRM 458 Div 1  (0) 2010.01.17

Leave a Comment


to Top