Submission #4014661
Source Code Expand
//set many funcs template
//Ver.20181228
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<stdbool.h>
#include<time.h>
#define inf 1072114514
#define llinf 4154118101919364364
#define mod 1000000007
#define pi 3.1415926535897932384
int max(int a,int b){if(a>b){return a;}return b;}
int min(int a,int b){if(a<b){return a;}return b;}
int zt(int a,int b){return max(a,b)-min(a,b);}
int round(int a,int b){if((a%b)*2 >= b){return (a/b)+1;}return a/b;}
int ceil(int a,int b){if(a%b==0){return a/b;}return (a/b)+1;}
int gcd(int a,int b){int c;while(b!=0){c=a%b;a=b;b=c;}return a;}
int lcm(int a,int b){int c=gcd(a,b);a/=c;return a*b;}
int nCr(int a,int b){int i,r=1;for(i=1;i<=b;i++){r*=(a+1-i);r/=i;}return r;}
int nHr(int a,int b){return nCr(a+b-1,b);}
int fact(int a){int i,r=1;for(i=1;i<=a;i++){r*=i;}return r;}
int pow(int a,int b){int i,r=1;for(i=1;i<=b;i++){r*=a;}return r;}
int dsum(int x){int r=0;while(x){r+=(x%10);x/=10;}return r;}
int dsumb(int x,int b){int r=0;while(x){r+=(x%b);x/=b;}return r;}
int sankaku(int x){return ((1+x)*x)/2;}
long long llmax(long long a,long long b){if(a>b){return a;}return b;}
long long llmin(long long a,long long b){if(a<b){return a;}return b;}
long long llzt(long long a,long long b){return llmax(a,b)-llmin(a,b);}
long long llround(long long a,long long b){if((a%b)*2 >= b){return (a/b)+1;}return a/b;}
long long llceil(long long a,long long b){if(a%b==0){return a/b;}return (a/b)+1;}
long long llgcd(long long a,long long b){long long c;while(b!=0){c=a%b;a=b;b=c;}return a;}
long long lllcm(long long a,long long b){long long c=llgcd(a,b);a/=c;return a*b;}
long long llnCr(long long a,long long b){long long i,r=1;for(i=1;i<=b;i++){r*=(a+1-i);r/=i;}return r;}
long long llnHr(long long a,long long b){return llnCr(a+b-1,b);}
long long llfact(long long a){long long i,r=1;for(i=1;i<=a;i++){r*=i;}return r;}
long long llpow(long long a,long long b){long long i,r=1;for(i=1;i<=b;i++){r*=a;}return r;}
long long lldsum(long long x){long long r=0;while(x){r+=(x%10);x/=10;}return r;}
long long lldsumb(long long x,long long b){long long r=0;while(x){r+=(x%b);x/=b;}return r;}
long long llsankaku(long long x){return ((1+x)*x)/2;}
double dbmax(double a,double b){if(a>b){return a;}return b;}
double dbmin(double a,double b){if(a<b){return a;}return b;}
double dbzt(double a,double b){return dbmax(a,b)-dbmin(a,b);}
int sortfncsj(const void *a,const void *b){if(*(int *)a>*(int *)b){return 1;}if(*(int *)a==*(int *)b){return 0;}return -1;}
int sortfnckj(const void *a,const void *b){if(*(int *)a<*(int *)b){return 1;}if(*(int *)a==*(int *)b){return 0;}return -1;}
int llsortfncsj(const void *a,const void *b){if(*(long long *)a>*(long long *)b){return 1;}if(*(long long *)a==*(long long *)b){return 0;}return -1;}
int llsortfnckj(const void *a,const void *b){if(*(long long *)a<*(long long *)b){return 1;}if(*(long long *)a==*(long long *)b){return 0;}return -1;}
int dbsortfncsj(const void *a,const void *b){if(*(double *)a>*(double *)b){return 1;}if(*(double *)a==*(double *)b){return 0;}return -1;}
int dbsortfnckj(const void *a,const void *b){if(*(double *)a<*(double *)b){return 1;}if(*(double *)a==*(double *)b){return 0;}return -1;}
int strsortfncsj(const void *a,const void *b){return strcmp((char *)a,(char *)b);}
int strsortfnckj(const void *a,const void *b){return strcmp((char *)b,(char *)a);}
int chsortfncsj(const void *a,const void *b){if(*(char *)a>*(char *)b){return 1;}if(*(char *)a==*(char *)b){return 0;}return -1;}
int chsortfnckj(const void *a,const void *b){if(*(char *)a<*(char *)b){return 1;}if(*(char *)a==*(char *)b){return 0;}return -1;}
void shuffledget(int x[],int n){
srand(time(0));
int i,b[524288],p,c;
for(i=0;i<n;i++){
b[i]=i;
}
for(i=n;i>=1;i--){
p=rand()%i;
c=b[i-1];b[i-1]=b[p];b[p]=c;
}
for(i=0;i<n;i++){
scanf("%d",&x[b[i]]);
}
}
int dx4[4]={1,-1,0,0};
int dy4[4]={0,0,1,-1};
int dx8[8]={-1,-1,-1,0,0,1,1,1};
int dy8[8]={-1,0,1,-1,1,-1,0,1};
int search(int x,int a[],int n){
int st=0,fi=n-1,te;
while(st<=fi){
te=(st+fi)/2;
if(a[te]<x){st=te+1;}else{fi=te-1;}
}
return st;
}
void prarr(int arr[],int n){
int i;
for(i=0;i<n;i++){
if(i){printf(" ");}
printf("%d",arr[i]);
}
printf("\n");
return;
}
typedef struct{
int val;
int node;
}sd;
int sdsortfnc(const void *a,const void *b){
if(((sd*)a)->val < ((sd*)b)->val){return -1;}
if(((sd*)a)->val > ((sd*)b)->val){return 1;}
return 0;
}
double dp[128][128][128];
double mov[128][128]={0.0};
double rep(int a,int b,int c){
if(a<0 || b<0 || c<0){return 0.0;}
if(dp[a][b][c]>=0.0){
return dp[a][b][c];
}
dp[a][b][c]=rep(a-1,b,c)/3.0;
dp[a][b][c]+=rep(a,b-1,c)/3.0;
dp[a][b][c]+=rep(a,b,c-1)/3.0;
return dp[a][b][c];
}
void calc(){
int i,j,k;
int p,q,r,v;
for(i=0;i<128;i++){
for(j=0;j<128;j++){
for(k=0;k<128;k++){
dp[i][j][k]=-1.0;
}
}
}
dp[0][0][0]=1.0;
for(i=2;i<110;i++){
for(j=0;j<=i;j++){
for(k=0;k<=i;k++){
p=j;q=k;r=i-j-k;
if(r<0){continue;}
if(p==i || q==i || r==i){
v=i;
}
else if(p==q && q==r){
v=i;
}
else{
v=inf;
if(p!=0){v=min(p,v);}
if(q!=0){v=min(q,v);}
if(r!=0){v=min(r,v);}
}
mov[i][v]+=rep(p,q,r);
//if(i<=3){printf("%d %d %d:%.12lf\n",p,q,r,rep(p,q,r));}
}
}
}
return;
}
int main(void){
calc();
int i,j,k,n;
double tdp[128]={0.0},ndp[128]={0.0},res=0.0;
scanf("%d",&n);
tdp[n]=1.0;
for(i=1;i<7777;i++){
for(j=2;j<=n;j++){
for(k=1;k<=j;k++){
ndp[k]+=tdp[j]*mov[j][k];
}
}
//printf("%d:<%.12lf>\n",1,ndp[1]);
for(j=2;j<=n;j++){
//printf("%d:<%.12lf>\n",j,ndp[j]);
tdp[j]=ndp[j];
ndp[j]=0.0;
}//printf("\n");
res+=((double)i*ndp[1]);
ndp[1]=0.0;
}
printf("%.12lf\n",res);
return 0;
}
Submission Info
Submission Time
2019-01-14 19:48:17+0900
Task
C - ゲーマーじゃんけん
User
physics0523
Language
C (GCC 5.4.1)
Score
100
Code Size
6186 Byte
Status
AC
Exec Time
53 ms
Memory
16640 KB
Compile Error
./Main.c:16:5: warning: conflicting types for built-in function ‘round’
int round(int a,int b){if((a%b)*2 >= b){return (a/b)+1;}return a/b;}
^
./Main.c:17:5: warning: conflicting types for built-in function ‘ceil’
int ceil(int a,int b){if(a%b==0){return a/b;}return (a/b)+1;}
^
./Main.c:23:5: warning: conflicting types for built-in function ‘pow’
int pow(int a,int b){int i,r=1;for(i=1;i<=b;i++){r*=a;}return r;}
^
./Main.c:30:11: warning: conflicting types for built-in function ‘llround’
long long llround(long long a,long long b){if((a%b)*2 >= b){return (a/b)+1;}return a/b;}
^
./Main.c: In function ‘shuffledget’:
./Main.c:66:9: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&x[b[i]]);
^
./Main.c: In function ‘main’:
./Main.c:159:5: warning: ignoring return value of ‘scanf’, 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
12 ms
16640 KB
input-003.txt
AC
12 ms
16640 KB
input-004.txt
AC
12 ms
16640 KB
input-005.txt
AC
12 ms
16640 KB
input-006.txt
AC
12 ms
16640 KB
input-007.txt
AC
12 ms
16640 KB
input-008.txt
AC
12 ms
16640 KB
input-009.txt
AC
12 ms
16640 KB
input-010.txt
AC
13 ms
16640 KB
input-011.txt
AC
13 ms
16640 KB
input-012.txt
AC
13 ms
16640 KB
input-013.txt
AC
13 ms
16640 KB
input-014.txt
AC
13 ms
16640 KB
input-015.txt
AC
13 ms
16640 KB
input-016.txt
AC
13 ms
16640 KB
input-017.txt
AC
14 ms
16640 KB
input-018.txt
AC
13 ms
16640 KB
input-019.txt
AC
14 ms
16640 KB
input-020.txt
AC
14 ms
16640 KB
input-021.txt
AC
14 ms
16640 KB
input-022.txt
AC
14 ms
16640 KB
input-023.txt
AC
14 ms
16640 KB
input-024.txt
AC
15 ms
16640 KB
input-025.txt
AC
15 ms
16640 KB
input-026.txt
AC
15 ms
16640 KB
input-027.txt
AC
15 ms
16640 KB
input-028.txt
AC
16 ms
16640 KB
input-029.txt
AC
15 ms
16640 KB
input-030.txt
AC
16 ms
16640 KB
input-031.txt
AC
16 ms
16640 KB
input-032.txt
AC
17 ms
16640 KB
input-033.txt
AC
17 ms
16640 KB
input-034.txt
AC
18 ms
16640 KB
input-035.txt
AC
18 ms
16640 KB
input-036.txt
AC
18 ms
16640 KB
input-037.txt
AC
19 ms
16640 KB
input-038.txt
AC
19 ms
16640 KB
input-039.txt
AC
19 ms
16640 KB
input-040.txt
AC
20 ms
16640 KB
input-041.txt
AC
20 ms
16640 KB
input-042.txt
AC
20 ms
16640 KB
input-043.txt
AC
20 ms
16640 KB
input-044.txt
AC
21 ms
16640 KB
input-045.txt
AC
21 ms
16640 KB
input-046.txt
AC
22 ms
16640 KB
input-047.txt
AC
22 ms
16640 KB
input-048.txt
AC
23 ms
16640 KB
input-049.txt
AC
23 ms
16640 KB
input-050.txt
AC
23 ms
16640 KB
input-051.txt
AC
24 ms
16640 KB
input-052.txt
AC
24 ms
16640 KB
input-053.txt
AC
24 ms
16640 KB
input-054.txt
AC
25 ms
16640 KB
input-055.txt
AC
25 ms
16640 KB
input-056.txt
AC
26 ms
16640 KB
input-057.txt
AC
26 ms
16640 KB
input-058.txt
AC
27 ms
16640 KB
input-059.txt
AC
27 ms
16640 KB
input-060.txt
AC
28 ms
16640 KB
input-061.txt
AC
28 ms
16640 KB
input-062.txt
AC
29 ms
16640 KB
input-063.txt
AC
30 ms
16640 KB
input-064.txt
AC
30 ms
16640 KB
input-065.txt
AC
30 ms
16640 KB
input-066.txt
AC
31 ms
16640 KB
input-067.txt
AC
31 ms
16640 KB
input-068.txt
AC
32 ms
16640 KB
input-069.txt
AC
32 ms
16640 KB
input-070.txt
AC
33 ms
16640 KB
input-071.txt
AC
33 ms
16640 KB
input-072.txt
AC
34 ms
16640 KB
input-073.txt
AC
35 ms
16640 KB
input-074.txt
AC
35 ms
16640 KB
input-075.txt
AC
36 ms
16640 KB
input-076.txt
AC
36 ms
16640 KB
input-077.txt
AC
37 ms
16640 KB
input-078.txt
AC
37 ms
16640 KB
input-079.txt
AC
38 ms
16640 KB
input-080.txt
AC
38 ms
16640 KB
input-081.txt
AC
40 ms
16640 KB
input-082.txt
AC
40 ms
16640 KB
input-083.txt
AC
40 ms
16640 KB
input-084.txt
AC
41 ms
16640 KB
input-085.txt
AC
42 ms
16640 KB
input-086.txt
AC
42 ms
16640 KB
input-087.txt
AC
44 ms
16640 KB
input-088.txt
AC
43 ms
16640 KB
input-089.txt
AC
44 ms
16640 KB
input-090.txt
AC
45 ms
16640 KB
input-091.txt
AC
45 ms
16640 KB
input-092.txt
AC
46 ms
16640 KB
input-093.txt
AC
47 ms
16640 KB
input-094.txt
AC
49 ms
16640 KB
input-095.txt
AC
48 ms
16640 KB
input-096.txt
AC
50 ms
16640 KB
input-097.txt
AC
49 ms
16640 KB
input-098.txt
AC
51 ms
16640 KB
input-099.txt
AC
51 ms
16640 KB
input-100.txt
AC
53 ms
16640 KB