Overview
| SHA1 Hash: | f6e551e04b5aecf33f362c1b4c726b0bb732e033 |
|---|---|
| Date: | 2012-05-19 15:56:15 |
| User: | kinaba |
| Comment: | TCO12-2B |
| 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-2B-U/1A.cpp version [02db4ce3f40ece1c]
> 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 <cstring> > 18 #ifdef __GNUC__ > 19 #include <ext/hash_map> > 20 #define unordered_map __gnu_cxx::hash_map > 21 #else > 22 #include <unordered_map> > 23 #endif > 24 using namespace std; > 25 typedef long long LL; > 26 typedef complex<double> CMP; > 27 > 28 class BlurredDartboard { public: > 29 int minThrows(vector <int> points, int P) > 30 { > 31 const int N = points.size(); > 32 > 33 int VisibleMax = *max_element(points.begin(), points.end()); > 34 > 35 vector<int> hidden; > 36 for(int x=1; x<=N; ++x) > 37 if( count(points.begin(), points.end(), x) == 0 ) > 38 hidden.push_back(x); > 39 > 40 int K = hidden.size(); > 41 if( hidden.empty() || hidden.back() < VisibleMax ) > 42 return (P+VisibleMax-1) / VisibleMax; > 43 > 44 partial_sum(hidden.begin(), hidden.end(), hidden.begin()); > 45 vector<int> vis; > 46 for(int i=1; i<=K; ++i) > 47 vis.push_back(i*VisibleMax); > 48 > 49 int turn = max(vis.back(), hidden.back()); > 50 int n = (P/turn)*K; > 51 if(P%turn) { > 52 ++n; > 53 for(int i=0; max(vis[i],hidden[i]) < (P%turn); ++i) > 54 ++n; > 55 } > 56 return n; > 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(_, BlurredDartboard().minThrows(points, P));} > 74 int main(){ > 75 > 76 CASE(0) > 77 int points_[] = {0, 3, 4, 0, 0}; > 78 vector <int> points(points_, points_+sizeof(points_)/sizeof(*points_)) > 79 int P = 8; > 80 int _ = 2; > 81 END > 82 CASE(1) > 83 int points_[] = {0, 0, 0, 0, 0}; > 84 vector <int> points(points_, points_+sizeof(points_)/sizeof(*points_)) > 85 int P = 15; > 86 int _ = 5; > 87 END > 88 CASE(2) > 89 int points_[] = {4, 7, 8, 1, 3, 2, 6, 5}; > 90 vector <int> points(points_, points_+sizeof(points_)/sizeof(*points_)) > 91 int P = 2012; > 92 int _ = 252; > 93 END > 94 CASE(3) > 95 int points_[] = {0, 0, 5, 0, 0, 0, 1, 3, 0, 0}; > 96 vector <int> points(points_, points_+sizeof(points_)/sizeof(*points_)) > 97 int P = 2012; > 98 int _ = 307; > 99 END > 100 CASE(4) > 101 int points_[] = {0, 2, 0, 0, 0, 0, 0, 0, 0, 9, 0, 0, 6, 0, 0, 0, 4, 0, 0 > 102 vector <int> points(points_, points_+sizeof(points_)/sizeof(*points_)) > 103 int P = 1000000000; > 104 int _ = 84656087; > 105 END > 106 CASE(5) > 107 int points_[] = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 > 108 vector <int> points(points_, points_+sizeof(points_)/sizeof(*points_)) > 109 int P = 1000000000; > 110 int _ = -1; > 111 END > 112 /* > 113 CASE(6) > 114 int points_[] = ; > 115 vector <int> points(points_, points_+sizeof(points_)/sizeof(*points_)) > 116 int P = ; > 117 int _ = ; > 118 END > 119 */ > 120 } > 121 // END CUT HERE
Added SRM/TCO12-2B-U/1B.cpp version [b2dc4bd6b9ccd651]
> 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 <cstring> > 18 #ifdef __GNUC__ > 19 #include <ext/hash_map> > 20 #define unordered_map __gnu_cxx::hash_map > 21 #else > 22 #include <unordered_map> > 23 #endif > 24 using namespace std; > 25 typedef long long LL; > 26 typedef complex<double> CMP; > 27 > 28 template<typename T> > 29 struct DP2 > 30 { > 31 const int N1, N2; > 32 vector<T> data; > 33 DP2(int N1, int N2, const T& t = T()) > 34 : N1(N1), N2(N2), data(N1*N2, t) { assert(data.size()*sizeof(T)< > 35 T& operator()(int i1, int i2) > 36 { return data[ (i1*N2)+i2 ]; } > 37 void swap(DP2& rhs) > 38 { data.swap(rhs.data); } > 39 }; > 40 > 41 class HeavyBooks { public: > 42 vector <int> findWeight(vector <int> books, vector <int> moves) > 43 { > 44 const int K = moves[0]; > 45 > 46 vector<int> tomek, wojtek; > 47 for(int i=0; i<K; ++i) > 48 wojtek.push_back(i); > 49 > 50 for(int i=1; i<moves.size(); ++i) { > 51 vector<int>& fr = (i%2 == 0 ? tomek : wojtek); > 52 vector<int>& to = (i%2 == 0 ? wojtek : tomek); > 53 for(int k=0; k<moves[i] && !fr.empty(); ++k) { > 54 to.push_back(fr.back()); > 55 fr.pop_back(); > 56 } > 57 sort(fr.begin(), fr.end()); > 58 sort(to.begin(), to.end()); > 59 } > 60 > 61 vector<bool> for_tomek(K); > 62 for(int i=0; i<tomek.size(); ++i) > 63 for_tomek[tomek[i]] = true; > 64 > 65 sort(books.begin(), books.end()); > 66 > 67 DP2< pair<int,int> > dp(books.size(), K+1); > 68 for(int i=0; i<books.size(); ++i) > 69 for(int k=0; k<=K; ++k) > 70 { > 71 int DifIncr = for_tomek[k-1] ? -books[i] : +books[i]; > 72 int SumIncr = books[i]; > 73 if( i == 0 ) { > 74 if( k == 0 ) > 75 dp(i, k) = make_pair(0, 0); > 76 else if( k == 1 ) > 77 dp(i, k) = make_pair(DifIncr, SumIncr); > 78 else > 79 dp(i, k) = make_pair(-123456789, -123456 > 80 } else { > 81 dp(i, k) = dp(i-1, k); > 82 if( k == 0 ) { > 83 } else { > 84 int PrevDif = dp(i-1,k-1).first; > 85 int PrevSum = dp(i-1,k-1).second; > 86 pair<int,int> next(PrevDif+DifIncr, Prev > 87 if( dp(i,k) < next ) > 88 dp(i,k) = next; > 89 } > 90 } > 91 } > 92 > 93 int WminusT = dp(books.size()-1, K).first; > 94 int WplusT = dp(books.size()-1, K).second; > 95 vector<int> answer; > 96 answer.push_back( (WplusT - WminusT)/2 ); > 97 answer.push_back( (WplusT + WminusT)/2 ); > 98 return answer; > 99 } > 100 }; > 101 > 102 // BEGIN CUT HERE > 103 #include <ctime> > 104 double start_time; string timer() > 105 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 106 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 107 { os << "{ "; > 108 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 109 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 110 void verify_case(const vector <int>& Expected, const vector <int>& Received) { > 111 bool ok = (Expected == Received); > 112 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 113 cerr << "\to: " << Expected << endl << "\tx: " << Received << endl; } } > 114 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 115 #define END verify_case(_, HeavyBooks().findWeight(books, moves));} > 116 int main(){ > 117 > 118 CASE(0) > 119 int books_[] = {5,2,3,1}; > 120 vector <int> books(books_, books_+sizeof(books_)/sizeof(*books_)); > 121 int moves_[] = {3,2,1,1,1}; > 122 vector <int> moves(moves_, moves_+sizeof(moves_)/sizeof(*moves_)); > 123 int __[] = {3, 7 }; > 124 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 125 END > 126 CASE(1) > 127 int books_[] = {10, 100, 1000}; > 128 vector <int> books(books_, books_+sizeof(books_)/sizeof(*books_)); > 129 int moves_[] = {2, 3}; > 130 vector <int> moves(moves_, moves_+sizeof(moves_)/sizeof(*moves_)); > 131 int __[] = {110, 0 }; > 132 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 133 END > 134 CASE(2) > 135 int books_[] = {155870,565381}; > 136 vector <int> books(books_, books_+sizeof(books_)/sizeof(*books_)); > 137 int moves_[] = {1,1,1}; > 138 vector <int> moves(moves_, moves_+sizeof(moves_)/sizeof(*moves_)); > 139 int __[] = {0, 565381 }; > 140 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 141 END > 142 CASE(3) > 143 int books_[] = {500,500,500,500}; > 144 vector <int> books(books_, books_+sizeof(books_)/sizeof(*books_)); > 145 int moves_[] = {4,1,1,3,2}; > 146 vector <int> moves(moves_, moves_+sizeof(moves_)/sizeof(*moves_)); > 147 int __[] = {500, 1500 }; > 148 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 149 END > 150 CASE(4) > 151 int books_[] = {1,1,1,1,1000000}; > 152 vector <int> books(books_, books_+sizeof(books_)/sizeof(*books_)); > 153 int moves_[] = {1}; > 154 vector <int> moves(moves_, moves_+sizeof(moves_)/sizeof(*moves_)); > 155 int __[] = {0, 1000000 }; > 156 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 157 END > 158 CASE(5) > 159 int books_[] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20}; > 160 vector <int> books(books_, books_+sizeof(books_)/sizeof(*books_)); > 161 int moves_[] = {20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1}; > 162 vector <int> moves(moves_, moves_+sizeof(moves_)/sizeof(*moves_)); > 163 int __[] = {110, 100 }; > 164 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 165 END > 166 /* > 167 CASE(6) > 168 int books_[] = ; > 169 vector <int> books(books_, books_+sizeof(books_)/sizeof(*books_)); > 170 int moves_[] = ; > 171 vector <int> moves(moves_, moves_+sizeof(moves_)/sizeof(*moves_)); > 172 int __[] = ; > 173 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 174 END > 175 CASE(7) > 176 int books_[] = ; > 177 vector <int> books(books_, books_+sizeof(books_)/sizeof(*books_)); > 178 int moves_[] = ; > 179 vector <int> moves(moves_, moves_+sizeof(moves_)/sizeof(*moves_)); > 180 int __[] = ; > 181 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 182 END > 183 */ > 184 } > 185 // END CUT HERE