Overview
| SHA1 Hash: | aae12c19ff296b4e06e89a684ac0f2ffd9d57af0 |
|---|---|
| Date: | 2015-07-23 12:48:32 |
| User: | kinaba |
| Comment: | TCO15-2C |
| 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
Name change from from SRM/TCO15-2B/1A.cpp to SRM/TCO15-2B-U/1A.cpp.
Name change from from SRM/TCO15-2B/1B.cpp to SRM/TCO15-2B-U/1B.cpp.
Deleted SRM/TCO15-2B/1A.cpp version [f77c6b1cfc679969]
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 Bitwisdom { public: < 23 double expectedActions(vector <int> p) < 24 { < 25 double e = 0; < 26 for(int i=1; i<p.size(); ++i) { < 27 e += (p[i]/100.0) * (100-p[i-1])/100.0 < 28 + (p[i-1]/100.0) * (100-p[i])/100.0; < 29 } < 30 double q = 1.0; < 31 for(int i=0; i<p.size(); ++i) < 32 q *= (p[i]/100.0); < 33 return e + q; < 34 } < 35 }; < 36 < 37 // BEGIN CUT HERE < 38 #include <ctime> < 39 double start_time; string timer() < 40 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) < 41 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) < 42 { os << "{ "; < 43 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) < 44 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return < 45 void verify_case(const double& Expected, const double& Received) { < 46 bool ok = (abs(Expected - Received) < 1e-9); < 47 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() < 48 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' < 49 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( < 50 #define END verify_case(_, Bitwisdom().expectedActions(p));} < 51 int main(){ < 52 < 53 CASE(0) < 54 int p_[] = {100, 100, 100}; < 55 vector <int> p(p_, p_+sizeof(p_)/sizeof(*p_)); < 56 double _ = 1.0; < 57 END < 58 CASE(1) < 59 int p_[] = {50, 50}; < 60 vector <int> p(p_, p_+sizeof(p_)/sizeof(*p_)); < 61 double _ = 0.75; < 62 END < 63 CASE(2) < 64 int p_[] = {0, 40, 50, 60}; < 65 vector <int> p(p_, p_+sizeof(p_)/sizeof(*p_)); < 66 double _ = 1.4; < 67 END < 68 CASE(3) < 69 int p_[] = {37, 63, 23, 94, 12}; < 70 vector <int> p(p_, p_+sizeof(p_)/sizeof(*p_)); < 71 double _ = 2.6820475464; < 72 END < 73 /* < 74 CASE(4) < 75 int p_[] = ; < 76 vector <int> p(p_, p_+sizeof(p_)/sizeof(*p_)); < 77 double _ = ; < 78 END < 79 CASE(5) < 80 int p_[] = ; < 81 vector <int> p(p_, p_+sizeof(p_)/sizeof(*p_)); < 82 double _ = ; < 83 END < 84 */ < 85 } < 86 // END CUT HERE <
Deleted SRM/TCO15-2B/1B.cpp version [1948580a37893b4c]
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 Balance { public: < 23 string canTransform(vector <string> initial, vector <string> target) < 24 { < 25 auto ti = gen_tree(initial); < 26 auto tt = gen_tree(target); < 27 return tree_eq(ti, tt) ? "Possible" : "Impossible"; < 28 } < 29 < 30 vector<vector<int>> gen_tree(vector<string> s) { < 31 s.push_back(string(s[0].size(), '#')); < 32 s.insert(s.begin(), string(s[0].size(), '#')); < 33 for(auto& si: s) < 34 si = '#'+si+'#'; < 35 < 36 const int H = s.size(), W = s[0].size(); < 37 const int NOTYET = 0x7fffffff; < 38 < 39 vector<vector<int>> tree; < 40 vector<vector<int>> parent_cand(H, vector<int>(W, -1)); < 41 vector<vector<int>> color(H, vector<int>(W, NOTYET)); < 42 for(int y=0; y<H; ++y) < 43 for(int x=0; x<W; ++x) < 44 if(color[y][x]==NOTYET) { < 45 const char ME = s[y][x]; < 46 int newId = tree.size(); < 47 tree.resize(newId+1); < 48 < 49 // BFS < 50 set<int> tonari; < 51 < 52 queue<pair<int,int>> Q; < 53 color[y][x] = newId; < 54 Q.emplace(y, x); < 55 while(!Q.empty()) { < 56 int yy = Q.front().first; < 57 int xx = Q.front().second; < 58 Q.pop(); < 59 < 60 int dx[] = {-1,+1,0,0}; < 61 int dy[] = {0,0,-1,+1}; < 62 for(int d=0; d<4; ++d) { < 63 int y2 = yy+dy[d]; < 64 int x2 = xx+dx[d]; < 65 if(0<=x2&&x2<W&&0<=y2&&y2<H) { < 66 if(s[y2][x2]==ME&&color[y2][x2]= < 67 color[y2][x2] = newId; < 68 Q.emplace(y2, x2); < 69 } < 70 if(s[y2][x2]!=ME&&color[y2][x2]! < 71 tonari.insert(color[y2][ < 72 } < 73 } < 74 } < 75 } < 76 if(tonari.size() == 1) < 77 tree[*tonari.begin()].push_back(newId); < 78 } < 79 return tree; < 80 } < 81 < 82 map<vector<int>, int> hashId; < 83 bool tree_eq(const vector<vector<int>>& a, const vector<vector<int>>& b) < 84 { < 85 return hash(a,0) == hash(b,0); < 86 } < 87 < 88 int hash(const vector<vector<int>>& a, int r) < 89 { < 90 vector<int> ch; < 91 for(int v: a[r]) < 92 ch.push_back(hash(a, v)); < 93 sort(ch.begin(), ch.end()); < 94 if(hashId.count(ch)) < 95 return hashId[ch]; < 96 int v = hashId.size(); < 97 return hashId[ch] = v; < 98 } < 99 }; < 100 < 101 // BEGIN CUT HERE < 102 #include <ctime> < 103 double start_time; string timer() < 104 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) < 105 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) < 106 { os << "{ "; < 107 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) < 108 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return < 109 void verify_case(const string& Expected, const string& Received) { < 110 bool ok = (Expected == Received); < 111 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() < 112 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' < 113 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( < 114 #define END verify_case(_, Balance().canTransform(initial, target));} < 115 int main(){ < 116 < 117 CASE(0) < 118 string initial_[] = {"#"}; < 119 vector <string> initial(initial_, initial_+sizeof(initial_)/sizeof(*in < 120 string target_[] = {"."}; < 121 vector <string> target(target_, target_+sizeof(target_)/sizeof(*target < 122 string _ = "Impossible"; < 123 END < 124 CASE(1) < 125 string initial_[] = {"..", < 126 ".."}; < 127 vector <string> initial(initial_, initial_+sizeof(initial_)/sizeof(*in < 128 string target_[] = {".#", < 129 "##"}; < 130 vector <string> target(target_, target_+sizeof(target_)/sizeof(*target < 131 string _ = "Possible"; < 132 END < 133 CASE(2) < 134 string initial_[] = {"...", < 135 ".#.", < 136 "..."}; < 137 vector <string> initial(initial_, initial_+sizeof(initial_)/sizeof(*in < 138 string target_[] = {"###", < 139 "#.#", < 140 "###"}; < 141 vector <string> target(target_, target_+sizeof(target_)/sizeof(*target < 142 string _ = "Impossible"; < 143 END < 144 CASE(3) < 145 string initial_[] = {".#.#.......", < 146 "####.###...", < 147 ".....####..", < 148 "..##.#.##.#", < 149 ".##..#.##.#", < 150 ".#######...", < 151 ".#....###.#", < 152 ".##.#.#....", < 153 "..#...#...#", < 154 "..#####...#", < 155 "..........."}; < 156 vector <string> initial(initial_, initial_+sizeof(initial_)/sizeof(*in < 157 string target_[] = {"...........", < 158 ".###....#..", < 159 ".#.#..#....", < 160 ".###.......", < 161 ".#####.....", < 162 ".#...#####.", < 163 ".#.#.....#.", < 164 ".#.#####.#.", < 165 ".#.......#.", < 166 ".#########.", < 167 "..........."}; < 168 vector <string> target(target_, target_+sizeof(target_)/sizeof(*target < 169 string _ = "Impossible"; < 170 END < 171 CASE(4) < 172 string initial_[] = {".....", < 173 ".###.", < 174 ".....", < 175 ".###.", < 176 "....."}; < 177 vector <string> initial(initial_, initial_+sizeof(initial_)/sizeof(*in < 178 string target_[] = {".....", < 179 ".#.#.", < 180 ".#.#.", < 181 ".#.#.", < 182 "....."}; < 183 vector <string> target(target_, target_+sizeof(target_)/sizeof(*target < 184 string _ = "Possible"; < 185 END < 186 /* < 187 CASE(5) < 188 string initial_[] = ; < 189 vector <string> initial(initial_, initial_+sizeof(initial_)/sizeof(*in < 190 string target_[] = ; < 191 vector <string> target(target_, target_+sizeof(target_)/sizeof(*target < 192 string _ = ; < 193 END < 194 CASE(6) < 195 string initial_[] = ; < 196 vector <string> initial(initial_, initial_+sizeof(initial_)/sizeof(*in < 197 string target_[] = ; < 198 vector <string> target(target_, target_+sizeof(target_)/sizeof(*target < 199 string _ = ; < 200 END < 201 */ < 202 < 203 } < 204 // END CUT HERE <
Added SRM/TCO15-2C-U/1A.cpp version [d9b27fe6bd32c9ac]
> 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 YetAnotherCardGame { public: > 23 int maxCards(vector <int> petr, vector <int> snuke) > 24 { > 25 sort(petr.begin(), petr.end()); > 26 sort(snuke.begin(), snuke.end()); > 27 > 28 return rec(&petr, &snuke, 0, 0, 0, 0, 0); > 29 } > 30 > 31 map<tuple<int,int,int,int,int>,int> memo; > 32 int rec(const vector<int>* me, const vector<int>* you, > 33 int turn, int m_next, int y_next, int m_musteat, int y_musteat) > 34 { > 35 if(m_musteat>=0 && m_next+m_musteat==me->size()) > 36 return 0; > 37 > 38 tuple<int,int,int,int,int> key(turn,m_next,y_next,m_musteat,y_mu > 39 if(memo.count(key)) > 40 return memo[key]; > 41 > 42 // eat > 43 int best = rec(you,me,turn^1,y_next,m_next,y_musteat,m_musteat+1 > 44 > 45 // play > 46 if(m_next < me->size()) { > 47 int v = (*me)[m_next]; > 48 m_next++; > 49 while(m_next<me->size() && (*me)[m_next]<=v) > 50 m_next++, m_musteat--; > 51 while(y_next<you->size() && (*you)[y_next]<=v) > 52 y_next++, y_musteat--; > 53 best = max(best, 1+rec(you,me,turn^1,y_next,m_next,y_mus > 54 } > 55 > 56 return memo[key] = best; > 57 } > 58 }; > 59 > 60 // BEGIN CUT HERE > 61 #include <ctime> > 62 double start_time; string timer() > 63 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 64 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 65 { os << "{ "; > 66 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 67 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 68 void verify_case(const int& Expected, const int& Received) { > 69 bool ok = (Expected == Received); > 70 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 71 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 72 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 73 #define END verify_case(_, YetAnotherCardGame().maxCards(petr, snuke));} > 74 int main(){ > 75 > 76 CASE(0) > 77 int petr_[] = {2, 5}; > 78 vector <int> petr(petr_, petr_+sizeof(petr_)/sizeof(*petr_)); > 79 int snuke_[] = {3, 1}; > 80 vector <int> snuke(snuke_, snuke_+sizeof(snuke_)/sizeof(*snuke_)); > 81 int _ = 3; > 82 END > 83 CASE(1) > 84 int petr_[] = {1, 1, 1, 1, 1}; > 85 vector <int> petr(petr_, petr_+sizeof(petr_)/sizeof(*petr_)); > 86 int snuke_[] = {1, 1, 1, 1, 1}; > 87 vector <int> snuke(snuke_, snuke_+sizeof(snuke_)/sizeof(*snuke_)); > 88 int _ = 1; > 89 END > 90 CASE(2) > 91 int petr_[] = {1, 4, 6, 7, 3}; > 92 vector <int> petr(petr_, petr_+sizeof(petr_)/sizeof(*petr_)); > 93 int snuke_[] = {1, 7, 1, 5, 7}; > 94 vector <int> snuke(snuke_, snuke_+sizeof(snuke_)/sizeof(*snuke_)); > 95 int _ = 6; > 96 END > 97 CASE(3) > 98 int petr_[] = {19, 99, 86, 30, 98, 68, 73, 92, 37, 69, 93, 28, 58, 36, 8 > 99 vector <int> petr(petr_, petr_+sizeof(petr_)/sizeof(*petr_)); > 100 int snuke_[] = {28, 29, 22, 75, 78, 75, 39, 41, 5, 14, 100, 28, 51, 42, > 101 vector <int> snuke(snuke_, snuke_+sizeof(snuke_)/sizeof(*snuke_)); > 102 int _ = 28; > 103 END > 104 CASE(4) > 105 int petr_[] = {69,32,81,40,44,69,80,13,46,34,100,93,81,46,72,10,98,27,27 > 106 vector <int> petr(petr_, petr_+sizeof(petr_)/sizeof(*petr_)); > 107 int snuke_[] = {52,76,64,82,37,76,31,5,54,53,98,12,26,22,80,8,5,21,48,44 > 108 vector <int> snuke(snuke_, snuke_+sizeof(snuke_)/sizeof(*snuke_)); > 109 int _ = -1; > 110 END > 111 CASE(5) > 112 int petr_[] = {7,2,7,5,8,1,3,5,7,4,4,8,6,5,8,8,8,4,1,2,1,2,6,3,1,5,2,3,8 > 113 vector <int> petr(petr_, petr_+sizeof(petr_)/sizeof(*petr_)); > 114 int snuke_[] = {7,3,6,7,8,4,7,3,2,1,3,6,8,7,8,2,8,8,7,7,8,5,7,6,2,1,8,5, > 115 vector <int> snuke(snuke_, snuke_+sizeof(snuke_)/sizeof(*snuke_)); > 116 int _ = -1; > 117 END > 118 } > 119 // END CUT HERE