Overview
| SHA1 Hash: | 5749d4c594226221b96ca298456e7d5514a0d2f0 |
|---|---|
| Date: | 2012-07-09 10:37:14 |
| User: | kinaba |
| Comment: | tco12 3b |
| 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/TCO12-3B-U/1A.cpp version [8cb659246b1c63d7]
> 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 using namespace std; > 18 typedef long long LL; > 19 typedef long double LD; > 20 typedef complex<LD> CMP; > 21 > 22 class CrossingTheRiver { public: > 23 string isItEvenPossible(int waterWidth, int landWidth, vector <int> bloc > 24 { > 25 return solve(waterWidth, landWidth, blockHeight, depth) ? "POSSI > 26 } > 27 > 28 bool solve(int WW, int LW, vector<int> B, int D) > 29 { > 30 if( count(B.begin(), B.end(), D) >= WW ) > 31 return true; > 32 > 33 sort(B.begin(), B.end()); > 34 for(int lastW=D; lastW<=D+WW; ++lastW) > 35 for(int lastL=lastW-D; lastL<=lastW-D+LW; ++lastL) > 36 if( solve2(B, WW, D, lastW, LW, lastW-D, lastL) ) > 37 return true; > 38 return false; > 39 } > 40 > 41 bool solve2(vector<int> B, int WW, int W_min, int W_max, int LW, int L_m > 42 { > 43 for(int h=W_min+1; h<=W_max; ++h,--WW) > 44 if(!erase(B, h)) > 45 return false; > 46 for(int h=L_min+1; h<=L_max; ++h,--LW) > 47 if(!erase(B, h)) > 48 return false; > 49 > 50 int both = 0; > 51 for(int i=0; i<B.size(); ++i) > 52 if( W_min<=B[i] && B[i]<=W_max && L_min<=B[i] && B[i]<=L > 53 both++; > 54 else if( W_min<=B[i] && B[i]<=W_max ) > 55 --WW; > 56 else if( L_min<=B[i] && B[i]<=L_max ) > 57 --LW; > 58 return (max(WW,0)+max(LW,0) <= both); > 59 } > 60 > 61 bool erase(vector<int>& v, int n) > 62 { > 63 vector<int>::iterator it = find(v.begin(), v.end(), n); > 64 if( it == v.end() ) > 65 return false; > 66 v.erase(it); > 67 return true; > 68 } > 69 }; > 70 > 71 // BEGIN CUT HERE > 72 #include <ctime> > 73 double start_time; string timer() > 74 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 75 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 76 { os << "{ "; > 77 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 78 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 79 void verify_case(const string& Expected, const string& Received) { > 80 bool ok = (Expected == Received); > 81 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 82 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 83 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 84 #define END verify_case(_, CrossingTheRiver().isItEvenPossible(waterWidth, > 85 int main(){ > 86 > 87 CASE(0) > 88 int waterWidth = 3; > 89 int landWidth = 3; > 90 int blockHeight_[] = {3,4,4,5,5, 6}; > 91 vector <int> blockHeight(blockHeight_, blockHeight_+sizeof(blockHeight > 92 int depth = 2; > 93 string _ = "POSSIBLE"; > 94 END > 95 CASE(1) > 96 int waterWidth = 3; > 97 int landWidth = 3; > 98 int blockHeight_[] = {3,4,4,5,6, 6}; > 99 vector <int> blockHeight(blockHeight_, blockHeight_+sizeof(blockHeight > 100 int depth = 2; > 101 string _ = "IMPOSSIBLE"; > 102 END > 103 CASE(2) > 104 int waterWidth = 5; > 105 int landWidth = 2; > 106 int blockHeight_[] = {4,4,4,4,4}; > 107 vector <int> blockHeight(blockHeight_, blockHeight_+sizeof(blockHeight > 108 int depth = 4; > 109 string _ = "POSSIBLE"; > 110 END > 111 CASE(3) > 112 int waterWidth = 5; > 113 int landWidth = 5; > 114 int blockHeight_[] = {5,5,5,5,5,5, 2,3,4,4,6, 7, 3, 2}; > 115 vector <int> blockHeight(blockHeight_, blockHeight_+sizeof(blockHeight > 116 int depth = 2; > 117 string _ = "POSSIBLE"; > 118 END > 119 CASE(4) > 120 int waterWidth = 5; > 121 int landWidth = 7; > 122 int blockHeight_[] = {6,6,6,6,6,6,6, 6,6,6,6,6,7,8,9,10}; > 123 vector <int> blockHeight(blockHeight_, blockHeight_+sizeof(blockHeight > 124 int depth = 5; > 125 string _ = "POSSIBLE"; > 126 END > 127 CASE(5) > 128 int waterWidth = 1; > 129 int landWidth = 1; > 130 int blockHeight_[] = {5,3,4}; > 131 vector <int> blockHeight(blockHeight_, blockHeight_+sizeof(blockHeight > 132 int depth = 2; > 133 string _ = "IMPOSSIBLE"; > 134 END > 135 CASE(6) > 136 int waterWidth = 3; > 137 int landWidth = 1; > 138 int blockHeight_[] = {2, 3, 4, 5}; > 139 vector <int> blockHeight(blockHeight_, blockHeight_+sizeof(blockHeight > 140 int depth = 2; > 141 string _ = "IMPOSSIBLE"; > 142 END > 143 /* > 144 CASE(7) > 145 int waterWidth = ; > 146 int landWidth = ; > 147 int blockHeight_[] = ; > 148 vector <int> blockHeight(blockHeight_, blockHeight_+sizeof(blockHeight > 149 int depth = ; > 150 string _ = ; > 151 END > 152 */ > 153 } > 154 // END CUT HERE
Added SRM/TCO12-3B-U/1B-U.cpp version [c64847afba8ca911]
> 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 using namespace std; > 18 typedef long long LL; > 19 typedef long double LD; > 20 typedef complex<LD> CMP; > 21 > 22 static const int MODVAL = 1000000007; > 23 struct mint > 24 { > 25 int val; > 26 mint():val(0){} > 27 mint(int x):val(x%MODVAL) {} > 28 mint(size_t x):val(x%MODVAL) {} > 29 mint(LL x):val(x%MODVAL) {} > 30 }; > 31 mint& operator+=(mint& x, mint y) { return x = x.val+y.val; } > 32 mint& operator-=(mint& x, mint y) { return x = x.val-y.val+MODVAL; } > 33 mint& operator*=(mint& x, mint y) { return x = LL(x.val)*y.val; } > 34 mint POW(mint x, LL e) { mint v=1; for(;e;x*=x,e>>=1) if(e&1) v*=x; return v; } > 35 mint& operator/=(mint& x, mint y) { return x *= POW(y, MODVAL-2); } > 36 mint operator+(mint x, mint y) { return x+=y; } > 37 mint operator-(mint x, mint y) { return x-=y; } > 38 mint operator*(mint x, mint y) { return x*=y; } > 39 mint operator/(mint x, mint y) { return x/=y; } > 40 vector<mint> FAC_(1,1); > 41 mint FAC(LL n) { while( FAC_.size()<=n ) FAC_.push_back( FAC_.back()*FAC_.size() > 42 vector< vector<mint> > CP_; // Pascal's triangle: if O(1) nCk is needed. > 43 mint C(LL n, LL k) { > 44 while( CP_.size() <= n ) { > 45 int nn = CP_.size(); > 46 CP_.push_back(vector<mint>(nn+1,1)); > 47 for(int kk=1; kk<nn; ++kk) > 48 CP_[nn][kk] = CP_[nn-1][kk-1] + CP_[nn-1][kk]; > 49 } > 50 return k<0 || n<k ? 0 : CP_[n][k]; > 51 } > 52 > 53 template<typename T> > 54 struct DP3 > 55 { > 56 int N1, N2, N3; > 57 vector<T> data; > 58 DP3(int N1, int N2, int N3, const T& t = T()) > 59 : N1(N1), N2(N2), N3(N3), data(N1*N2*N3, t) { assert(data.size() > 60 T& operator()(int i1, int i2, int i3) > 61 { return data[ ((i1*N2)+i2)*N3+i3 ]; } > 62 void swap(DP3& rhs) > 63 { data.swap(rhs.data); } > 64 }; > 65 > 66 class ElevenMultiples { public: > 67 // (10^p)%11 > 68 int rem11(int p) > 69 { > 70 return p%2==0 ? 1 : 10; > 71 } > 72 > 73 int countMultiples(vector <string> pieces) > 74 { > 75 vector<int> es, os; > 76 for(int i=0; i<pieces.size(); ++i) { > 77 int r = 0; > 78 for(int k=0; k<pieces[i].size(); ++k) > 79 r = (r + (pieces[i][k]-'0')*rem11(k)) % 11; > 80 (pieces.size()%2==0 ? es : os).push_back(r); > 81 } > 82 return solve(es, os).val; > 83 } > 84 > 85 mint solve(const vector<int>& es, const vector<int>& os) > 86 { > 87 DP3<mint> dpE(es.size(), 11, es.size()+1); > 88 int rE = accumulate(es.begin(), es.end(), 0) % 11; > 89 for(int i=0; i<es.size(); ++i) > 90 for(int r=0; r<11; ++r) > 91 for(int n=0; n<=es.size(); ++n) > 92 { > 93 int v = es[i]; > 94 if(i==0) { > 95 if(r==0 && n==0 || r==v && n==1) > 96 dpE(i,r,n) = 1; > 97 } else { > 98 if(n>0) > 99 dpE(i,r,n) = dpE(i-1,r,n) + dpE(i-1, (r- > 100 else > 101 dpE(i,r,n) = dpE(i-1,r,n); > 102 } > 103 } > 104 DP3<mint> dpO(os.size(), 11, os.size()+1); > 105 int rO = accumulate(os.begin(), os.end(), 0) % 11; > 106 for(int i=0; i<os.size(); ++i) > 107 for(int r=0; r<11; ++r) > 108 for(int n=0; n<=os.size(); ++n) > 109 { > 110 int v = os[i]; > 111 if(i==0) { > 112 if(r==0 && n==0 || r==v && n==1) > 113 dpO(i,r,n) = 1; > 114 } else { > 115 if(n>0) > 116 dpO(i,r,n) = dpO(i-1,r,n) + dpO(i-1, (r- > 117 else > 118 dpO(i,r,n) = dpO(i-1,r,n); > 119 } > 120 } > 121 > 122 mint total = 0; > 123 for(int re=0; re<11; ++re) > 124 for(int ne=0; ne<=es.size(); ++ne) > 125 for(int ro=0; ro<11; ++ro) > 126 for(int no=0; no<=os.size(); ++no) > 127 { > 128 int re2 = (rE - re + 11)*10%11; > 129 int ne2 = es.size() - ne; > 130 int ro2 = (rO - ro + 11)*10%11; > 131 int no2 = os.size() - no; > 132 if((re + re2 + ro + ro2)%11 == 0) > 133 if( ne2+no2==0 || no>0 ) > 134 if(no==no2 || no==no2+1) { > 135 mint choice = (es.empty() ? re==0?1:0 : dpE(es.s > 136 * (os.empty() ? ro==0?1:0 : dpO(os.size( > 137 total += choice * cnt(ne, ne2, no, no2); > 138 } > 139 } > 140 return total; > 141 } > 142 > 143 mint cnt(int ne, int ne2, int no, int no2) > 144 { > 145 mint x = FAC(no) * FAC(no2); > 146 int nec = (no==no2 ? no+1 : no); > 147 int ne2c = no; > 148 return x * dist(nec, ne) * dist(ne2c, ne2); > 149 } > 150 > 151 mint dist(int n, int k) > 152 { > 153 return FAC(n) * C(n+k-1, k-1); > 154 } > 155 }; > 156 > 157 // BEGIN CUT HERE > 158 #include <ctime> > 159 double start_time; string timer() > 160 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 161 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 162 { os << "{ "; > 163 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 164 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 165 void verify_case(const int& Expected, const int& Received) { > 166 bool ok = (Expected == Received); > 167 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 168 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 169 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 170 #define END verify_case(_, ElevenMultiples().countMultiples(pieces));} > 171 int main(){ > 172 > 173 CASE(0) > 174 string pieces_[] = {"58", "2012", "123"}; > 175 vector <string> pieces(pieces_, pieces_+sizeof(pieces_)/sizeof(*pieces > 176 int _ = 2; > 177 END > 178 CASE(1) > 179 string pieces_[] = {"1", "1111", "1", "11"}; > 180 vector <string> pieces(pieces_, pieces_+sizeof(pieces_)/sizeof(*pieces > 181 int _ = 24; > 182 END > 183 CASE(2) > 184 string pieces_[] = {"43925486943738659795389387498953274"}; > 185 vector <string> pieces(pieces_, pieces_+sizeof(pieces_)/sizeof(*pieces > 186 int _ = 1; > 187 END > 188 CASE(3) > 189 string pieces_[] = {"983", "4654", "98", "3269", "861", "30981"}; > 190 vector <string> pieces(pieces_, pieces_+sizeof(pieces_)/sizeof(*pieces > 191 int _ = 96; > 192 END > 193 CASE(4) > 194 string pieces_[] = {"193", "8819", "40676", "97625892", "5719", "4551566 > 195 "93391", "942068", "506", "901150", "874", "895567", "7560480", "7427691", "7994 > 196 vector <string> pieces(pieces_, pieces_+sizeof(pieces_)/sizeof(*pieces > 197 int _ = 537147821; > 198 END > 199 CASE(5) > 200 string pieces_[] = {"687045939630", "997856158148599044", "2014910234712 > 201 "67925153345598920", "6960366756", "863413844386808834", "799302243562410012", " > 202 "8004606814733183", "19623906615609", "23859998326058162", "461385591582", "9261 > 203 "1569373294276", "318106951168934", "65389049931", "12791173342", "507877942026" > 204 "3947173045690", "472425746178910", "524552931853595", "40771812249667850232", " > 205 "28147819070", "797007158858587", "5716177008624223", "387565700495309324", "471 > 206 ; > 207 vector <string> pieces(pieces_, pieces_+sizeof(pieces_)/sizeof(*pieces > 208 int _ = 814880650; > 209 END > 210 /* > 211 CASE(6) > 212 string pieces_[] = ; > 213 vector <string> pieces(pieces_, pieces_+sizeof(pieces_)/sizeof(*pieces > 214 int _ = ; > 215 END > 216 CASE(7) > 217 string pieces_[] = ; > 218 vector <string> pieces(pieces_, pieces_+sizeof(pieces_)/sizeof(*pieces > 219 int _ = ; > 220 END > 221 */ > 222 } > 223 // END CUT HERE