A.Password Problem

2012-04-28

02:01 |

B文字のパスワードをA文字まで打った。i番目の文字が正しく打てている確率はp[i]。以後正しい文字を打てるとして、0〜A文字削除して残りを打つ、あきらめてenterを押して再度全部打つという選択肢がある。残り打鍵数の期待値が一番低いものを計算する問題。

げげ、ぱっと見て確率DPみたいな感じ？と思ったけど、i番目の文字まで戻ったときに全部合ってる確率だけ分かればよいことが分かった。

int main() {
	int test_cases;
	cin>>test_cases;
	REP(ttt, test_cases) {
		int A, B;
		cin>>A>>B;
		
		double ans = 100000000;
		double co = 1.0;
		
		REP(i, A+1) {
			// co is prod[0, i)
			int bs = A-i;
			double p = (bs*2+B-A+1)*co+(bs*2+B-A+1+B+1)*(1-co);
//			cout<<bs<<" "<<p<<endl;
			ans=min(ans, p);
			if(i<A) {
				double in;
				cin>>in;
				co *= in;
			}
		}
		ans=min(ans, B+2.0); // enter right away
		cout<<"Case #"<<ttt+1<<": "<<setprecision(10)<<ans<<endl;
	}
	return 0;
}