Submission #1026604
Source Code Expand
#include <iostream> #include <cstdio> #include <vector> #include <string> #include <algorithm> #include <set> #include <map> #define rep(i,n) for(int i=0; i<(n); i++) #define reps(i,x,n) for(int i=x; i<(n); i++) #define rrep(i,n) for(int i=(n)-1; i>=0; i--) #define all(X) (X).begin(),(X).end() #define X first #define Y second #define pb push_back #define eb emplace_back using namespace std; typedef long long int ll; typedef pair<int,int> pii; typedef pair<ll,ll> pll; template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; } template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; } template<class A, size_t N, class T> void Fill(A (&a)[N], const T &v){ fill( (T*)a, (T*)(a+N), v ); } const ll INF = 0x3fffffff; const ll MOD = 1e9+7; ll cmb_memo[10005][10005]={}; ll cmb(int n, int r){ if( cmb_memo[n][r] ) return cmb_memo[n][r]; if( r == 0 || r == n ) return 1; return cmb_memo[n][r] = (cmb(n-1,r) + cmb(n-1,r-1)) % MOD; } double memo[200]={}; double solve(int N){ // cout << "solve N=" << N << endl; if( N <= 1 ) return 0; if( memo[N] ) return memo[N]; double stay_rate=0.0, nex_e=0.0, nex_rate=0.0, sum=0.0; rep(g,N+1) rep(t,N+1-g) rep(p,N+1-g-t){ if( g + t + p != N ) continue; double num = cmb(N, g) * cmb(N-g, t); // cout << "N=" << N << "\tg=" << g << " t=" << t << " p=" << p << " num=" << num << endl; sum += num; if( g == 0 && t == 0 ) stay_rate += num; else if( t == 0 && p == 0 ) stay_rate += num; else if( p == 0 && g == 0 ) stay_rate += num; else if( g == t && t == p ) stay_rate += num; else if( g == 0 && t <= p ){ nex_e += num * solve(t); nex_rate += num; } else if( t == 0 && p <= g ){ nex_e += num * solve(p); nex_rate += num; } else if( p == 0 && g <= t ){ nex_e += num * solve(g); nex_rate += num; } else if( g == 0 && t > p ){ nex_e += num * solve(p); nex_rate += num; } else if( t == 0 && p > g ){ nex_e += num * solve(g); nex_rate += num; } else if( p == 0 && g > t ){ nex_e += num * solve(t); nex_rate += num; } else if( g < t && g < p ){ nex_e += num * solve(g); nex_rate += num; } else if( t < g && t < p ){ nex_e += num * solve(t); nex_rate += num; } else if( p < g && p < t ){ nex_e += num * solve(p); nex_rate += num; } else if( g == t && t < p ){ nex_e += num * solve(g); nex_rate += num; } else if( t == p && p < g ){ nex_e += num * solve(t); nex_rate += num; } else if( p == g && g < t ){ nex_e += num * solve(p); nex_rate += num; } } stay_rate /= sum; nex_e /= nex_rate; nex_rate /= sum; // cout << "stay_rate=" << stay_rate << "\tnex_e=" << nex_e << "\tnex_rate=" << nex_rate << endl; double rate=1.0; rep(i,100){ //memo[N] += rate * (1.0-stay_rate) * ((double)(i+1) + nex_e); memo[N] += rate * nex_rate * ((double)(i+1) + nex_e); rate *= stay_rate; } return memo[N]; } int main(){ //ios_base::sync_with_stdio(0); int N, ans=0; cin >> N; printf("%.8f\n", solve(N) ); return 0; }
Submission Info
Submission Time | |
---|---|
Task | C - ゲーマーじゃんけん |
User | oyas |
Language | C++11 (GCC 4.8.1) |
Score | 0 |
Code Size | 3062 Byte |
Status | WA |
Exec Time | 34 ms |
Memory | 1432 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 | 20 ms | 1044 KB |
input-003.txt | AC | 20 ms | 924 KB |
input-004.txt | AC | 18 ms | 924 KB |
input-005.txt | AC | 20 ms | 924 KB |
input-006.txt | AC | 20 ms | 920 KB |
input-007.txt | AC | 19 ms | 1040 KB |
input-008.txt | AC | 20 ms | 1028 KB |
input-009.txt | AC | 20 ms | 920 KB |
input-010.txt | AC | 20 ms | 924 KB |
input-011.txt | AC | 19 ms | 1044 KB |
input-012.txt | AC | 20 ms | 1048 KB |
input-013.txt | AC | 20 ms | 1044 KB |
input-014.txt | AC | 19 ms | 1040 KB |
input-015.txt | AC | 20 ms | 1048 KB |
input-016.txt | AC | 19 ms | 1048 KB |
input-017.txt | AC | 20 ms | 1044 KB |
input-018.txt | AC | 18 ms | 1048 KB |
input-019.txt | AC | 19 ms | 1044 KB |
input-020.txt | AC | 18 ms | 1040 KB |
input-021.txt | AC | 20 ms | 1048 KB |
input-022.txt | AC | 18 ms | 1044 KB |
input-023.txt | AC | 19 ms | 1044 KB |
input-024.txt | AC | 18 ms | 1044 KB |
input-025.txt | AC | 20 ms | 1048 KB |
input-026.txt | AC | 20 ms | 1048 KB |
input-027.txt | AC | 20 ms | 1036 KB |
input-028.txt | AC | 20 ms | 1044 KB |
input-029.txt | AC | 21 ms | 1048 KB |
input-030.txt | AC | 20 ms | 1044 KB |
input-031.txt | AC | 20 ms | 1044 KB |
input-032.txt | AC | 21 ms | 1168 KB |
input-033.txt | WA | 20 ms | 1048 KB |
input-034.txt | WA | 20 ms | 1172 KB |
input-035.txt | WA | 20 ms | 1176 KB |
input-036.txt | WA | 20 ms | 1044 KB |
input-037.txt | WA | 20 ms | 1176 KB |
input-038.txt | WA | 18 ms | 1048 KB |
input-039.txt | WA | 20 ms | 984 KB |
input-040.txt | WA | 20 ms | 1044 KB |
input-041.txt | WA | 20 ms | 1164 KB |
input-042.txt | WA | 20 ms | 1164 KB |
input-043.txt | WA | 20 ms | 1172 KB |
input-044.txt | WA | 20 ms | 1164 KB |
input-045.txt | WA | 18 ms | 1168 KB |
input-046.txt | WA | 20 ms | 1164 KB |
input-047.txt | WA | 20 ms | 1176 KB |
input-048.txt | WA | 19 ms | 1176 KB |
input-049.txt | WA | 34 ms | 1144 KB |
input-050.txt | WA | 21 ms | 1172 KB |
input-051.txt | WA | 20 ms | 1168 KB |
input-052.txt | WA | 20 ms | 1172 KB |
input-053.txt | WA | 21 ms | 1176 KB |
input-054.txt | WA | 20 ms | 1168 KB |
input-055.txt | WA | 20 ms | 1160 KB |
input-056.txt | WA | 20 ms | 1172 KB |
input-057.txt | WA | 19 ms | 1168 KB |
input-058.txt | WA | 20 ms | 1176 KB |
input-059.txt | WA | 20 ms | 1176 KB |
input-060.txt | WA | 21 ms | 1172 KB |
input-061.txt | WA | 20 ms | 1172 KB |
input-062.txt | WA | 20 ms | 1304 KB |
input-063.txt | WA | 20 ms | 1300 KB |
input-064.txt | WA | 19 ms | 1304 KB |
input-065.txt | WA | 20 ms | 1300 KB |
input-066.txt | WA | 21 ms | 1300 KB |
input-067.txt | WA | 21 ms | 1176 KB |
input-068.txt | WA | 21 ms | 1304 KB |
input-069.txt | WA | 20 ms | 1300 KB |
input-070.txt | WA | 19 ms | 1168 KB |
input-071.txt | WA | 21 ms | 1288 KB |
input-072.txt | WA | 21 ms | 1284 KB |
input-073.txt | WA | 21 ms | 1176 KB |
input-074.txt | WA | 21 ms | 1304 KB |
input-075.txt | WA | 21 ms | 1296 KB |
input-076.txt | WA | 21 ms | 1304 KB |
input-077.txt | WA | 19 ms | 1304 KB |
input-078.txt | WA | 21 ms | 1304 KB |
input-079.txt | WA | 22 ms | 1240 KB |
input-080.txt | WA | 20 ms | 1300 KB |
input-081.txt | WA | 20 ms | 1304 KB |
input-082.txt | WA | 21 ms | 1304 KB |
input-083.txt | WA | 19 ms | 1300 KB |
input-084.txt | WA | 21 ms | 1300 KB |
input-085.txt | WA | 21 ms | 1300 KB |
input-086.txt | WA | 21 ms | 1304 KB |
input-087.txt | WA | 20 ms | 1208 KB |
input-088.txt | WA | 21 ms | 1304 KB |
input-089.txt | WA | 21 ms | 1300 KB |
input-090.txt | WA | 21 ms | 1300 KB |
input-091.txt | WA | 19 ms | 1296 KB |
input-092.txt | WA | 21 ms | 1432 KB |
input-093.txt | WA | 21 ms | 1432 KB |
input-094.txt | WA | 21 ms | 1304 KB |
input-095.txt | WA | 21 ms | 1304 KB |
input-096.txt | WA | 20 ms | 1428 KB |
input-097.txt | WA | 21 ms | 1432 KB |
input-098.txt | WA | 22 ms | 1368 KB |
input-099.txt | WA | 22 ms | 1428 KB |
input-100.txt | WA | 21 ms | 1428 KB |