Overview
| SHA1 Hash: | 9149ebcfa28448810e32de528ce34716943802f9 |
|---|---|
| Date: | 2014-02-07 15:33:49 |
| User: | kinaba |
| Comment: | 607 |
| Timelines: | family | ancestors | descendants | both | trunk |
| Downloads: | Tarball | ZIP archive |
| Other Links: | files | file ages | manifest |
Tags And Properties
- branch=trunk inherited from [9165bd3629]
- sym-trunk inherited from [9165bd3629]
Changes
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) > 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 > 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() > 69 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 70 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 71 #define END verify_case(_, PalindromicSubstringsDiv1().expectedPalindromes( > 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() > 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( > 68 dp(i+1,mm,ppp) = min(dp(i+1,mm,ppp), dp( > 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) > 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 > 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() > 92 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 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","410 > 141 vector <string> P(P_, P_+sizeof(P_)/sizeof(*P_)); > 142 string Q_[] = {"26585546315429895673160149821124323624385723648950","931 > 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