結果

問題 No.352 カード並べ
ユーザー 👑 testestesttestestest
提出日時 2016-03-12 09:57:12
言語 C90
(gcc 11.4.0)
結果
AC  
実行時間 1 ms / 2,000 ms
コード長 914 bytes
コンパイル時間 116 ms
コンパイル使用メモリ 20,608 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-09-25 03:14:59
合計ジャッジ時間 651 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 1 ms
5,376 KB
testcase_02 AC 1 ms
5,376 KB
testcase_03 AC 1 ms
5,376 KB
testcase_04 AC 1 ms
5,376 KB
testcase_05 AC 1 ms
5,376 KB
testcase_06 AC 1 ms
5,376 KB
testcase_07 AC 1 ms
5,376 KB
testcase_08 AC 1 ms
5,376 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.c:1:10: warning: data definition has no type or storage class
    1 | double s;n;main(){for(scanf("%d",&n);--n;)s+=~-n*(3*n+2)/12.+2./-~n;n=!printf("%f",s+1);}
      |          ^
main.c:1:10: warning: type defaults to ‘int’ in declaration of ‘n’ [-Wimplicit-int]
main.c:1:12: warning: return type defaults to ‘int’ [-Wimplicit-int]
    1 | double s;n;main(){for(scanf("%d",&n);--n;)s+=~-n*(3*n+2)/12.+2./-~n;n=!printf("%f",s+1);}
      |            ^~~~
main.c: In function ‘main’:
main.c:1:23: warning: implicit declaration of function ‘scanf’ [-Wimplicit-function-declaration]
    1 | double s;n;main(){for(scanf("%d",&n);--n;)s+=~-n*(3*n+2)/12.+2./-~n;n=!printf("%f",s+1);}
      |                       ^~~~~
main.c:1:1: note: include ‘<stdio.h>’ or provide a declaration of ‘scanf’
  +++ |+#include <stdio.h>
    1 | double s;n;main(){for(scanf("%d",&n);--n;)s+=~-n*(3*n+2)/12.+2./-~n;n=!printf("%f",s+1);}
main.c:1:23: warning: incompatible implicit declaration of built-in function ‘scanf’ [-Wbuiltin-declaration-mismatch]
    1 | double s;n;main(){for(scanf("%d",&n);--n;)s+=~-n*(3*n+2)/12.+2./-~n;n=!printf("%f",s+1);}
      |                       ^~~~~
main.c:1:23: note: include ‘<stdio.h>’ or provide a declaration of ‘scanf’
main.c:1:72: warning: implicit declaration of function ‘printf’ [-Wimplicit-function-declaration]
    1 | double s;n;main(){for(scanf("%d",&n);--n;)s+=~-n*(3*n+2)/12.+2./-~n;n=!printf("%f",s+1);}
      |                                                                        ^~~~~~
main.c:1:72: note: include ‘<stdio.h>’ or provide a declaration of ‘printf’
main.c:1:72: warning: incompatible implicit declaration of built-in function ‘printf’ [-Wbuiltin-declaration-mismatch]
main.c:1:72: note: include ‘<stdio.h>’ or provide a declaration of ‘printf’

ソースコード

diff # 

double s;n;main(){for(scanf("%d",&n);--n;)s+=~-n*(3*n+2)/12.+2./-~n;n=!printf("%f",s+1);}
/*
k≧3としてkのカードを置く際のコスト期待値を求める
kのカードをiとjの間に置く確率は
　iとjが隣り合う確率2/(k-1)
　その間を選ぶ確率1/k
の積であり、これはi,jに依存しない。コスト期待値は
　端におく場合1*2/k
　間に置く場合Σ[0<i<j<k](i*j*2/(k-1)*1/k)
の和となる
ここでΣ[0<i<j<k](i*j)=(k-2)*(k-1)*k*(3k-1)/24なので
（wolframalpha等に任せてもいいが、対称式なので((Σi)^2-Σ(i^2))/2で計算できる）
Σ[0<i<j<k](i*j*2/(k-1)*1/k)=(k-2)*(3k-1)/12
よって求める期待値は (k-2)*(3k-1)/12+2/k
この結果はk=2でも成立。k=1ではダメ。
なので答えは
1+Σ[1<k<=n]((k-2)*(3k-1)/12+2/k)
となる。実装ではindexを1つずらして
1+Σ[0<k<n]((k-1)*(3k+2)/12+2/(k+1))
としている
*/
0