Overview
| SHA1 Hash: | 006cf643bb908b38141638f1e78c1896170f5ce0 |
|---|---|
| Date: | 2013-06-22 13:20:07 |
| User: | kinaba |
| Comment: | 583. |
| 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/583-U/1A.cpp version [a651e5c841fa9c10]
> 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<double> CMP; > 21 > 22 class TravelOnMars { public: > 23 int minTimes(vector <int> range, int startCity, int endCity) > 24 { > 25 int N = range.size(); > 26 > 27 set<int> V; > 28 V.insert(startCity); > 29 for(int s=0 ;; ++s) > 30 { > 31 if(V.count(endCity)) > 32 return s; > 33 set<int> VV; > 34 for(set<int>::iterator it=V.begin(); it!=V.end(); ++it) > 35 { > 36 int v = *it; > 37 for(int d=0; d<=range[v]; ++d) { > 38 VV.insert((v+d)%N); > 39 VV.insert((v-d+N*100)%N); > 40 } > 41 } > 42 V.swap(VV); > 43 } > 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(_, TravelOnMars().minTimes(range, startCity, endCit > 61 int main(){ > 62 > 63 CASE(0) > 64 int range_[] = {2,1,1,1,1,1}; > 65 vector <int> range(range_, range_+sizeof(range_)/sizeof(*range_)); > 66 int startCity = 1; > 67 int endCity = 4; > 68 int _ = 2; > 69 END > 70 CASE(1) > 71 int range_[] = {2,1,1,1,1,1}; > 72 vector <int> range(range_, range_+sizeof(range_)/sizeof(*range_)); > 73 int startCity = 4; > 74 int endCity = 1; > 75 int _ = 3; > 76 END > 77 CASE(2) > 78 int range_[] = {2,1,1,2,1,2,1,1}; > 79 vector <int> range(range_, range_+sizeof(range_)/sizeof(*range_)); > 80 int startCity = 2; > 81 int endCity = 6; > 82 int _ = 3; > 83 END > 84 CASE(3) > 85 int range_[] = {3,2,1,1,3,1,2,2,1,1,2,2,2,2,3}; > 86 vector <int> range(range_, range_+sizeof(range_)/sizeof(*range_)); > 87 int startCity = 6; > 88 int endCity = 13; > 89 int _ = 4; > 90 END > 91 CASE(4) > 92 int range_[] = {10,1,1,1,4,1,1,1,1,1,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2}; > 93 vector <int> range(range_, range_+sizeof(range_)/sizeof(*range_)); > 94 int startCity = 3; > 95 int endCity = 10; > 96 int _ = 3; > 97 END > 98 CASE(5) > 99 int range_[] = {50,50}; > 100 vector <int> range(range_, range_+sizeof(range_)/sizeof(*range_)); > 101 int startCity = 0; > 102 int endCity = 1; > 103 int _ = 1; > 104 END > 105 } > 106 // END CUT HERE
Added SRM/583-U/1B.cpp version [7d4d425514bcb888]
> 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<double> CMP; > 21 > 22 class TurnOnLamps { public: > 23 typedef int Vert; > 24 struct Edge { > 25 bool init; > 26 bool goal; > 27 Vert from; > 28 Vert to; > 29 }; > 30 > 31 int minimize(vector <int> roads, string initState, string isImportant) > 32 { > 33 int N = roads.size() + 1; > 34 vector< vector<Edge> > G(N); > 35 for(int i=0; i<roads.size(); ++i) > 36 { > 37 int v = i+1; > 38 int u = roads[i]; > 39 {Edge e = {initState[i]=='1', isImportant[i]=='1', v, u} > 40 {Edge e = {initState[i]=='1', isImportant[i]=='1', u, v} > 41 } > 42 > 43 Edge e = {false, false, -1, 0}; > 44 pair<int,int> rr = rec(e, G); > 45 return min(rr.first, rr.second); > 46 } > 47 > 48 static const int INF = 999999; > 49 > 50 // not use, use > 51 pair<int,int> rec(Edge e, vector<vector<Edge> >& G) > 52 { > 53 vector< pair<int,int> > p; > 54 for(int i=0; i<G[e.to].size(); ++i) > 55 { > 56 Edge& e2 = G[e.to][i]; > 57 if(e2.to != e.from) > 58 p.push_back(rec(e2, G)); > 59 } > 60 pair<int,int> r = calc_on_node(p); > 61 if(e.goal) > 62 (e.init ? r.second : r.first) = INF; > 63 return r; > 64 } > 65 > 66 pair<int,int> calc_on_node(vector<pair<int,int> >& c) > 67 { > 68 int nu = calc(c); > 69 int u = (c.empty() ? 1 : INF); > 70 for(int i=0; i<c.size(); ++i) > 71 { > 72 vector<pair<int,int> > cc = c; > 73 cc.erase(cc.begin() + i); > 74 int s1 = calc(cc); > 75 int s2 = min(c[i].first + 1, c[i].second); > 76 u = min(u, s1+s2); > 77 } > 78 return make_pair(nu, u); > 79 } > 80 > 81 int calc(vector<pair<int,int> >& c) > 82 { > 83 int od = INF; > 84 int ev = 0; > 85 for(int i=0; i<c.size(); ++i) > 86 { > 87 int c0 = c[i].first; > 88 int c1 = c[i].second; > 89 > 90 int od2 = min(ev+c1, od+c0); > 91 int ev2 = min(ev+c0, od+c1-1); > 92 od = od2, ev = ev2; > 93 } > 94 return min(od, ev); > 95 } > 96 }; > 97 > 98 // BEGIN CUT HERE > 99 #include <ctime> > 100 double start_time; string timer() > 101 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 102 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 103 { os << "{ "; > 104 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 105 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 106 void verify_case(const int& Expected, const int& Received) { > 107 bool ok = (Expected == Received); > 108 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 109 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 110 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 111 #define END verify_case(_, TurnOnLamps().minimize(roads, initState, isImpor > 112 int main(){ > 113 > 114 CASE(0) > 115 int roads_[] = {0,0,1,1}; > 116 vector <int> roads(roads_, roads_+sizeof(roads_)/sizeof(*roads_)); > 117 string initState = "0001"; > 118 string isImportant = "0111"; > 119 int _ = 1; > 120 END > 121 CASE(1) > 122 int roads_[] = {0,0,1,1}; > 123 vector <int> roads(roads_, roads_+sizeof(roads_)/sizeof(*roads_)); > 124 string initState = "0000"; > 125 string isImportant = "0111"; > 126 int _ = 2; > 127 END > 128 CASE(2) > 129 int roads_[] = {0,0,1,1,4,4}; > 130 vector <int> roads(roads_, roads_+sizeof(roads_)/sizeof(*roads_)); > 131 string initState = "000100"; > 132 string isImportant = "111111"; > 133 int _ = 2; > 134 END > 135 CASE(3) > 136 int roads_[] = {0,0,1,1,4,4}; > 137 vector <int> roads(roads_, roads_+sizeof(roads_)/sizeof(*roads_)); > 138 string initState = "100100"; > 139 string isImportant = "011101"; > 140 int _ = 2; > 141 END > 142 CASE(4) > 143 int roads_[] = {0,0,2,2,3,1,6,3,1}; > 144 vector <int> roads(roads_, roads_+sizeof(roads_)/sizeof(*roads_)); > 145 string initState = "010001110"; > 146 string isImportant = "000110100"; > 147 int _ = 1; > 148 END > 149 CASE(5) > 150 int roads_[] = {0,0,1,2,4,4,6,1,2,5,2,8,8,3,6,4,14,7,18,14,11,7,1,12,7,5 > 151 vector <int> roads(roads_, roads_+sizeof(roads_)/sizeof(*roads_)); > 152 string initState = "0000000000010000000000000010000010100000000000000"; > 153 string isImportant = "1010111111111011011111000110111111111111111110111" > 154 int _ = 14; > 155 END > 156 /* > 157 CASE(6) > 158 int roads_[] = ; > 159 vector <int> roads(roads_, roads_+sizeof(roads_)/sizeof(*roads_)); > 160 string initState = ; > 161 string isImportant = ; > 162 int _ = ; > 163 END > 164 CASE(7) > 165 int roads_[] = ; > 166 vector <int> roads(roads_, roads_+sizeof(roads_)/sizeof(*roads_)); > 167 string initState = ; > 168 string isImportant = ; > 169 int _ = ; > 170 END > 171 */ > 172 } > 173 // END CUT HERE