Overview
| SHA1 Hash: | 2827f8702408d95110958f6b889a3ef0ab5f7d7e |
|---|---|
| Date: | 2014-01-21 11:16:39 |
| User: | kinaba |
| Comment: | 604 |
| 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/604-U/1A.cpp version [b81d85fd8b288dc7]
> 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 PowerOfThree { public: > 23 string ableToGet(int x_, int y_) > 24 { > 25 LL x=x_, y=y_; > 26 for(LL tk=1;; tk*=3) > 27 { > 28 if(x==0 && y==0) > 29 break; > 30 LL xr = ((x/tk)%3+3)%3; > 31 LL yr = ((y/tk)%3+3)%3; > 32 if(xr==1 && yr==0) x-=tk; > 33 else if(xr==2 && yr==0) x+=tk; > 34 else if(xr==0 && yr==1) y-=tk; > 35 else if(xr==0 && yr==2) y+=tk; > 36 else return "Impossible"; > 37 } > 38 return "Possible"; > 39 } > 40 }; > 41 > 42 // BEGIN CUT HERE > 43 #include <ctime> > 44 double start_time; string timer() > 45 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 46 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 47 { os << "{ "; > 48 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 49 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 50 void verify_case(const string& Expected, const string& Received) { > 51 bool ok = (Expected == Received); > 52 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 53 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 54 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 55 #define END verify_case(_, PowerOfThree().ableToGet(x, y));} > 56 int main(){ > 57 > 58 CASE(0) > 59 int x = 1; > 60 int y = 3; > 61 string _ = "Possible"; > 62 END > 63 CASE(1) > 64 int x = 0; > 65 int y = 2; > 66 string _ = "Possible"; > 67 END > 68 CASE(2) > 69 int x = 1; > 70 int y = 9; > 71 string _ = "Impossible"; > 72 END > 73 CASE(3) > 74 int x = 3; > 75 int y = 0; > 76 string _ = "Impossible"; > 77 END > 78 CASE(4) > 79 int x = 1; > 80 int y = 1; > 81 string _ = "Impossible"; > 82 END > 83 CASE(5) > 84 int x = -6890; > 85 int y = 18252; > 86 string _ = "Possible"; > 87 END > 88 CASE(6) > 89 int x = 1000000000; > 90 int y = -1000000000; > 91 string _ = "Impossible"; > 92 END > 93 CASE(7) > 94 int x = 0; > 95 int y = 0; > 96 string _ = "Possible"; > 97 END > 98 CASE(8) > 99 int x = 8; > 100 int y = 3; > 101 string _ = "P"; > 102 END > 103 CASE(9) > 104 // -3^0 - 3^1 - ... - 3^18 + 3^19 > 105 // NOTE: 3^19 = 1162261467 > 10^9 > 106 int x = 581130734; > 107 int y = 0; > 108 string _ = "P"; > 109 END > 110 } > 111 // END CUT HERE
Added SRM/604-U/1B-U.cpp version [72fa1058f372c23c]
> 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 DP2 > 24 { > 25 const int N1, N2; > 26 vector<T> data; > 27 DP2(int N1, int N2, const T& t = T()) > 28 : N1(N1), N2(N2), data(N1*N2, t) { assert(data.size()*sizeof(T)< > 29 T& operator()(int i1, int i2) > 30 { return data[ (i1*N2)+i2 ]; } > 31 void swap(DP2& rhs) > 32 { data.swap(rhs.data); } > 33 }; > 34 > 35 static const int INF = 0x3fffffff; > 36 class FoxConnection { public: > 37 int minimalDistance(vector <int> A, vector <int> B, string haveFox) > 38 { > 39 int N = haveFox.size(); > 40 vector<vector<int>> G(N); > 41 for(int i=0; i<A.size(); ++i) { > 42 int a = A[i] - 1; > 43 int b = B[i] - 1; > 44 G[a].push_back(b); > 45 G[b].push_back(a); > 46 } > 47 > 48 int best = INF; > 49 memo.resize(N+1, vector<vector<int>>(N)); > 50 ts_memo.resize(N+1, vector<int>(N, INF)); > 51 for(int root=0; root<N; ++root) { > 52 const vector<int>& L = rec(-1, root, G, haveFox); > 53 best = min(best, L[0]); > 54 } > 55 return best==INF ? 0 : best; > 56 } > 57 > 58 vector<vector<int>> ts_memo; > 59 int treeSize(int prev, int v, const vector<vector<int>>& G, const string > 60 { > 61 if(ts_memo[prev+1][v] != INF) > 62 return ts_memo[prev+1][v]; > 63 > 64 int ts = (haveFox[v]=='Y'); > 65 for(int u : G[v]) if(u != prev) > 66 ts += treeSize(v, u, G, haveFox); > 67 return ts_memo[prev+1][v] = ts; > 68 } > 69 > 70 vector<vector<vector<int>>> memo; > 71 const vector<int>& rec(int prev, int v, const vector<vector<int>>& G, co > 72 { > 73 if(!memo[prev+1][v].empty()) > 74 return memo[prev+1][v]; > 75 int N = G.size(); > 76 > 77 vector<const vector<int>*> children; > 78 for(int u : G[v]) if(u != prev) > 79 children.push_back(&rec(v,u,G,haveFox)); > 80 int Z = children.size(); > 81 > 82 DP2<int> dp(Z+1, N, INF); > 83 dp(0,0) = 0; > 84 for(int i=0; i<Z; ++i) > 85 { > 86 const vector<int>& ch = *children[i]; > 87 for(int t=0; t<N; ++t) > 88 for(int w=0; w<N; ++w) > 89 if(t+w<N) > 90 dp(i+1, t+w) = min(dp(i+1, t+w), dp(i,t) > 91 } > 92 > 93 const bool Y = (haveFox[v]=='Y'); > 94 vector<int>& L = memo[prev+1][v]; > 95 L.resize(N, INF); > 96 > 97 const int TS = treeSize(prev, v, G, haveFox); > 98 for(int i=0; i<N; ++i) > 99 { > 100 if(i == TS) > 101 L[i] = min(INF, TS + (Y ? dp(Z,TS-1) : dp(Z,TS)) > 102 else > 103 L[i] = min(INF, i + (Y ? dp(Z,i) : i+1<N ? dp(Z, > 104 } > 105 return L; > 106 } > 107 }; > 108 > 109 // BEGIN CUT HERE > 110 #include <ctime> > 111 double start_time; string timer() > 112 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 113 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 114 { os << "{ "; > 115 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 116 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 117 void verify_case(const int& Expected, const int& Received) { > 118 bool ok = (Expected == Received); > 119 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 120 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 121 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 122 #define END verify_case(_, FoxConnection().minimalDistance(A, B, haveFox)); > 123 int main(){ > 124 > 125 CASE(0) > 126 int A_[] = {1,2,3}; > 127 vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_)); > 128 int B_[] = {2,3,4}; > 129 vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); > 130 string haveFox = "YNNY"; > 131 int _ = 2; > 132 END > 133 CASE(1) > 134 int A_[] = {1,1,1,1}; > 135 vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_)); > 136 int B_[] = {2,3,4,5}; > 137 vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); > 138 string haveFox = "NYYYY"; > 139 int _ = 1; > 140 END > 141 CASE(2) > 142 int A_[] = {1,3,4,5,4}; > 143 vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_)); > 144 int B_[] = {2,2,2,4,6}; > 145 vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); > 146 string haveFox = "YNYNYY"; > 147 int _ = 2; > 148 END > 149 CASE(3) > 150 int A_[] = {1,2,3,4,5,6,7,8,9}; > 151 vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_)); > 152 int B_[] = {2,3,4,5,6,7,8,9,10}; > 153 vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); > 154 string haveFox = "YNNNYNYNNY"; > 155 int _ = 7; > 156 END > 157 CASE(4) > 158 int A_[] = {1,2,3,4,3,6,8,7}; > 159 vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_)); > 160 int B_[] = {2,3,4,5,6,8,9,6}; > 161 vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); > 162 string haveFox = "YNNYYNYYY"; > 163 int _ = 3; > 164 END > 165 CASE(5) > 166 int A_[] = {1}; > 167 vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_)); > 168 int B_[] = {2}; > 169 vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); > 170 string haveFox = "NY"; > 171 int _ = 0; > 172 END > 173 CASE(6) > 174 int A_[] = {1}; > 175 vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_)); > 176 int B_[] = {2}; > 177 vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); > 178 string haveFox = "NN"; > 179 int _ = 0; > 180 END > 181 /* > 182 CASE(7) > 183 int A_[] = ; > 184 vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_)); > 185 int B_[] = ; > 186 vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); > 187 string haveFox = ; > 188 int _ = ; > 189 END > 190 CASE(8) > 191 int A_[] = ; > 192 vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_)); > 193 int B_[] = ; > 194 vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); > 195 string haveFox = ; > 196 int _ = ; > 197 END > 198 */ > 199 } > 200 // END CUT HERE