9149ebcfa2 2014-02-07 kinaba: #include <iostream> 9149ebcfa2 2014-02-07 kinaba: #include <sstream> 9149ebcfa2 2014-02-07 kinaba: #include <iomanip> 9149ebcfa2 2014-02-07 kinaba: #include <vector> 9149ebcfa2 2014-02-07 kinaba: #include <string> 9149ebcfa2 2014-02-07 kinaba: #include <map> 9149ebcfa2 2014-02-07 kinaba: #include <set> 9149ebcfa2 2014-02-07 kinaba: #include <algorithm> 9149ebcfa2 2014-02-07 kinaba: #include <numeric> 9149ebcfa2 2014-02-07 kinaba: #include <iterator> 9149ebcfa2 2014-02-07 kinaba: #include <functional> 9149ebcfa2 2014-02-07 kinaba: #include <complex> 9149ebcfa2 2014-02-07 kinaba: #include <queue> 9149ebcfa2 2014-02-07 kinaba: #include <stack> 9149ebcfa2 2014-02-07 kinaba: #include <cmath> 9149ebcfa2 2014-02-07 kinaba: #include <cassert> 9149ebcfa2 2014-02-07 kinaba: #include <tuple> 9149ebcfa2 2014-02-07 kinaba: using namespace std; 9149ebcfa2 2014-02-07 kinaba: typedef long long LL; 9149ebcfa2 2014-02-07 kinaba: typedef complex<double> CMP; 9149ebcfa2 2014-02-07 kinaba: 9149ebcfa2 2014-02-07 kinaba: template<typename T> 9149ebcfa2 2014-02-07 kinaba: struct DP3 9149ebcfa2 2014-02-07 kinaba: { 9149ebcfa2 2014-02-07 kinaba: int N1, N2, N3; 9149ebcfa2 2014-02-07 kinaba: vector<T> data; 9149ebcfa2 2014-02-07 kinaba: DP3(int N1, int N2, int N3, const T& t = T()) 9149ebcfa2 2014-02-07 kinaba: : N1(N1), N2(N2), N3(N3), data(N1*N2*N3, t) { assert(data.size()*sizeof(T)<(1<<28)); } 9149ebcfa2 2014-02-07 kinaba: T& operator()(int i1, int i2, int i3) 9149ebcfa2 2014-02-07 kinaba: { return data[ ((i1*N2)+i2)*N3+i3 ]; } 9149ebcfa2 2014-02-07 kinaba: void swap(DP3& rhs) 9149ebcfa2 2014-02-07 kinaba: { data.swap(rhs.data); } 9149ebcfa2 2014-02-07 kinaba: }; 9149ebcfa2 2014-02-07 kinaba: 9149ebcfa2 2014-02-07 kinaba: class CombinationLockDiv1 { public: 9149ebcfa2 2014-02-07 kinaba: int minimumMoves(vector <string> P, vector <string> Q) 9149ebcfa2 2014-02-07 kinaba: { 9149ebcfa2 2014-02-07 kinaba: string S = accumulate(P.begin(), P.end(), string()); 9149ebcfa2 2014-02-07 kinaba: string T = accumulate(Q.begin(), Q.end(), string()); 9149ebcfa2 2014-02-07 kinaba: 9149ebcfa2 2014-02-07 kinaba: vector<int> U; 9149ebcfa2 2014-02-07 kinaba: for(int i=0; i<S.size(); ++i) 9149ebcfa2 2014-02-07 kinaba: U.push_back((T[i]-S[i]+10) % 10); 9149ebcfa2 2014-02-07 kinaba: return solve(U); 9149ebcfa2 2014-02-07 kinaba: } 9149ebcfa2 2014-02-07 kinaba: 9149ebcfa2 2014-02-07 kinaba: int solve(const vector<int>& U) 9149ebcfa2 2014-02-07 kinaba: { 9149ebcfa2 2014-02-07 kinaba: const int INF = 50*50*20; 9149ebcfa2 2014-02-07 kinaba: const int Q = 10; 9149ebcfa2 2014-02-07 kinaba: 9149ebcfa2 2014-02-07 kinaba: DP3<int> dp(U.size()+1, Q, Q, INF); 9149ebcfa2 2014-02-07 kinaba: dp(0,0,0) = 0; 9149ebcfa2 2014-02-07 kinaba: 9149ebcfa2 2014-02-07 kinaba: for(int i=0; i<U.size(); ++i) 9149ebcfa2 2014-02-07 kinaba: { 9149ebcfa2 2014-02-07 kinaba: for(int m=0; m<Q; ++m) 9149ebcfa2 2014-02-07 kinaba: for(int p=0; p<Q; ++p) 9149ebcfa2 2014-02-07 kinaba: { 9149ebcfa2 2014-02-07 kinaba: for(int mm=0; mm<=m; ++mm) 9149ebcfa2 2014-02-07 kinaba: for(int pp=0; pp<=p; ++pp) { 9149ebcfa2 2014-02-07 kinaba: int v = (pp-mm+10)%10; 9149ebcfa2 2014-02-07 kinaba: int dip = (U[i]-v+10)%10; 9149ebcfa2 2014-02-07 kinaba: int dim = (10-dip)%10; 9149ebcfa2 2014-02-07 kinaba: int mmm = min(dim+mm,Q-1); 9149ebcfa2 2014-02-07 kinaba: int ppp = min(dip+pp,Q-1); 9149ebcfa2 2014-02-07 kinaba: dp(i+1,mmm,pp) = min(dp(i+1,mmm,pp), dp(i,m,p) + dim); 9149ebcfa2 2014-02-07 kinaba: dp(i+1,mm,ppp) = min(dp(i+1,mm,ppp), dp(i,m,p) + dip); 9149ebcfa2 2014-02-07 kinaba: } 9149ebcfa2 2014-02-07 kinaba: } 9149ebcfa2 2014-02-07 kinaba: } 9149ebcfa2 2014-02-07 kinaba: 9149ebcfa2 2014-02-07 kinaba: int best = INF; 9149ebcfa2 2014-02-07 kinaba: for(int m=0; m<Q; ++m) 9149ebcfa2 2014-02-07 kinaba: for(int p=0; p<Q; ++p) 9149ebcfa2 2014-02-07 kinaba: best = min(best, dp(U.size(), m, p)); 9149ebcfa2 2014-02-07 kinaba: return best; 9149ebcfa2 2014-02-07 kinaba: } 9149ebcfa2 2014-02-07 kinaba: }; 9149ebcfa2 2014-02-07 kinaba: 9149ebcfa2 2014-02-07 kinaba: // BEGIN CUT HERE 9149ebcfa2 2014-02-07 kinaba: #include <ctime> 9149ebcfa2 2014-02-07 kinaba: double start_time; string timer() 9149ebcfa2 2014-02-07 kinaba: { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 9149ebcfa2 2014-02-07 kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 9149ebcfa2 2014-02-07 kinaba: { os << "{ "; 9149ebcfa2 2014-02-07 kinaba: for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 9149ebcfa2 2014-02-07 kinaba: os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 9149ebcfa2 2014-02-07 kinaba: void verify_case(const int& Expected, const int& Received) { 9149ebcfa2 2014-02-07 kinaba: bool ok = (Expected == Received); 9149ebcfa2 2014-02-07 kinaba: if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 9149ebcfa2 2014-02-07 kinaba: cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 9149ebcfa2 2014-02-07 kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 9149ebcfa2 2014-02-07 kinaba: #define END verify_case(_, CombinationLockDiv1().minimumMoves(P, Q));} 9149ebcfa2 2014-02-07 kinaba: int main(){ 9149ebcfa2 2014-02-07 kinaba: 9149ebcfa2 2014-02-07 kinaba: CASE(0) 9149ebcfa2 2014-02-07 kinaba: string P_[] = {"123"}; 9149ebcfa2 2014-02-07 kinaba: vector <string> P(P_, P_+sizeof(P_)/sizeof(*P_)); 9149ebcfa2 2014-02-07 kinaba: string Q_[] = {"112"}; 9149ebcfa2 2014-02-07 kinaba: vector <string> Q(Q_, Q_+sizeof(Q_)/sizeof(*Q_)); 9149ebcfa2 2014-02-07 kinaba: int _ = 1; 9149ebcfa2 2014-02-07 kinaba: END 9149ebcfa2 2014-02-07 kinaba: CASE(1) 9149ebcfa2 2014-02-07 kinaba: string P_[] = {"1"}; 9149ebcfa2 2014-02-07 kinaba: vector <string> P(P_, P_+sizeof(P_)/sizeof(*P_)); 9149ebcfa2 2014-02-07 kinaba: string Q_[] = {"7"}; 9149ebcfa2 2014-02-07 kinaba: vector <string> Q(Q_, Q_+sizeof(Q_)/sizeof(*Q_)); 9149ebcfa2 2014-02-07 kinaba: int _ = 4; 9149ebcfa2 2014-02-07 kinaba: END 9149ebcfa2 2014-02-07 kinaba: CASE(2) 9149ebcfa2 2014-02-07 kinaba: string P_[] = {"6","07"}; 9149ebcfa2 2014-02-07 kinaba: vector <string> P(P_, P_+sizeof(P_)/sizeof(*P_)); 9149ebcfa2 2014-02-07 kinaba: string Q_[] = {"","60","7"}; 9149ebcfa2 2014-02-07 kinaba: vector <string> Q(Q_, Q_+sizeof(Q_)/sizeof(*Q_)); 9149ebcfa2 2014-02-07 kinaba: int _ = 0; 9149ebcfa2 2014-02-07 kinaba: END 9149ebcfa2 2014-02-07 kinaba: CASE(3) 9149ebcfa2 2014-02-07 kinaba: string P_[] = {"1234"}; 9149ebcfa2 2014-02-07 kinaba: vector <string> P(P_, P_+sizeof(P_)/sizeof(*P_)); 9149ebcfa2 2014-02-07 kinaba: string Q_[] = {"4567"}; 9149ebcfa2 2014-02-07 kinaba: vector <string> Q(Q_, Q_+sizeof(Q_)/sizeof(*Q_)); 9149ebcfa2 2014-02-07 kinaba: int _ = 3; 9149ebcfa2 2014-02-07 kinaba: END 9149ebcfa2 2014-02-07 kinaba: CASE(4) 9149ebcfa2 2014-02-07 kinaba: string P_[] = {"020"}; 9149ebcfa2 2014-02-07 kinaba: vector <string> P(P_, P_+sizeof(P_)/sizeof(*P_)); 9149ebcfa2 2014-02-07 kinaba: string Q_[] = {"909"}; 9149ebcfa2 2014-02-07 kinaba: vector <string> Q(Q_, Q_+sizeof(Q_)/sizeof(*Q_)); 9149ebcfa2 2014-02-07 kinaba: int _ = 2; 9149ebcfa2 2014-02-07 kinaba: END 9149ebcfa2 2014-02-07 kinaba: CASE(5) 9149ebcfa2 2014-02-07 kinaba: string P_[] = {"4423232218340"}; 9149ebcfa2 2014-02-07 kinaba: vector <string> P(P_, P_+sizeof(P_)/sizeof(*P_)); 9149ebcfa2 2014-02-07 kinaba: string Q_[] = {"6290421476245"}; 9149ebcfa2 2014-02-07 kinaba: vector <string> Q(Q_, Q_+sizeof(Q_)/sizeof(*Q_)); 9149ebcfa2 2014-02-07 kinaba: int _ = 18; 9149ebcfa2 2014-02-07 kinaba: END 9149ebcfa2 2014-02-07 kinaba: CASE(6) 9149ebcfa2 2014-02-07 kinaba: 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"}; 9149ebcfa2 2014-02-07 kinaba: vector <string> P(P_, P_+sizeof(P_)/sizeof(*P_)); 9149ebcfa2 2014-02-07 kinaba: 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"}; 9149ebcfa2 2014-02-07 kinaba: 9149ebcfa2 2014-02-07 kinaba: vector <string> Q(Q_, Q_+sizeof(Q_)/sizeof(*Q_)); 9149ebcfa2 2014-02-07 kinaba: int _ = -1; 9149ebcfa2 2014-02-07 kinaba: END 9149ebcfa2 2014-02-07 kinaba: CASE(7) 9149ebcfa2 2014-02-07 kinaba: string P_[] = {"000000"}; 9149ebcfa2 2014-02-07 kinaba: vector <string> P(P_, P_+sizeof(P_)/sizeof(*P_)); 9149ebcfa2 2014-02-07 kinaba: string Q_[] = {"456789"}; 9149ebcfa2 2014-02-07 kinaba: vector <string> Q(Q_, Q_+sizeof(Q_)/sizeof(*Q_)); 9149ebcfa2 2014-02-07 kinaba: int _ = 6; 9149ebcfa2 2014-02-07 kinaba: END 9149ebcfa2 2014-02-07 kinaba: } 9149ebcfa2 2014-02-07 kinaba: // END CUT HERE