9ce62cec1c 2015-03-26 kinaba: #include <iostream> 9ce62cec1c 2015-03-26 kinaba: #include <sstream> 9ce62cec1c 2015-03-26 kinaba: #include <iomanip> 9ce62cec1c 2015-03-26 kinaba: #include <vector> 9ce62cec1c 2015-03-26 kinaba: #include <string> 9ce62cec1c 2015-03-26 kinaba: #include <map> 9ce62cec1c 2015-03-26 kinaba: #include <set> 9ce62cec1c 2015-03-26 kinaba: #include <algorithm> 9ce62cec1c 2015-03-26 kinaba: #include <numeric> 9ce62cec1c 2015-03-26 kinaba: #include <iterator> 9ce62cec1c 2015-03-26 kinaba: #include <functional> 9ce62cec1c 2015-03-26 kinaba: #include <complex> 9ce62cec1c 2015-03-26 kinaba: #include <queue> 9ce62cec1c 2015-03-26 kinaba: #include <stack> 9ce62cec1c 2015-03-26 kinaba: #include <cmath> 9ce62cec1c 2015-03-26 kinaba: #include <cassert> 9ce62cec1c 2015-03-26 kinaba: #include <tuple> 9ce62cec1c 2015-03-26 kinaba: using namespace std; 9ce62cec1c 2015-03-26 kinaba: typedef long long LL; 9ce62cec1c 2015-03-26 kinaba: typedef complex<double> CMP; 9ce62cec1c 2015-03-26 kinaba: 9ce62cec1c 2015-03-26 kinaba: class SquareScores { public: 9ce62cec1c 2015-03-26 kinaba: double calcexpectation(vector <int> p, string s) 9ce62cec1c 2015-03-26 kinaba: { 9ce62cec1c 2015-03-26 kinaba: double ans = 0.0; 9ce62cec1c 2015-03-26 kinaba: for(int k=0; k<s.size(); ++k) { 9ce62cec1c 2015-03-26 kinaba: int num_q = 0; 9ce62cec1c 2015-03-26 kinaba: char ch = '*'; 9ce62cec1c 2015-03-26 kinaba: for(int e=k; e<s.size(); ++e) { 9ce62cec1c 2015-03-26 kinaba: if(s[e]=='?') 9ce62cec1c 2015-03-26 kinaba: num_q++; 9ce62cec1c 2015-03-26 kinaba: if(ch == '*') { 9ce62cec1c 2015-03-26 kinaba: if(s[e] != '?') 9ce62cec1c 2015-03-26 kinaba: ch = s[e]; 9ce62cec1c 2015-03-26 kinaba: } else { 9ce62cec1c 2015-03-26 kinaba: if(s[e] != '?' && s[e] != ch) 9ce62cec1c 2015-03-26 kinaba: break; 9ce62cec1c 2015-03-26 kinaba: } 9ce62cec1c 2015-03-26 kinaba: 9ce62cec1c 2015-03-26 kinaba: for(int ci=0; ci<p.size(); ++ci) 9ce62cec1c 2015-03-26 kinaba: if(ch=='*' || ch-'a'==ci) 9ce62cec1c 2015-03-26 kinaba: ans += pow(p[ci]/100.0, num_q); 9ce62cec1c 2015-03-26 kinaba: } 9ce62cec1c 2015-03-26 kinaba: } 9ce62cec1c 2015-03-26 kinaba: return ans; 9ce62cec1c 2015-03-26 kinaba: } 9ce62cec1c 2015-03-26 kinaba: }; 9ce62cec1c 2015-03-26 kinaba: 9ce62cec1c 2015-03-26 kinaba: // BEGIN CUT HERE 9ce62cec1c 2015-03-26 kinaba: #include <ctime> 9ce62cec1c 2015-03-26 kinaba: double start_time; string timer() 9ce62cec1c 2015-03-26 kinaba: { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 9ce62cec1c 2015-03-26 kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 9ce62cec1c 2015-03-26 kinaba: { os << "{ "; 9ce62cec1c 2015-03-26 kinaba: for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 9ce62cec1c 2015-03-26 kinaba: os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 9ce62cec1c 2015-03-26 kinaba: void verify_case(const double& Expected, const double& Received) { 9ce62cec1c 2015-03-26 kinaba: bool ok = (abs(Expected - Received) < 1e-9); 9ce62cec1c 2015-03-26 kinaba: if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 9ce62cec1c 2015-03-26 kinaba: cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 9ce62cec1c 2015-03-26 kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 9ce62cec1c 2015-03-26 kinaba: #define END verify_case(_, SquareScores().calcexpectation(p, s));} 9ce62cec1c 2015-03-26 kinaba: int main(){ 9ce62cec1c 2015-03-26 kinaba: 9ce62cec1c 2015-03-26 kinaba: CASE(0) 9ce62cec1c 2015-03-26 kinaba: int p_[] = {1, 99}; 9ce62cec1c 2015-03-26 kinaba: vector <int> p(p_, p_+sizeof(p_)/sizeof(*p_)); 9ce62cec1c 2015-03-26 kinaba: string s = "aaaba"; 9ce62cec1c 2015-03-26 kinaba: double _ = 8.0; 9ce62cec1c 2015-03-26 kinaba: END 9ce62cec1c 2015-03-26 kinaba: CASE(1) 9ce62cec1c 2015-03-26 kinaba: int p_[] = {10, 20, 70}; 9ce62cec1c 2015-03-26 kinaba: vector <int> p(p_, p_+sizeof(p_)/sizeof(*p_)); 9ce62cec1c 2015-03-26 kinaba: string s = "aa?bbbb"; 9ce62cec1c 2015-03-26 kinaba: double _ = 15.0; 9ce62cec1c 2015-03-26 kinaba: END 9ce62cec1c 2015-03-26 kinaba: CASE(2) 9ce62cec1c 2015-03-26 kinaba: int p_[] = {10, 20, 30, 40}; 9ce62cec1c 2015-03-26 kinaba: vector <int> p(p_, p_+sizeof(p_)/sizeof(*p_)); 9ce62cec1c 2015-03-26 kinaba: string s = "a??c?dc?b"; 9ce62cec1c 2015-03-26 kinaba: double _ = 11.117; 9ce62cec1c 2015-03-26 kinaba: END 9ce62cec1c 2015-03-26 kinaba: CASE(3) 9ce62cec1c 2015-03-26 kinaba: int p_[] = {25, 25, 21, 2, 2, 25}; 9ce62cec1c 2015-03-26 kinaba: vector <int> p(p_, p_+sizeof(p_)/sizeof(*p_)); 9ce62cec1c 2015-03-26 kinaba: string s = "a??b???????ff??e"; 9ce62cec1c 2015-03-26 kinaba: double _ = 21.68512690712425; 9ce62cec1c 2015-03-26 kinaba: END 9ce62cec1c 2015-03-26 kinaba: CASE(4) 9ce62cec1c 2015-03-26 kinaba: int p_[] = {4, 4, 4, 3, 4, 4, 4, 4, 4, 4, 3, 4, 4, 4, 3, 4, 4, 4, 4, 4, 4, 4, 3, 4, 4, 4}; 9ce62cec1c 2015-03-26 kinaba: vector <int> p(p_, p_+sizeof(p_)/sizeof(*p_)); 9ce62cec1c 2015-03-26 kinaba: string s = "??????????????????????????????"; 9ce62cec1c 2015-03-26 kinaba: double _ = 31.16931963781721; 9ce62cec1c 2015-03-26 kinaba: END 9ce62cec1c 2015-03-26 kinaba: CASE(5) 9ce62cec1c 2015-03-26 kinaba: int p_[] = {4, 3, 4, 3, 8, 2, 4, 3, 4, 4, 3, 2, 4, 4, 3, 4, 2, 4, 7, 6, 4, 4, 3, 4, 4, 3}; 9ce62cec1c 2015-03-26 kinaba: vector <int> p(p_, p_+sizeof(p_)/sizeof(*p_)); 9ce62cec1c 2015-03-26 kinaba: string s = "makigotapresentfromniko"; 9ce62cec1c 2015-03-26 kinaba: double _ = 23.0; 9ce62cec1c 2015-03-26 kinaba: END 9ce62cec1c 2015-03-26 kinaba: /* 9ce62cec1c 2015-03-26 kinaba: CASE(6) 9ce62cec1c 2015-03-26 kinaba: int p_[] = ; 9ce62cec1c 2015-03-26 kinaba: vector <int> p(p_, p_+sizeof(p_)/sizeof(*p_)); 9ce62cec1c 2015-03-26 kinaba: string s = ; 9ce62cec1c 2015-03-26 kinaba: double _ = ; 9ce62cec1c 2015-03-26 kinaba: END 9ce62cec1c 2015-03-26 kinaba: CASE(7) 9ce62cec1c 2015-03-26 kinaba: int p_[] = ; 9ce62cec1c 2015-03-26 kinaba: vector <int> p(p_, p_+sizeof(p_)/sizeof(*p_)); 9ce62cec1c 2015-03-26 kinaba: string s = ; 9ce62cec1c 2015-03-26 kinaba: double _ = ; 9ce62cec1c 2015-03-26 kinaba: END 9ce62cec1c 2015-03-26 kinaba: */ 9ce62cec1c 2015-03-26 kinaba: } 9ce62cec1c 2015-03-26 kinaba: // END CUT HERE