TopCoder SRM 448 Div 1
Problem Solving/TopCoder logs 2009. 9. 11. 23:08
어제 저녁 8시에 열린 매치..
시간대도 좋았고 요즘 ACM 시즌 + 구글 코드잼 시즌 이라 상당히 많은 사람이 참여했다..
나는 저번 상금매치도 시간대가 안맞아서 참가 못하고 오랜만에 참가했는데..
완전 삽질끝에 또다시 망쳐버렸다.. 아.. 나의 rating은 어디로 가고있는것일까.. ㅠ_ㅠ
250 점 문제는 맞았다고 생각했는데 결국 system test fail 당했다..
우리방에서 나혼자 system test fail 이라서 완전 쪽팔렸다.. -_-;
대부분의 case 는 통과하는데 특정 case 에서 소숫점 몇째자리부터 틀리기 시작한다..
이거 디버깅할수도없고.. 도대체 뭐가 틀린건지.. 쩝..
Level1 - TheBlackJackDivOne
카드를 몇장 받았고 현재까지 카드의 숫자 합이 21 이 넘을때까지 계속 카드를 받아야 한다.. 앞으로 카드를 평균 몇장을 더 받을것인지.. 기대값 구하기..
가능한 상태가 얼마 없기때문에 굳이 memorization 할것까지도 없었다..
괜히 어렵게 생각해서 뭔가 틀렸거나 precision error 거나..
Level2 - TheCardShufflingDivOne
괜히 어렵게 생각해서 뭔가 틀렸거나 precision error 거나..
1 #include <iostream>
2 #include <cstdio>
3 #include <algorithm>
4 #include <vector>
5 #include <string>
6 #include <map>
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 999999999
11
12 int get_val(char ch)
13 {
14 if (ch >= '2' && ch <= '9')
15 return ch - '0';
16 if (ch == 'A')
17 return 11;
18 return 10;
19 }
20
21 double recur(int sum, int* cnt, int left)
22 {
23 int i;
24 double res, p;
25 if (sum >= 21)
26 return 0;
27 res = 1.0;
28 for (i = 2; i <= 11; i++) {
29 if (cnt[i]) {
30 p = (double)cnt[i] / left;
31 cnt[i]--;
32 res += p * recur(sum + i, cnt, left-1);
33 cnt[i]++;
34 }
35 }
36 return res;
37 }
38
39 class TheBlackJackDivOne {
40 public:
41
42 double expected(vector <string> cards)
43 {
44 int i, k;
45 int sum;
46 int cnt[100];
47 double res;
48 for (i = 2; i <= 9; i++) {
49 cnt[i] = 4;
50 }
51 cnt[10] = 16;
52 cnt[11] = 4;
53 sum = 0;
54 for (i = 0; i < cards.size(); i++) {
55 k = get_val(cards[i][0]);
56 cnt[k]--;
57 sum += k;
58 }
59 res = recur(sum, cnt, 52-cards.size());
60 return res;
61 }
62
63 };
2 #include <cstdio>
3 #include <algorithm>
4 #include <vector>
5 #include <string>
6 #include <map>
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 999999999
11
12 int get_val(char ch)
13 {
14 if (ch >= '2' && ch <= '9')
15 return ch - '0';
16 if (ch == 'A')
17 return 11;
18 return 10;
19 }
20
21 double recur(int sum, int* cnt, int left)
22 {
23 int i;
24 double res, p;
25 if (sum >= 21)
26 return 0;
27 res = 1.0;
28 for (i = 2; i <= 11; i++) {
29 if (cnt[i]) {
30 p = (double)cnt[i] / left;
31 cnt[i]--;
32 res += p * recur(sum + i, cnt, left-1);
33 cnt[i]++;
34 }
35 }
36 return res;
37 }
38
39 class TheBlackJackDivOne {
40 public:
41
42 double expected(vector <string> cards)
43 {
44 int i, k;
45 int sum;
46 int cnt[100];
47 double res;
48 for (i = 2; i <= 9; i++) {
49 cnt[i] = 4;
50 }
51 cnt[10] = 16;
52 cnt[11] = 4;
53 sum = 0;
54 for (i = 0; i < cards.size(); i++) {
55 k = get_val(cards[i][0]);
56 cnt[k]--;
57 sum += k;
58 }
59 res = recur(sum, cnt, 52-cards.size());
60 return res;
61 }
62
63 };
Level2 - TheCardShufflingDivOne
to be updated..
Level3 - TheCardLineDivOne
to be updated..
'Problem Solving > TopCoder logs' 카테고리의 다른 글
| TopCoder SRM 453.5 (??) Div 1 (0) | 2009.11.26 |
|---|---|
| [SRM 453] 탑코더 아레나 폭발 -> unrated event (4) | 2009.11.18 |
| TopCoder SRM 450 Div 1 (0) | 2009.10.19 |
| TopCoder Member Pilot 2 (0) | 2009.10.01 |
| TopCoder SRM 449 Div 1 (0) | 2009.09.24 |
| Beta SRM (Member-Run Round) (0) | 2009.08.19 |
| [SRM 446] 매치가 뭐 이래..?! (Unchallengeable Match) (6) | 2009.08.09 |
| TopCoder SRM 445 Div 1 (0) | 2009.07.24 |
| [SRM 444] 개인 역대 최고 등급 경신..~ (0) | 2009.07.09 |
| TopCoder SRM 442 Div 1 (11) | 2009.06.14 |