Overview
| SHA1 Hash: | 2ba3bf09a0f0251ac9f52205289d436159f917f5 |
|---|---|
| Date: | 2013-05-11 19:07:14 |
| User: | kinaba |
| Comment: | TCO 13 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
Added SRM/TCO13-2C-U/1A.cpp version [8ec0b22b8f67ffe8]
> 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 DancingFoxes { public: > 23 int minimalDays(vector <string> friendship) > 24 { > 25 static const int INF = 0x1fffffff; > 26 int N = friendship.size(); > 27 vector< vector<int> > M(N, vector<int>(N)); > 28 for(int i=0; i<N; ++i) > 29 for(int k=0; k<N; ++k) > 30 M[i][k] = (friendship[i][k]=='Y' ? 1 : INF); > 31 > 32 for(int k=0; k<N; ++k) > 33 for(int i=0; i<N; ++i) > 34 for(int j=0; j<N; ++j) > 35 M[i][j] = min(M[i][j], M[i][k]+M[k][j]); > 36 > 37 if(M[0][1] == INF) > 38 return -1; > 39 > 40 int s = 0; > 41 for(int d = M[0][1]; d>1; ++s) > 42 d -= (d+1)/3; > 43 return s; > 44 } > 45 }; > 46 > 47 // BEGIN CUT HERE > 48 #include <ctime> > 49 double start_time; string timer() > 50 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 51 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 52 { os << "{ "; > 53 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 54 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 55 void verify_case(const int& Expected, const int& Received) { > 56 bool ok = (Expected == Received); > 57 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 58 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 59 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 60 #define END verify_case(_, DancingFoxes().minimalDays(friendship));} > 61 int main(){ > 62 > 63 CASE(0) > 64 string friendship_[] = {"NNY", > 65 "NNY", > 66 "YYN"}; > 67 vector <string> friendship(friendship_, friendship_+sizeof(friendship_ > 68 int _ = 1; > 69 END > 70 CASE(1) > 71 string friendship_[] = {"NNNNN", > 72 "NNYYY", > 73 "NYNYY", > 74 "NYYNY", > 75 "NYYYN"}; > 76 vector <string> friendship(friendship_, friendship_+sizeof(friendship_ > 77 int _ = -1; > 78 END > 79 CASE(2) > 80 string friendship_[] = {"NNYYNN", > 81 "NNNNYY", > 82 "YNNNYN", > 83 "YNNNNY", > 84 "NYYNNN", > 85 "NYNYNN"}; > 86 vector <string> friendship(friendship_, friendship_+sizeof(friendship_ > 87 int _ = 2; > 88 END > 89 CASE(3) > 90 string friendship_[] = {"NNYNNNNYN", > 91 "NNNNYNYNN", > 92 "YNNYNYNNN", > 93 "NNYNYNYYN", > 94 "NYNYNNNNY", > 95 "NNYNNNYNN", > 96 "NYNYNYNNN", > 97 "YNNYNNNNY", > 98 "NNNNYNNYN"}; > 99 vector <string> friendship(friendship_, friendship_+sizeof(friendship_ > 100 int _ = 3; > 101 END > 102 CASE(4) > 103 string friendship_[] = {"NY", > 104 "YN"}; > 105 vector <string> friendship(friendship_, friendship_+sizeof(friendship_ > 106 int _ = 0; > 107 END > 108 CASE(5) > 109 string friendship_[] = { > 110 "NNYNNNNNN", > 111 "NNNNNNNNY", > 112 "YNNYNNNNN", > 113 "NNYNYNNNN", > 114 "NNNYNYNNN", > 115 "NNNNYNYNN", > 116 "NNNNNYNYN", > 117 "NNNNNNYNY", > 118 "NYNNNNNYN" > 119 }; > 120 vector <string> friendship(friendship_, friendship_+sizeof(friendship_ > 121 int N = friendship.size(); > 122 int idx[] = {0,8,1,2,3,4,5,6,7}; > 123 for(int y=0; y<N; ++y, cout<<endl) > 124 for(int x=0; x<N; ++x) { > 125 cout << friendship[idx[y]][idx[x]]; > 126 } > 127 int _ = -1; > 128 END > 129 /* > 130 CASE(6) > 131 string friendship_[] = ; > 132 vector <string> friendship(friendship_, friendship_+sizeof(friendship_ > 133 int _ = ; > 134 END > 135 */ > 136 } > 137 // END CUT HERE
Added SRM/TCO13-2C-U/1B.cpp version [c50d0a704a3e9f57]
> 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 TheMountain { public: > 23 int minSum(int H, int W, vector <int> Y, vector <int> X, vector <int> V) > 24 { > 25 const int N = Y.size(); > 26 static const int INF = 0x3fffffff; > 27 int best = INF; > 28 > 29 vector< vector<int> > fixed(H, vector<int>(W, 0)); > 30 for(int i=0; i<N; ++i) > 31 fixed[Y[i]][X[i]] = V[i]; > 32 > 33 for(int x=0; x<W; ++x) > 34 { > 35 vector< vector<int> > td(H, vector<int>(W)); > 36 vector<int> td_sum(H); > 37 int td_end = 0; > 38 for(int y=0; y<H; ++y) > 39 { > 40 for(int a=0; a<x; ++a) { > 41 int req = 1; > 42 if(0<=a-1&&a-1<W) req = max(req, td[y][a > 43 if(0<=y-1&&y-1<H) req = max(req, td[y-1] > 44 if(fixed[y][a]) { > 45 if(fixed[y][a] < req) > 46 goto label_td_end; > 47 td[y][a] = fixed[y][a]; > 48 } else { > 49 td[y][a] = req; > 50 } > 51 } > 52 for(int a=W-1; a>x; --a) { > 53 int req = 1; > 54 if(0<=a+1&&a+1<W) req = max(req, td[y][a > 55 if(0<=y-1&&y-1<H) req = max(req, td[y-1] > 56 if(fixed[y][a]) { > 57 if(fixed[y][a] < req) > 58 goto label_td_end; > 59 td[y][a] = fixed[y][a]; > 60 } else { > 61 td[y][a] = req; > 62 } > 63 } > 64 int a = x; > 65 { > 66 int req = 1; > 67 if(0<=a-1&&a-1<W) req = max(req, td[y][a > 68 if(0<=a+1&&a+1<W) req = max(req, td[y][a > 69 if(0<=y-1&&y-1<H) req = max(req, td[y-1] > 70 if(fixed[y][a]) { > 71 if(fixed[y][a] < req) > 72 goto label_td_end; > 73 td[y][a] = fixed[y][a]; > 74 } else { > 75 td[y][a] = req; > 76 } > 77 } > 78 td_sum[y] = accumulate(td[y].begin(), td[y].end( > 79 td_end ++; > 80 } > 81 label_td_end:; > 82 > 83 vector< vector<int> > bu(H, vector<int>(W)); > 84 vector<int> bu_sum(H); > 85 int bu_begin = H; > 86 for(int y=H-1; y>=0; --y) > 87 { > 88 for(int a=0; a<x; ++a) { > 89 int req = 1; > 90 if(0<=a-1&&a-1<W) req = max(req, bu[y][a > 91 if(0<=y+1&&y+1<H) req = max(req, bu[y+1] > 92 if(fixed[y][a]) { > 93 if(fixed[y][a] < req) > 94 goto label_bu_end; > 95 bu[y][a] = fixed[y][a]; > 96 } else { > 97 bu[y][a] = req; > 98 } > 99 } > 100 for(int a=W-1; a>x; --a) { > 101 int req = 1; > 102 if(0<=a+1&&a+1<W) req = max(req, bu[y][a > 103 if(0<=y+1&&y+1<H) req = max(req, bu[y+1] > 104 if(fixed[y][a]) { > 105 if(fixed[y][a] < req) > 106 goto label_bu_end; > 107 bu[y][a] = fixed[y][a]; > 108 } else { > 109 bu[y][a] = req; > 110 } > 111 } > 112 int a = x; > 113 { > 114 int req = 1; > 115 if(0<=a-1&&a-1<W) req = max(req, bu[y][a > 116 if(0<=a+1&&a+1<W) req = max(req, bu[y][a > 117 if(0<=y+1&&y+1<H) req = max(req, bu[y+1] > 118 if(fixed[y][a]) { > 119 if(fixed[y][a] < req) > 120 goto label_bu_end; > 121 bu[y][a] = fixed[y][a]; > 122 } else { > 123 bu[y][a] = req; > 124 } > 125 } > 126 bu_sum[y] = accumulate(bu[y].begin(), bu[y].end( > 127 bu_begin --; > 128 } > 129 label_bu_end:; > 130 > 131 if(td_end <= bu_begin) > 132 continue; > 133 > 134 int baseline = 0; > 135 for(int Y=0; Y<H; ++Y) > 136 baseline += (Y<bu_begin ? td_sum[Y] : Y==bu_begi > 137 > 138 for(int y=bu_begin; y<td_end; ++y) > 139 { > 140 int score = baseline; > 141 for(int x=0; x<W; ++x) > 142 score += max(td[y][x], bu[y][x]); > 143 best = min(best, score); > 144 if(y<H) > 145 baseline += td_sum[y] - bu_sum[y+1]; > 146 } > 147 } > 148 return (best==INF ? -1 : best); > 149 } > 150 }; > 151 > 152 // BEGIN CUT HERE > 153 #include <ctime> > 154 double start_time; string timer() > 155 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 156 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 157 { os << "{ "; > 158 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 159 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 160 void verify_case(const int& Expected, const int& Received) { > 161 bool ok = (Expected == Received); > 162 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 163 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 164 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 165 #define END verify_case(_, TheMountain().minSum(n, m, rowIndex, columnIndex > 166 int main(){ > 167 > 168 CASE(0) > 169 int n = 2; > 170 int m = 3; > 171 int rowIndex_[] = {0, 0, 0, 1, 1, 1}; > 172 vector <int> rowIndex(rowIndex_, rowIndex_+sizeof(rowIndex_)/sizeof(*r > 173 int columnIndex_[] = {0, 1, 2, 0, 1, 2}; > 174 vector <int> columnIndex(columnIndex_, columnIndex_+sizeof(columnIndex > 175 int element_[] = {4, 6, 9, 1, 3, 6}; > 176 vector <int> element(element_, element_+sizeof(element_)/sizeof(*eleme > 177 int _ = 29; > 178 END > 179 CASE(1) > 180 int n = 2; > 181 int m = 3; > 182 int rowIndex_[] = {1, 0, 1}; > 183 vector <int> rowIndex(rowIndex_, rowIndex_+sizeof(rowIndex_)/sizeof(*r > 184 int columnIndex_[] = {2, 2, 0}; > 185 vector <int> columnIndex(columnIndex_, columnIndex_+sizeof(columnIndex > 186 int element_[] = {5, 7, 6}; > 187 vector <int> element(element_, element_+sizeof(element_)/sizeof(*eleme > 188 int _ = 40; > 189 END > 190 CASE(2) > 191 int n = 3; > 192 int m = 3; > 193 int rowIndex_[] = {0, 0, 2, 2}; > 194 vector <int> rowIndex(rowIndex_, rowIndex_+sizeof(rowIndex_)/sizeof(*r > 195 int columnIndex_[] = {0, 2, 2, 0}; > 196 vector <int> columnIndex(columnIndex_, columnIndex_+sizeof(columnIndex > 197 int element_[] = {1, 1, 1, 1}; > 198 vector <int> element(element_, element_+sizeof(element_)/sizeof(*eleme > 199 int _ = 15; > 200 END > 201 CASE(3) > 202 int n = 2; > 203 int m = 2; > 204 int rowIndex_[] = {0, 0, 1, 1}; > 205 vector <int> rowIndex(rowIndex_, rowIndex_+sizeof(rowIndex_)/sizeof(*r > 206 int columnIndex_[] = {0, 1, 1, 0}; > 207 vector <int> columnIndex(columnIndex_, columnIndex_+sizeof(columnIndex > 208 int element_[] = {5, 8, 5, 8}; > 209 vector <int> element(element_, element_+sizeof(element_)/sizeof(*eleme > 210 int _ = -1; > 211 END > 212 CASE(4) > 213 int n = 1; > 214 int m = 3; > 215 int rowIndex_[] = {0}; > 216 vector <int> rowIndex(rowIndex_, rowIndex_+sizeof(rowIndex_)/sizeof(*r > 217 int columnIndex_[] = {1}; > 218 vector <int> columnIndex(columnIndex_, columnIndex_+sizeof(columnIndex > 219 int element_[] = {1}; > 220 vector <int> element(element_, element_+sizeof(element_)/sizeof(*eleme > 221 int _ = -1; > 222 END > 223 CASE(5) > 224 int n = 123; > 225 int m = 45; > 226 int rowIndex_[] = {2, 3, 5, 7, 11}; > 227 vector <int> rowIndex(rowIndex_, rowIndex_+sizeof(rowIndex_)/sizeof(*r > 228 int columnIndex_[] = {13, 17, 19, 23, 29}; > 229 vector <int> columnIndex(columnIndex_, columnIndex_+sizeof(columnIndex > 230 int element_[] = {100, 200, 300, 400, 500}; > 231 vector <int> element(element_, element_+sizeof(element_)/sizeof(*eleme > 232 int _ = 367047; > 233 END > 234 CASE(6) > 235 int n = 200; > 236 int m = 200; > 237 int rowIndex_[] = {5}; > 238 vector <int> rowIndex(rowIndex_, rowIndex_+sizeof(rowIndex_)/sizeof(*r > 239 int columnIndex_[] = {8}; > 240 vector <int> columnIndex(columnIndex_, columnIndex_+sizeof(columnIndex > 241 int element_[] = {666}; > 242 vector <int> element(element_, element_+sizeof(element_)/sizeof(*eleme > 243 int _ = 5737554; > 244 END > 245 CASE(7) > 246 int n = 10; > 247 int m = 10; > 248 int rowIndex_[] = {0, 8, 7}; > 249 vector <int> rowIndex(rowIndex_, rowIndex_+sizeof(rowIndex_)/sizeof(*r > 250 int columnIndex_[] = {3, 1, 9}; > 251 vector <int> columnIndex(columnIndex_, columnIndex_+sizeof(columnIndex > 252 int element_[] = {5, 4, 7}; > 253 vector <int> element(element_, element_+sizeof(element_)/sizeof(*eleme > 254 int _ = 593; > 255 END > 256 CASE(8) > 257 int n = 200; > 258 int m = 200; > 259 int rowIndex_[] = {129,99,142,33,111,174,169,176,83,143,70,116,193,139,7 > 260 vector <int> rowIndex(rowIndex_, rowIndex_+sizeof(rowIndex_)/sizeof(*r > 261 int columnIndex_[] = {191,148,194,13,90,17,185,163,17,170,193,165,140,15 > 262 vector <int> columnIndex(columnIndex_, columnIndex_+sizeof(columnIndex > 263 int element_[] = {953,216,307,197,970,590,659,153,79,262,628,153,106,904 > 264 vector <int> element(element_, element_+sizeof(element_)/sizeof(*eleme > 265 int _ = -1; > 266 END > 267 /* > 268 CASE(9) > 269 int n = ; > 270 int m = ; > 271 int rowIndex_[] = ; > 272 vector <int> rowIndex(rowIndex_, rowIndex_+sizeof(rowIndex_)/sizeof(*r > 273 int columnIndex_[] = ; > 274 vector <int> columnIndex(columnIndex_, columnIndex_+sizeof(columnIndex > 275 int element_[] = ; > 276 vector <int> element(element_, element_+sizeof(element_)/sizeof(*eleme > 277 int _ = ; > 278 END > 279 */ > 280 } > 281 // END CUT HERE
Added YNGraph.rb version [7857b17ad5edb6a7]
> 1 STDERR.print "Number of nodes? " > 2 V = gets.to_i > 3 > 4 STDERR.print "Directed (u/d)? " > 5 D = (gets.chomp.downcase=="d"); > 6 > 7 ES = [] > 8 loop do > 9 STDERR.print "Edge (u v)? " > 10 edge = gets.split.map(&:to_i) > 11 break if edge.size==0 > 12 ES << edge > 13 end > 14 > 15 V.times do |y| > 16 puts (0...V).map{|x| > 17 (D ? ES.index([y,x]) : ES.index([y,x]) || ES.index([x,y])) ? "Y" > 18 }*"" > 19 end