Submission #324811
Source Code Expand
#include <bits/stdc++.h> using namespace std; typedef long double ldb; typedef long long ll; ldb cdp[111][111]; ldb C(int n,int r) { if( n==r || r==0 ) return 1; if(cdp[n][r]>=0)return cdp[n][r]; return cdp[n][r]=C(n-1,r)+C(n-1,r-1); } ldb dp[111]; ldb f(int a) { ldb ret=1; while( a-- ) ret *= 3; return ret; } ldb solve(int n) { if(n==1) return 0; if(dp[n]>=0)return dp[n]; ldb res=1; ldb cnt[111] = {}; //ldb b = pow(3,n); ldb b = f(n); for( int i = 0; i <= n; i++ ) { for( int j = 0; j <= n-i; j++ ) { int k = n-j-i; int v[]={i,j,k},m=114514; for( int ii = 0; ii < 3; ii++ ) if(v[ii]>0&&v[ii]<m) m=v[ii]; //cnt[m] += 1; ldb p = 1*C(n,i)*C(n-i,j); //printf("%d %d %d %.0Lf %d\n",i,j,k,p,m); switch( count(v,v+3,m) ) { case 1: if( m == n ) { cnt[n] += p; } else { cnt[m] += p; } break; case 2: cnt[m] += p; break; case 3: cnt[n] += p; break; } } } //for( int i = 1; i <= n; i++ ) { //printf("%d:%.0Lf\n",n,cnt[i]); //} for( int i = n-1; i >= 1; i-- ) { res += ((cnt[i]/b)*solve(i)); } res /= (1-cnt[n]/b); return dp[n]=res; } int main(void) { int n; scanf("%d",&n); for(int i=0;i<111;i++)for(int j=0;j<111;j++)cdp[i][j]=-1; for(int i=0;i<111;i++)dp[i]=-1; /* srand(time(0)); ll res = 0; const ll a = 100000000*n; for( int i = 0; i < a; i++ ) { res += sim(n); } printf("%lld %.10Lf\n",res,ld(res)/a); */ printf("%.10Lf\n",solve(n)); return 0; }
Submission Info
Submission Time | |
---|---|
Task | C - ゲーマーじゃんけん |
User | roxion1377 |
Language | C++11 (GCC 4.8.1) |
Score | 100 |
Code Size | 1674 Byte |
Status | AC |
Exec Time | 31 ms |
Memory | 1188 KB |
Compile Error
./Main.cpp: In function ‘int main()’: ./Main.cpp:71:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d",&n); ^
Judge Result
Set Name | All | ||
---|---|---|---|
Score / Max Score | 100 / 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 | 23 ms | 1056 KB |
input-003.txt | AC | 23 ms | 1056 KB |
input-004.txt | AC | 23 ms | 1004 KB |
input-005.txt | AC | 23 ms | 1060 KB |
input-006.txt | AC | 25 ms | 1056 KB |
input-007.txt | AC | 23 ms | 1056 KB |
input-008.txt | AC | 24 ms | 1052 KB |
input-009.txt | AC | 25 ms | 1056 KB |
input-010.txt | AC | 23 ms | 1060 KB |
input-011.txt | AC | 25 ms | 1056 KB |
input-012.txt | AC | 24 ms | 1052 KB |
input-013.txt | AC | 23 ms | 1052 KB |
input-014.txt | AC | 25 ms | 936 KB |
input-015.txt | AC | 25 ms | 924 KB |
input-016.txt | AC | 23 ms | 1056 KB |
input-017.txt | AC | 24 ms | 928 KB |
input-018.txt | AC | 27 ms | 1004 KB |
input-019.txt | AC | 24 ms | 1060 KB |
input-020.txt | AC | 23 ms | 1052 KB |
input-021.txt | AC | 24 ms | 1060 KB |
input-022.txt | AC | 23 ms | 1012 KB |
input-023.txt | AC | 24 ms | 1060 KB |
input-024.txt | AC | 23 ms | 1052 KB |
input-025.txt | AC | 24 ms | 1056 KB |
input-026.txt | AC | 24 ms | 1052 KB |
input-027.txt | AC | 24 ms | 1048 KB |
input-028.txt | AC | 24 ms | 924 KB |
input-029.txt | AC | 24 ms | 1056 KB |
input-030.txt | AC | 23 ms | 928 KB |
input-031.txt | AC | 23 ms | 1052 KB |
input-032.txt | AC | 24 ms | 1052 KB |
input-033.txt | AC | 25 ms | 1056 KB |
input-034.txt | AC | 23 ms | 928 KB |
input-035.txt | AC | 24 ms | 940 KB |
input-036.txt | AC | 24 ms | 1060 KB |
input-037.txt | AC | 23 ms | 1060 KB |
input-038.txt | AC | 24 ms | 1052 KB |
input-039.txt | AC | 25 ms | 1184 KB |
input-040.txt | AC | 23 ms | 1188 KB |
input-041.txt | AC | 25 ms | 1184 KB |
input-042.txt | AC | 25 ms | 1064 KB |
input-043.txt | AC | 23 ms | 1188 KB |
input-044.txt | AC | 25 ms | 1060 KB |
input-045.txt | AC | 25 ms | 1188 KB |
input-046.txt | AC | 25 ms | 1064 KB |
input-047.txt | AC | 25 ms | 1184 KB |
input-048.txt | AC | 24 ms | 1180 KB |
input-049.txt | AC | 24 ms | 1180 KB |
input-050.txt | AC | 24 ms | 1064 KB |
input-051.txt | AC | 25 ms | 1188 KB |
input-052.txt | AC | 25 ms | 1060 KB |
input-053.txt | AC | 25 ms | 1188 KB |
input-054.txt | AC | 26 ms | 1056 KB |
input-055.txt | AC | 25 ms | 1184 KB |
input-056.txt | AC | 26 ms | 992 KB |
input-057.txt | AC | 24 ms | 988 KB |
input-058.txt | AC | 26 ms | 1060 KB |
input-059.txt | AC | 24 ms | 1176 KB |
input-060.txt | AC | 25 ms | 1184 KB |
input-061.txt | AC | 24 ms | 1060 KB |
input-062.txt | AC | 27 ms | 1060 KB |
input-063.txt | AC | 25 ms | 1060 KB |
input-064.txt | AC | 25 ms | 1184 KB |
input-065.txt | AC | 27 ms | 1064 KB |
input-066.txt | AC | 25 ms | 1176 KB |
input-067.txt | AC | 26 ms | 1056 KB |
input-068.txt | AC | 25 ms | 1188 KB |
input-069.txt | AC | 26 ms | 1064 KB |
input-070.txt | AC | 26 ms | 1060 KB |
input-071.txt | AC | 27 ms | 1064 KB |
input-072.txt | AC | 26 ms | 1064 KB |
input-073.txt | AC | 25 ms | 1188 KB |
input-074.txt | AC | 27 ms | 1064 KB |
input-075.txt | AC | 26 ms | 1124 KB |
input-076.txt | AC | 25 ms | 1180 KB |
input-077.txt | AC | 26 ms | 1048 KB |
input-078.txt | AC | 27 ms | 1040 KB |
input-079.txt | AC | 26 ms | 1052 KB |
input-080.txt | AC | 30 ms | 1012 KB |
input-081.txt | AC | 28 ms | 1052 KB |
input-082.txt | AC | 28 ms | 1068 KB |
input-083.txt | AC | 28 ms | 1124 KB |
input-084.txt | AC | 28 ms | 1136 KB |
input-085.txt | AC | 28 ms | 1060 KB |
input-086.txt | AC | 27 ms | 1056 KB |
input-087.txt | AC | 29 ms | 1116 KB |
input-088.txt | AC | 29 ms | 1068 KB |
input-089.txt | AC | 29 ms | 1116 KB |
input-090.txt | AC | 29 ms | 1120 KB |
input-091.txt | AC | 28 ms | 1184 KB |
input-092.txt | AC | 29 ms | 1180 KB |
input-093.txt | AC | 27 ms | 1064 KB |
input-094.txt | AC | 29 ms | 1064 KB |
input-095.txt | AC | 30 ms | 1184 KB |
input-096.txt | AC | 30 ms | 1184 KB |
input-097.txt | AC | 30 ms | 1064 KB |
input-098.txt | AC | 30 ms | 1068 KB |
input-099.txt | AC | 30 ms | 1060 KB |
input-100.txt | AC | 31 ms | 1136 KB |