Overview
| SHA1 Hash: | 2b07d53d04d3e65bba16afa907f36f09b82bd500 |
|---|---|
| Date: | 2012-07-07 14:14:07 |
| User: | kinaba |
| Comment: | 528 |
| 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/548-U/1A.cpp version [4bd4984796b0669c]
> 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 KingdomAndTrees { public: > 23 int minLevel(vector <int> heights) > 24 { > 25 // (L,R] > 26 int L = -1; > 27 int R = 1000000000; > 28 while(R-L>1) > 29 { > 30 int C = (L+R)/2; > 31 (possible(C,heights) ? R : L) = C; > 32 } > 33 return R; > 34 } > 35 > 36 bool possible(int C, const vector<int>& h) > 37 { > 38 int last = max(1, h[0]-C); > 39 for(int i=1; i<h.size(); ++i) > 40 { > 41 if( !(last < h[i]+C) ) > 42 return false; > 43 last = max(last+1, h[i]-C); > 44 } > 45 return true; > 46 } > 47 }; > 48 > 49 // BEGIN CUT HERE > 50 #include <ctime> > 51 double start_time; string timer() > 52 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 53 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 54 { os << "{ "; > 55 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 56 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 57 void verify_case(const int& Expected, const int& Received) { > 58 bool ok = (Expected == Received); > 59 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 60 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 61 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 62 #define END verify_case(_, KingdomAndTrees().minLevel(heights));} > 63 int main(){ > 64 > 65 CASE(0) > 66 int heights_[] = {9, 5, 11}; > 67 vector <int> heights(heights_, heights_+sizeof(heights_)/sizeof(*heigh > 68 int _ = 3; > 69 END > 70 CASE(1) > 71 int heights_[] = {5, 8}; > 72 vector <int> heights(heights_, heights_+sizeof(heights_)/sizeof(*heigh > 73 int _ = 0; > 74 END > 75 CASE(2) > 76 int heights_[] = {1, 1, 1, 1, 1}; > 77 vector <int> heights(heights_, heights_+sizeof(heights_)/sizeof(*heigh > 78 int _ = 4; > 79 END > 80 CASE(3) > 81 int heights_[] = {548, 47, 58, 250, 2012}; > 82 vector <int> heights(heights_, heights_+sizeof(heights_)/sizeof(*heigh > 83 int _ = 251; > 84 END > 85 CASE(4) > 86 int heights_[] = {337994619,837714986,7014426,516695490,268514071,590654 > 87 vector <int> heights(heights_, heights_+sizeof(heights_)/sizeof(*heigh > 88 int _ = -1; > 89 END > 90 CASE(5) > 91 int heights_[] = {1000000000,1}; > 92 vector <int> heights(heights_, heights_+sizeof(heights_)/sizeof(*heigh > 93 int _ = 500000000; > 94 END > 95 > 96 } > 97 // END CUT HERE
Added SRM/548-U/1B.cpp version [3c1fd7f25faac951]
> 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 template<typename T> > 23 struct DP3 > 24 { > 25 int N1, N2, N3; > 26 vector<T> data; > 27 DP3(int N1, int N2, int N3, const T& t = T()) > 28 : N1(N1), N2(N2), N3(N3), data(N1*N2*N3, t) { assert(data.size() > 29 T& operator()(int i1, int i2, int i3) > 30 { return data[ ((i1*N2)+i2)*N3+i3 ]; } > 31 void swap(DP3& rhs) > 32 { data.swap(rhs.data); } > 33 }; > 34 > 35 struct cmp { > 36 int N; > 37 cmp(int N):N(N){} > 38 bool operator()(int a, int b) const > 39 { > 40 if( abs(2*a - N*N) != abs(2*b - N*N) ) > 41 return abs(2*a - N*N) < abs(2*b - N*N); > 42 return a < b; > 43 } > 44 }; > 45 class KingdomAndDice { public: > 46 double newFairness(vector <int> firstDie, vector <int> secondDie, int X) > 47 { > 48 int N = firstDie.size(); > 49 sort(secondDie.begin(), secondDie.end()); > 50 > 51 vector<int> choice; > 52 { > 53 choice.push_back(N); > 54 for(int i=0; i+1<N; ++i) > 55 choice.push_back(secondDie[i+1]-secondDie[i]-1); > 56 choice.push_back(X-secondDie.back()); > 57 } > 58 int base = 0; > 59 { > 60 for(int k=0; k<N; ++k) > 61 if( firstDie[k]!=0 && firstDie[k]<secondDie[0] ) > 62 choice[0] --; > 63 base += 0; > 64 } > 65 for(int i=0; i+1<N; ++i) > 66 for(int k=0; k<N; ++k) > 67 if( firstDie[k]!=0 && secondDie[i]<first > 68 choice[i+1] --; > 69 base += i+1; > 70 } > 71 for(int k=0; k<N; ++k) > 72 if( firstDie[k]!=0 && secondDie[N-1]<firstDie[k] > 73 choice[N] --; > 74 base += N; > 75 } > 76 } > 77 return solve(N, base, choice, count(firstDie.begin(), firstDie.e > 78 } > 79 > 80 double solve(int N, int base, const vector<int>& choice, int K) > 81 { > 82 DP3<int> dp(N+1, K+1, N*N+1); > 83 for(int i=0; i<=N; ++i) > 84 for(int p=0; p<=K; ++p) > 85 for(int sum=0; sum<=N*N; ++sum) > 86 { > 87 if(i==0) > 88 { > 89 dp(i,p,sum) = (sum==base && p<=choice[i]); > 90 } > 91 else > 92 { > 93 bool b = false; > 94 for(int z=0; z<=p && z<=choice[i]; ++z) > 95 if(sum>=i*z) > 96 b = b | dp(i-1,p-z,sum-i*z); > 97 dp(i,p,sum) = b; > 98 } > 99 } > 100 > 101 vector<int> cand; > 102 for(int sum=0; sum<=N*N; ++sum) > 103 if( dp(N,K,sum) ) > 104 cand.push_back( sum ); > 105 return *min_element(cand.begin(), cand.end(), cmp(N)) / double(N > 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 double& Expected, const double& Received) { > 118 bool ok = (abs(Expected - Received) < 1e-9); > 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(_, KingdomAndDice().newFairness(firstDie, secondDie > 123 int main(){ > 124 > 125 CASE(0) > 126 int firstDie_[] = {0, 2, 7, 0}; > 127 vector <int> firstDie(firstDie_, firstDie_+sizeof(firstDie_)/sizeof(*f > 128 int secondDie_[] = {6, 3, 8, 10}; > 129 vector <int> secondDie(secondDie_, secondDie_+sizeof(secondDie_)/sizeo > 130 int X = 12; > 131 double _ = 0.4375; > 132 END > 133 CASE(1) > 134 int firstDie_[] = {0, 2, 7, 0}; > 135 vector <int> firstDie(firstDie_, firstDie_+sizeof(firstDie_)/sizeof(*f > 136 int secondDie_[] = {6, 3, 8, 10}; > 137 vector <int> secondDie(secondDie_, secondDie_+sizeof(secondDie_)/sizeo > 138 int X = 10; > 139 double _ = 0.375; > 140 END > 141 CASE(2) > 142 int firstDie_[] = {0, 0}; > 143 vector <int> firstDie(firstDie_, firstDie_+sizeof(firstDie_)/sizeof(*f > 144 int secondDie_[] = {5, 8}; > 145 vector <int> secondDie(secondDie_, secondDie_+sizeof(secondDie_)/sizeo > 146 int X = 47; > 147 double _ = 0.5; > 148 END > 149 CASE(3) > 150 int firstDie_[] = {19, 50, 4}; > 151 vector <int> firstDie(firstDie_, firstDie_+sizeof(firstDie_)/sizeof(*f > 152 int secondDie_[] = {26, 100, 37}; > 153 vector <int> secondDie(secondDie_, secondDie_+sizeof(secondDie_)/sizeo > 154 int X = 1000; > 155 double _ = 0.2222222222222222; > 156 END > 157 CASE(4) > 158 int firstDie_[] = {6371, 0, 6256, 1852, 0, 0, 6317, 3004, 5218, 9012}; > 159 vector <int> firstDie(firstDie_, firstDie_+sizeof(firstDie_)/sizeof(*f > 160 int secondDie_[] = {1557, 6318, 1560, 4519, 2012, 6316, 6315, 1559, 8215 > 161 vector <int> secondDie(secondDie_, secondDie_+sizeof(secondDie_)/sizeo > 162 int X = 10000; > 163 double _ = 0.49; > 164 END > 165 CASE(5) > 166 int firstDie_[] = {278130165,933636493,607327308,19369203,439158229,4452 > 167 vector <int> firstDie(firstDie_, firstDie_+sizeof(firstDie_)/sizeof(*f > 168 int secondDie_[] = {475017760,773630717,985005264,963668637,320647204,66 > 169 vector <int> secondDie(secondDie_, secondDie_+sizeof(secondDie_)/sizeo > 170 int X = 1000000000; > 171 double _ = 0.5; > 172 END > 173 CASE(6) > 174 int firstDie_[] = {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 > 175 vector <int> firstDie(firstDie_, firstDie_+sizeof(firstDie_)/sizeof(*f > 176 int secondDie_[] = {475017760,773630717,985005264,963668637,320647204,66 > 177 vector <int> secondDie(secondDie_, secondDie_+sizeof(secondDie_)/sizeo > 178 int X = 1000000000; > 179 double _ = 0.5; > 180 END > 181 CASE(6) > 182 int firstDie_[] = {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 > 183 vector <int> firstDie(firstDie_, firstDie_+sizeof(firstDie_)/sizeof(*f > 184 int secondDie_[] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,2 > 185 vector <int> secondDie(secondDie_, secondDie_+sizeof(secondDie_)/sizeo > 186 int X = 100; > 187 double _ = 0.5; > 188 END > 189 CASE(7) > 190 int firstDie_[] = {0,0}; > 191 vector <int> firstDie(firstDie_, firstDie_+sizeof(firstDie_)/sizeof(*f > 192 int secondDie_[] = {1,2}; > 193 vector <int> secondDie(secondDie_, secondDie_+sizeof(secondDie_)/sizeo > 194 int X = 4; > 195 double _ = 1; > 196 END > 197 > 198 } > 199 // END CUT HERE