• branch=trunk inherited from [9165bd3629]
• sym-trunk inherited from [9165bd3629]

Added SRM/607-U/1A.cpp version [db310718265ebf13]

            1  +#include <iostream>
            2  +#include <sstream>
            3  +#include <iomanip>
            4  +#include <vector>
            5  +#include <string>
            6  +#include <map>
            7  +#include <set>
            8  +#include <algorithm>
            9  +#include <numeric>
           10  +#include <iterator>
           11  +#include <functional>
           12  +#include <complex>
           13  +#include <queue>
           14  +#include <stack>
           15  +#include <cmath>
           16  +#include <cassert>
           17  +#include <tuple>
           18  +using namespace std;
           19  +typedef long long LL;
           20  +typedef complex<double> CMP;
           21  +
           22  +class PalindromicSubstringsDiv1 { public:
           23  + double expectedPalindromes(vector <string> S1, vector <string> S2)
           24  + {
           25  +  string A = accumulate(S1.begin(), S1.end(), string());
           26  +  string B = accumulate(S2.begin(), S2.end(), string());
           27  +  string S = A + B;
           28  +  return solve(S, S.size());
           29  + }
           30  +
           31  + double solve(const string& S, int N)
           32  + {
           33  +  double e = 0.0;
           34  +  for(int c=0; c<N; ++c)
           35  +  {
           36  +   // odd
           37  +   double p = 1.0;
           38  +   e += p;  // single-letter case
           39  +   for(int x=1; c-x>=0 && c+x<N; ++x)
           40  +   {
           41  +    if(S[c-x]=='?' || S[c+x]=='?') p*=1/26.0;
           42  +    else if(S[c-x] != S[c+x]) p=0;
           43  +    e += p;
           44  +   }
           45  +   // even
           46  +   p = 1.0;
           47  +   for(int x=1; c-x>=0 && c+x-1<N; ++x)
           48  +   {
           49  +    if(S[c-x]=='?' || S[c+x-1]=='?') p*=1/26.0;
           50  +    else if(S[c-x] != S[c+x-1]) p=0;
           51  +    e += p;
           52  +   }
           53  +  }
           54  +  return e;
           55  + }
           56  +};
           57  +
           58  +// BEGIN CUT HERE
           59  +#include <ctime>
           60  +double start_time; string timer()
           61  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           62  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           63  + { os << "{ ";
           64  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           65  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           66  +void verify_case(const double& Expected, const double& Received) {
           67  + bool ok = (abs(Expected - Received) < 1e-9);
           68  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           69  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           70  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           71  +#define END  verify_case(_, PalindromicSubstringsDiv1().expectedPalindromes(S1, S2));}
           72  +int main(){
           73  +
           74  +CASE(0)
           75  + string S1_[] = {"a","a",""};
           76  +   vector <string> S1(S1_, S1_+sizeof(S1_)/sizeof(*S1_));
           77  + string S2_[] = {"a"};
           78  +   vector <string> S2(S2_, S2_+sizeof(S2_)/sizeof(*S2_));
           79  + double _ = 6.0;
           80  +END
           81  +CASE(1)
           82  + string S1_[] = {"z??"};
           83  +   vector <string> S1(S1_, S1_+sizeof(S1_)/sizeof(*S1_));
           84  + vector <string> S2;
           85  + double _ = 3.115384615384615;
           86  +END
           87  +CASE(2)
           88  + string S1_[] = {"ab","c"};
           89  +   vector <string> S1(S1_, S1_+sizeof(S1_)/sizeof(*S1_));
           90  + string S2_[] = {"??","a?"};
           91  +   vector <string> S2(S2_, S2_+sizeof(S2_)/sizeof(*S2_));
           92  + double _ = 7.315088757396449;
           93  +END
           94  +CASE(3)
           95  + vector <string> S1;
           96  + string S2_[] = {"?"};
           97  +   vector <string> S2(S2_, S2_+sizeof(S2_)/sizeof(*S2_));
           98  + double _ = 1.0;
           99  +END
          100  +CASE(4)
          101  + string S1_[] = {"ab?def","?"};
          102  +   vector <string> S1(S1_, S1_+sizeof(S1_)/sizeof(*S1_));
          103  + string S2_[] = {"f??a"};
          104  +   vector <string> S2(S2_, S2_+sizeof(S2_)/sizeof(*S2_));
          105  + double _ = 12.545971779699588;
          106  +END
          107  +/*
          108  +CASE(5)
          109  + string S1_[] = ;
          110  +   vector <string> S1(S1_, S1_+sizeof(S1_)/sizeof(*S1_));
          111  + string S2_[] = ;
          112  +   vector <string> S2(S2_, S2_+sizeof(S2_)/sizeof(*S2_));
          113  + double _ = ;
          114  +END
          115  +CASE(6)
          116  + string S1_[] = ;
          117  +   vector <string> S1(S1_, S1_+sizeof(S1_)/sizeof(*S1_));
          118  + string S2_[] = ;
          119  +   vector <string> S2(S2_, S2_+sizeof(S2_)/sizeof(*S2_));
          120  + double _ = ;
          121  +END
          122  +*/
          123  +}
          124  +// END CUT HERE

Added SRM/607-U/1B-U.cpp version [d0b030fe982e4c92]

            1  +#include <iostream>
            2  +#include <sstream>
            3  +#include <iomanip>
            4  +#include <vector>
            5  +#include <string>
            6  +#include <map>
            7  +#include <set>
            8  +#include <algorithm>
            9  +#include <numeric>
           10  +#include <iterator>
           11  +#include <functional>
           12  +#include <complex>
           13  +#include <queue>
           14  +#include <stack>
           15  +#include <cmath>
           16  +#include <cassert>
           17  +#include <tuple>
           18  +using namespace std;
           19  +typedef long long LL;
           20  +typedef complex<double> CMP;
           21  +
           22  +template<typename T>
           23  +struct DP3
           24  +{
           25  + int N1, N2, N3;
           26  + vector<T> data;
           27  + DP3(int N1, int N2, int N3, const T& t = T())
           28  +  : N1(N1), N2(N2), N3(N3), data(N1*N2*N3, t) { assert(data.size()*sizeof(T)<(1<<28)); }
           29  + T& operator()(int i1, int i2, int i3)
           30  +  { return data[ ((i1*N2)+i2)*N3+i3 ]; }
           31  + void swap(DP3& rhs)
           32  +  { data.swap(rhs.data); }
           33  +};
           34  +
           35  +class CombinationLockDiv1 { public:
           36  + int minimumMoves(vector <string> P, vector <string> Q)
           37  + {
           38  +  string S = accumulate(P.begin(), P.end(), string());
           39  +  string T = accumulate(Q.begin(), Q.end(), string());
           40  +
           41  +  vector<int> U;
           42  +  for(int i=0; i<S.size(); ++i)
           43  +   U.push_back((T[i]-S[i]+10) % 10);
           44  +  return solve(U);
           45  + }
           46  +
           47  + int solve(const vector<int>& U)
           48  + {
           49  +  const int INF = 50*50*20;
           50  +  const int Q = 10;
           51  +
           52  +  DP3<int> dp(U.size()+1, Q, Q, INF);
           53  +  dp(0,0,0) = 0;
           54  +
           55  +  for(int i=0; i<U.size(); ++i)
           56  +  {
           57  +   for(int m=0; m<Q; ++m)
           58  +   for(int p=0; p<Q; ++p)
           59  +   {
           60  +    for(int mm=0; mm<=m; ++mm)
           61  +    for(int pp=0; pp<=p; ++pp) {
           62  +     int v = (pp-mm+10)%10;
           63  +     int dip = (U[i]-v+10)%10;
           64  +     int dim = (10-dip)%10;
           65  +     int mmm = min(dim+mm,Q-1);
           66  +     int ppp = min(dip+pp,Q-1);
           67  +     dp(i+1,mmm,pp) = min(dp(i+1,mmm,pp), dp(i,m,p) + dim);
           68  +     dp(i+1,mm,ppp) = min(dp(i+1,mm,ppp), dp(i,m,p) + dip);
           69  +    }
           70  +   }
           71  +  }
           72  +
           73  +  int best = INF;
           74  +  for(int m=0; m<Q; ++m)
           75  +  for(int p=0; p<Q; ++p)
           76  +   best = min(best, dp(U.size(), m, p));
           77  +  return best;
           78  + }
           79  +};
           80  +
           81  +// BEGIN CUT HERE
           82  +#include <ctime>
           83  +double start_time; string timer()
           84  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           85  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           86  + { os << "{ ";
           87  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           88  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           89  +void verify_case(const int& Expected, const int& Received) {
           90  + bool ok = (Expected == Received);
           91  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           92  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           93  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           94  +#define END  verify_case(_, CombinationLockDiv1().minimumMoves(P, Q));}
           95  +int main(){
           96  +
           97  +CASE(0)
           98  + string P_[] = {"123"};
           99  +   vector <string> P(P_, P_+sizeof(P_)/sizeof(*P_));
          100  + string Q_[] = {"112"};
          101  +   vector <string> Q(Q_, Q_+sizeof(Q_)/sizeof(*Q_));
          102  + int _ = 1;
          103  +END
          104  +CASE(1)
          105  + string P_[] = {"1"};
          106  +   vector <string> P(P_, P_+sizeof(P_)/sizeof(*P_));
          107  + string Q_[] = {"7"};
          108  +   vector <string> Q(Q_, Q_+sizeof(Q_)/sizeof(*Q_));
          109  + int _ = 4;
          110  +END
          111  +CASE(2)
          112  + string P_[] = {"6","07"};
          113  +   vector <string> P(P_, P_+sizeof(P_)/sizeof(*P_));
          114  + string Q_[] = {"","60","7"};
          115  +   vector <string> Q(Q_, Q_+sizeof(Q_)/sizeof(*Q_));
          116  + int _ = 0;
          117  +END
          118  +CASE(3)
          119  + string P_[] = {"1234"};
          120  +   vector <string> P(P_, P_+sizeof(P_)/sizeof(*P_));
          121  + string Q_[] = {"4567"};
          122  +   vector <string> Q(Q_, Q_+sizeof(Q_)/sizeof(*Q_));
          123  + int _ = 3;
          124  +END
          125  +CASE(4)
          126  + string P_[] = {"020"};
          127  +   vector <string> P(P_, P_+sizeof(P_)/sizeof(*P_));
          128  + string Q_[] = {"909"};
          129  +   vector <string> Q(Q_, Q_+sizeof(Q_)/sizeof(*Q_));
          130  + int _ = 2;
          131  +END
          132  +CASE(5)
          133  + string P_[] = {"4423232218340"};
          134  +   vector <string> P(P_, P_+sizeof(P_)/sizeof(*P_));
          135  + string Q_[] = {"6290421476245"};
          136  +   vector <string> Q(Q_, Q_+sizeof(Q_)/sizeof(*Q_));
          137  + int _ = 18;
          138  +END
          139  +CASE(6)
          140  + string P_[] = {"13582011523174667280008414541351904422031012238076","41048335045579967968275673754522871011068601257039","04855357969852282416624125536962426385082554121889","78074757536331862021838625347095667990535948893888","05579320225639822730235008835013806387280549085691","80899386988536534438059318016416835580192334813917","95341464766162715473052668803298477731786141378744","69816239602790838593717476180717906897243175749123","24738439366743704835924900681247874798806208147751","45337850860527204796077538037584119110987495462956","19109623542297344993947313914964412516346367095244","96248289645824455435790136083954599263965549130880","58401114021732043302864235558929780726578985430340","14418544383945031017494746702943514243376501190225","66249685629466035559385559250659296957755747196013","04785111927450904580203778222015365726498982699825","15269688063687053428204228967590278365731589445556","52836901795992325405969222392137556237720751803897","73917282470183746697363519879638377830810448700972","48931852957642664180697841772815067658315516508820","28656501252849429602603172562329240976023161940826","37156083646002750183572507124427592539716213493097","48063714185666861796912908924538985163177952016299","52773362719445635074535987829747253807426846754632","58904953136889913785986347937686998493070883951354","16945161728053635470076872669538849220363955440232","01316771478426257681554570729231953678202745236445","80547194249309162089697847348429235299584464070011","48909217233221310233477898131778996139508912874381","57165921870900700928516353466840515863348321007080","03199380285346276716385704233782058602186477541273","57629586195572946196250765990226852191103936041714","53446459026412049802639693633102627103026448385312","10449560544606230079321830630030549315203948785881","78865644328326729238917398515310302163206950711046","93807876100811118037712483047336372657089771808462","95924064423619365461974775778936847567532168396539","30934522552730239320804167555179733248719500179913","92449062520683014513899530376735799931693464212672","18439075607384060207916758028210747792158690034945","67550046930243544877782111951966692512319844028670","60767792508462968711880673532076795668800379421487","78121092917010361170954018211894626946083703760055","49667352485242602855643266038304470530983154846508","15168929880962349141948246852672003537639087309111","29037544243698149476895123319828479381872954148263","93686919265019496323833587775066697795417518561622","54995834325316496397379891082659236727599918638569","04499269120952438849149871831661730991764176812547","79371457213323740197817329649628939319568091637705"};
          141  +   vector <string> P(P_, P_+sizeof(P_)/sizeof(*P_));
          142  + string Q_[] = {"26585546315429895673160149821124323624385723648950","93145975424958492531929386719584878797847740043845","95701479323952655390238230967385653534124002661507","23983653758767357093823783993402052207751233494459","98711583090998839780395749138443275449931653742603","61293167602041603340392289107485524474795134870395","74512418862972537528310814463762318220469210316020","03358080324524140549537033852110007943188267480443","31646977753094077695930166382158316905727440462903","11002846107507123033068113706085961508369204903779","99741245890202804099741453386497577761969504241049","47836160882024796482460880683993868569526410623646","96107764672367326319737218357764159082400331128350","36961091275709970680500985451120241946922775875678","88397008935577205128749102059410926508484539966798","80534906503785197224539831265662419380733454092957","09475003340691062577096422764671636498967245119340","50433401131294882868176859626470398871396863774112","13802400129313166669538277217316956804639201622263","17257081790858760560971773120609978519424690526864","18019455769163702271286521059595276090770258883368","60351517055058669406347326556613386863411274223935","31394694251586651119602376269072383189130168471397","64862905602117845471790840660568880992748206616344","03722072134979404818149642072110006125367213097061","56890392458412031324407801718803651830274463787651","02604877724543786395576787946929929240596339245669","42373529984023882276028307690922789630695888449704","58231765898533664834822889266470284277354443339763","97209446654486428990686495351862368409922596851015","89749090720796049484610991644351923011565368078007","12740957679811435790969770507372742994884543250962","61607759784379577542186922781270084740937911060159","51864665482708227453841279720353622438748574669914","37976869128043879687016809498880435159399942579534","61200345600233010939778430702655952933023559483785","52956567802930503732745175189074850180362655567605","62376327002164238083885086706807442475301676912314","16570236775930283353485612619103181529970843080790","79555154762437866313663093223224491840166126405296","09352082575345052392287259550484807145788077671444","59554166683997533509509207485780871667325264585949","98764945336111968229089144120495247293714158297736","13309148762592847300050367505355443271678493638940","16190173208191757395742636058696599858531306877468","11441600207487016269710089937177986280975584413878","46684067545737865090159099578555995856800545435052","28369570052939976082383431980352736051623861461400","28591566192943839521108624118212754637294867570363","47161056270197028192623737725828173240010898334910"};
          143  +
          144  +   vector <string> Q(Q_, Q_+sizeof(Q_)/sizeof(*Q_));
          145  + int _ = -1;
          146  +END
          147  +CASE(7)
          148  + string P_[] = {"000000"};
          149  +   vector <string> P(P_, P_+sizeof(P_)/sizeof(*P_));
          150  + string Q_[] = {"456789"};
          151  +   vector <string> Q(Q_, Q_+sizeof(Q_)/sizeof(*Q_));
          152  + int _ = 6;
          153  +END
          154  +}
          155  +// END CUT HERE