結果

問題 No.76 回数の期待値で練習
ユーザー Lay_ecLay_ec
提出日時 2014-11-24 00:43:39
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 3,144 ms / 5,000 ms
コード長 1,642 bytes
コンパイル時間 627 ms
コンパイル使用メモリ 72,536 KB
実行使用メモリ 50,368 KB
最終ジャッジ日時 2023-08-30 22:39:13
合計ジャッジ時間 7,585 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge12
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1,732 ms
19,368 KB
testcase_01 AC 3,144 ms
50,368 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:81:33: warning: ‘ff’ may be used uninitialized in this function [-Wmaybe-uninitialized]
  a=aa; b=bb; c=cc; d=dd; e=ee; f=ff;
                                ~^~~
main.cpp:81:27: warning: ‘ee’ may be used uninitialized in this function [-Wmaybe-uninitialized]
  a=aa; b=bb; c=cc; d=dd; e=ee; f=ff;
                          ~^~~
main.cpp:81:21: warning: ‘dd’ may be used uninitialized in this function [-Wmaybe-uninitialized]
  a=aa; b=bb; c=cc; d=dd; e=ee; f=ff;
                    ~^~~
main.cpp:81:15: warning: ‘cc’ may be used uninitialized in this function [-Wmaybe-uninitialized]
  a=aa; b=bb; c=cc; d=dd; e=ee; f=ff;
              ~^~~
main.cpp:81:9: warning: ‘bb’ may be used uninitialized in this function [-Wmaybe-uninitialized]
  a=aa; b=bb; c=cc; d=dd; e=ee; f=ff;
        ~^~~
main.cpp:81:3: warning: ‘aa’ may be used uninitialized in this function [-Wmaybe-uninitialized]
  a=aa; b=bb; c=cc; d=dd; e=ee; f=ff;
  ~^~~

ソースコード

diff # 

#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <cstdio>
#include <functional>
#include <set>

using namespace std;

int k;
long double memo[1000100];

int a,b,c,d,e,f;

//x:これまでの和
//k以上になるのに必要な残り回数の期待値を返す
double rec(int x){

	if(memo[x]!=-1) return memo[x];
	if(x>=k) return memo[x]=0.0;

	double res=0.0;
	if(a!=0)res+=rec(x+1)*(a/12.0);
	if(b!=0)res+=rec(x+2)*(b/12.0);
	if(c!=0)res+=rec(x+3)*(c/12.0);
	if(d!=0)res+=rec(x+4)*(d/12.0);
	if(e!=0)res+=rec(x+5)*(e/12.0);
	if(f!=0)res+=rec(x+6)*(f/12.0);

	return memo[x]=res+1.0;

}

int main()
{	
	double min=-1;

	double test[]={
	1.0000000000000000,
	1.0833333333333333,
	1.2569444444444444,
	1.5353009259259260,
	1.6915991512345676,
	2.0513639724794235,
	5.7894594000345325,
	13.789629635263326,
	27.122962962962941,
	267.12296296296188
	};
	int num[]={1,2,3,4,5,6,20,50,100,1000};

	int aa,bb,cc,dd,ee,ff;

	for(a=0;a<=12;a++){
	for(b=0;b<=12;b++){
	for(c=0;c<=12;c++){
	for(d=0;d<=12;d++){
	for(e=0;e<=12;e++){
	for(f=0;f<=12;f++){
		if(a+b+c+d+e+f!=12) continue;

		double x=0;
		for(int i=0;i<10;i++){
			for(int j=0;j<10001;j++) memo[j]=-1;
			k=num[i];
			x+=abs(rec(0)-test[i]);
		}
		if(min==-1 || min>x){min=x; aa=a; bb=b; cc=c; dd=d; ee=e; ff=f;}

	}
	}
	}
	}
	}
	}

	a=aa; b=bb; c=cc; d=dd; e=ee; f=ff;

	int t;
	cin>>t;
	for(int i=0;i<t;i++){
		cin>>k;
		for(long j=0;j<1000100;j++) memo[j]=-1;
		printf("%.16f\n",rec(0));
	}

	return 0;
}
0