Submission #326530
Source Code Expand
#include <iostream> #include <sstream> #include <fstream> #include <string> #include <vector> #include <deque> #include <queue> #include <stack> #include <set> #include <map> #include <algorithm> #include <utility> #include <bitset> #include <cmath> #include <cstdlib> #include <ctime> #include <cstring> #include <cstdio> using namespace std; #define REP(i,n) for((i)=0;(i)<(int)(n);(i)++) #define foreach(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++) const double kEps = 1e-9; typedef unsigned long long ull; typedef pair<int,int> P; double nCr[102][102]; double E[102]; P combination_type(int rock, int scissor, int paper) { vector<int> v; if (rock) v.push_back(rock); if (scissor) v.push_back(scissor); if (paper) v.push_back(paper); sort(v.begin(), v.end()); int mn = v[0]; int mn_cnt = count(v.begin(), v.end(), mn); int sum = rock + scissor + paper; P ret; if (v.size() == 1) { ret.first = 3; ret.second = 0; } else if (mn_cnt == 1) { ret.first = 1; ret.second = sum - mn; } else if (mn_cnt == 2) { ret.first = 2; ret.second = sum - mn; } else { ret.first = 3; ret.second = 0; } return ret; } double solve(int n) { const double kDenom = pow(3, n); vector<double> pn(102, 0); for (int r = 0; r <= n; r++) { for (int s = 0; (s + r) <= n; s++) { for (int p = 0; (s + r + p) <= n; p++) { if (s + r + p < n) continue; P tmp = combination_type(r, s, p); // printf("r,s,p=%d,%d,%d value=%llu f,s=%d,%d\n", // r, s, p, nCr[n][r] * nCr[n-r][s], tmp.first, tmp.second); if (tmp.first == 1 || tmp.first == 2) { pn[n - tmp.second] += nCr[n][r] * nCr[n-r][s] / kDenom; } else { pn[n] += nCr[n][r] * nCr[n-r][s] / kDenom; } } } } for (int i = 0; i <= n; i++) { //printf("pn[%d] = %.3f\n", i, pn[i]); //pn[i] /= kDenom; } // expression double ret = pn[n]; for (int i = 1; i <= n - 1; i++) { //printf("compute sum at index=%d\n", i); ret += pn[i] * (E[i] + 1); } ret /= (1 - pn[n]); return ret; } int main() { // nCr memset(nCr, 0, sizeof nCr); nCr[0][0] = 1; for (int i = 1; i <= 100; i++) { nCr[i][0] = 1; for (int j = 1; j <= i; j++) { nCr[i][j] = nCr[i-1][j-1] + nCr[i-1][j]; } } // do memset(E, 0, sizeof E); E[1] = 0; for (int i = 2; i <= 100; i++) { E[i] = solve(i); //printf("E[%d] = %.3f\n", i, E[i]); } int in; while (cin >> in) { cout << E[in] << endl; } return 0; }
Submission Info
Submission Time | |
---|---|
Task | C - ゲーマーじゃんけん |
User | brly |
Language | C++ (G++ 4.6.4) |
Score | 0 |
Code Size | 2726 Byte |
Status | WA |
Exec Time | 100 ms |
Memory | 1392 KB |
Judge Result
Set Name | All | ||||
---|---|---|---|---|---|
Score / Max Score | 0 / 100 | ||||
Status |
|
Set Name | Test Cases |
---|---|
All | input-002.txt, input-003.txt, input-004.txt, input-005.txt, input-006.txt, input-007.txt, input-008.txt, input-009.txt, input-010.txt, input-011.txt, input-012.txt, input-013.txt, input-014.txt, input-015.txt, input-016.txt, input-017.txt, input-018.txt, input-019.txt, input-020.txt, input-021.txt, input-022.txt, input-023.txt, input-024.txt, input-025.txt, input-026.txt, input-027.txt, input-028.txt, input-029.txt, input-030.txt, input-031.txt, input-032.txt, input-033.txt, input-034.txt, input-035.txt, input-036.txt, input-037.txt, input-038.txt, input-039.txt, input-040.txt, input-041.txt, input-042.txt, input-043.txt, input-044.txt, input-045.txt, input-046.txt, input-047.txt, input-048.txt, input-049.txt, input-050.txt, input-051.txt, input-052.txt, input-053.txt, input-054.txt, input-055.txt, input-056.txt, input-057.txt, input-058.txt, input-059.txt, input-060.txt, input-061.txt, input-062.txt, input-063.txt, input-064.txt, input-065.txt, input-066.txt, input-067.txt, input-068.txt, input-069.txt, input-070.txt, input-071.txt, input-072.txt, input-073.txt, input-074.txt, input-075.txt, input-076.txt, input-077.txt, input-078.txt, input-079.txt, input-080.txt, input-081.txt, input-082.txt, input-083.txt, input-084.txt, input-085.txt, input-086.txt, input-087.txt, input-088.txt, input-089.txt, input-090.txt, input-091.txt, input-092.txt, input-093.txt, input-094.txt, input-095.txt, input-096.txt, input-097.txt, input-098.txt, input-099.txt, input-100.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
input-002.txt | AC | 99 ms | 1288 KB |
input-003.txt | AC | 82 ms | 1220 KB |
input-004.txt | WA | 95 ms | 1384 KB |
input-005.txt | AC | 100 ms | 1208 KB |
input-006.txt | AC | 80 ms | 1216 KB |
input-007.txt | WA | 80 ms | 1212 KB |
input-008.txt | WA | 78 ms | 1216 KB |
input-009.txt | WA | 76 ms | 1304 KB |
input-010.txt | WA | 75 ms | 1388 KB |
input-011.txt | WA | 78 ms | 1220 KB |
input-012.txt | AC | 76 ms | 1388 KB |
input-013.txt | WA | 78 ms | 1308 KB |
input-014.txt | WA | 77 ms | 1312 KB |
input-015.txt | WA | 78 ms | 1300 KB |
input-016.txt | AC | 78 ms | 1312 KB |
input-017.txt | AC | 78 ms | 1344 KB |
input-018.txt | WA | 77 ms | 1304 KB |
input-019.txt | WA | 78 ms | 1304 KB |
input-020.txt | AC | 76 ms | 1216 KB |
input-021.txt | WA | 76 ms | 1308 KB |
input-022.txt | WA | 78 ms | 1216 KB |
input-023.txt | AC | 78 ms | 1304 KB |
input-024.txt | WA | 77 ms | 1300 KB |
input-025.txt | WA | 79 ms | 1300 KB |
input-026.txt | WA | 79 ms | 1212 KB |
input-027.txt | WA | 80 ms | 1308 KB |
input-028.txt | AC | 80 ms | 1300 KB |
input-029.txt | WA | 77 ms | 1216 KB |
input-030.txt | AC | 78 ms | 1304 KB |
input-031.txt | WA | 77 ms | 1244 KB |
input-032.txt | WA | 84 ms | 1384 KB |
input-033.txt | WA | 79 ms | 1308 KB |
input-034.txt | WA | 80 ms | 1260 KB |
input-035.txt | WA | 79 ms | 1384 KB |
input-036.txt | WA | 78 ms | 1392 KB |
input-037.txt | WA | 79 ms | 1384 KB |
input-038.txt | AC | 78 ms | 1308 KB |
input-039.txt | WA | 79 ms | 1216 KB |
input-040.txt | WA | 82 ms | 1220 KB |
input-041.txt | WA | 78 ms | 1308 KB |
input-042.txt | WA | 79 ms | 1220 KB |
input-043.txt | WA | 80 ms | 1384 KB |
input-044.txt | WA | 83 ms | 1288 KB |
input-045.txt | WA | 79 ms | 1304 KB |
input-046.txt | WA | 79 ms | 1392 KB |
input-047.txt | WA | 80 ms | 1296 KB |
input-048.txt | WA | 78 ms | 1312 KB |
input-049.txt | WA | 82 ms | 1292 KB |
input-050.txt | AC | 79 ms | 1304 KB |
input-051.txt | WA | 80 ms | 1220 KB |
input-052.txt | WA | 78 ms | 1220 KB |
input-053.txt | WA | 79 ms | 1388 KB |
input-054.txt | WA | 79 ms | 1216 KB |
input-055.txt | AC | 79 ms | 1388 KB |
input-056.txt | WA | 79 ms | 1300 KB |
input-057.txt | WA | 78 ms | 1308 KB |
input-058.txt | WA | 79 ms | 1380 KB |
input-059.txt | AC | 77 ms | 1216 KB |
input-060.txt | WA | 79 ms | 1388 KB |
input-061.txt | WA | 77 ms | 1308 KB |
input-062.txt | AC | 79 ms | 1380 KB |
input-063.txt | WA | 78 ms | 1388 KB |
input-064.txt | WA | 78 ms | 1304 KB |
input-065.txt | WA | 77 ms | 1220 KB |
input-066.txt | WA | 78 ms | 1304 KB |
input-067.txt | WA | 77 ms | 1300 KB |
input-068.txt | WA | 78 ms | 1304 KB |
input-069.txt | WA | 79 ms | 1212 KB |
input-070.txt | WA | 79 ms | 1388 KB |
input-071.txt | WA | 77 ms | 1220 KB |
input-072.txt | WA | 79 ms | 1380 KB |
input-073.txt | WA | 79 ms | 1380 KB |
input-074.txt | WA | 79 ms | 1388 KB |
input-075.txt | AC | 78 ms | 1388 KB |
input-076.txt | AC | 79 ms | 1388 KB |
input-077.txt | WA | 79 ms | 1212 KB |
input-078.txt | AC | 79 ms | 1244 KB |
input-079.txt | WA | 79 ms | 1244 KB |
input-080.txt | WA | 79 ms | 1376 KB |
input-081.txt | WA | 78 ms | 1384 KB |
input-082.txt | WA | 79 ms | 1216 KB |
input-083.txt | AC | 78 ms | 1304 KB |
input-084.txt | WA | 79 ms | 1212 KB |
input-085.txt | WA | 78 ms | 1304 KB |
input-086.txt | WA | 77 ms | 1216 KB |
input-087.txt | WA | 78 ms | 1304 KB |
input-088.txt | WA | 78 ms | 1308 KB |
input-089.txt | AC | 78 ms | 1300 KB |
input-090.txt | WA | 78 ms | 1384 KB |
input-091.txt | WA | 78 ms | 1388 KB |
input-092.txt | WA | 79 ms | 1384 KB |
input-093.txt | WA | 79 ms | 1240 KB |
input-094.txt | AC | 78 ms | 1296 KB |
input-095.txt | AC | 78 ms | 1376 KB |
input-096.txt | WA | 78 ms | 1308 KB |
input-097.txt | WA | 79 ms | 1236 KB |
input-098.txt | WA | 77 ms | 1208 KB |
input-099.txt | AC | 79 ms | 1384 KB |
input-100.txt | WA | 78 ms | 1384 KB |