Overview
| SHA1 Hash: | ddf2358d33f6229f3672a35c69a7847237f95609 |
|---|---|
| Date: | 2012-08-08 14:26:16 |
| User: | kinaba |
| Comment: | 548 1C solved. |
| 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
Deleted 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 <
Deleted 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 <
Name change from from SRM/548-U/1A.cpp to SRM/548/1A.cpp.
Name change from from SRM/548-U/1B.cpp to SRM/548/1B.cpp.
Added SRM/548/1C.cpp version [7fa2189be95e994e]
> 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 static const int MODVAL = 1000000007; > 23 struct mint > 24 { > 25 int val; > 26 mint():val(0){} > 27 mint(int x):val(x%MODVAL) {} > 28 mint(size_t x):val(x%MODVAL) {} > 29 mint(LL x):val(x%MODVAL) {} > 30 }; > 31 mint& operator+=(mint& x, mint y) { return x = x.val+y.val; } > 32 mint& operator-=(mint& x, mint y) { return x = x.val-y.val+MODVAL; } > 33 mint& operator*=(mint& x, mint y) { return x = LL(x.val)*y.val; } > 34 mint operator+(mint x, mint y) { return x+=y; } > 35 mint operator-(mint x, mint y) { return x-=y; } > 36 mint operator*(mint x, mint y) { return x*=y; } > 37 vector< vector<mint> > CP_; > 38 mint C(LL n, LL k) { > 39 while( CP_.size() <= n ) { > 40 int nn = CP_.size(); > 41 CP_.push_back(vector<mint>(nn+1,1)); > 42 for(int kk=1; kk<nn; ++kk) > 43 CP_[nn][kk] = CP_[nn-1][kk-1] + CP_[nn-1][kk]; > 44 } > 45 return k<0 || n<k ? 0 : CP_[n][k]; > 46 } > 47 > 48 class KingdomAndCities { public: > 49 int howMany(int N, int M, int K) > 50 { > 51 if( M == 0 ) return zero(N, K).val; > 52 if( M == 1 ) return one(N, K).val; > 53 return two(N, K).val; > 54 } > 55 > 56 mint zero_may_be_disconnected(int N, int K) > 57 { > 58 return C(N*(N-1)/2, K); > 59 } > 60 > 61 map<pair<int,int>, mint> memo; > 62 mint zero(int N, int K) > 63 { > 64 pair<int,int> key(N, K); > 65 if(memo.count(key)) > 66 return memo[key]; > 67 > 68 mint sum = zero_may_be_disconnected(N, K); > 69 for(int NA=1; NA<=N-1; ++NA) > 70 for(int KA=0; KA<=K; ++KA) > 71 sum -= C(N-1,NA-1)*zero(NA,KA)*zero_may_be_disconnected( > 72 return memo[key] = sum; > 73 } > 74 > 75 mint one(int N, int K) > 76 { > 77 mint sum = zero(N-1,K-2)*C(N-1,2); > 78 for(int NA=1; NA<=N-2; ++NA) > 79 for(int KA=0; KA<=K-2; ++KA) > 80 sum += C(N-2,NA-1)*zero(NA,KA)*NA*(N-1-NA)*zero(N-1-NA,K > 81 return sum; > 82 } > 83 > 84 mint two(int N, int K) > 85 { > 86 mint sum = one(N-1,K-2)*C(N-2,2); > 87 for(int NA=1; NA<=N-2; ++NA) > 88 for(int KA=0; KA<=K-2; ++KA) > 89 sum += C(N-2,NA-1)*one(NA,KA)*(NA-1)*(N-1-NA)*zero(N-1-N > 90 --N, --K; > 91 sum += zero(N-1,K-2)*(N-1)*(N-1); > 92 for(int NA=1; NA<=N-2; ++NA) > 93 for(int KA=0; KA<=K-2; ++KA) > 94 sum += C(N-1,NA)*zero(NA,KA)*NA*(N-1-NA)*zero(N-1-NA,K-2 > 95 return sum; > 96 } > 97 }; > 98 > 99 // BEGIN CUT HERE > 100 #include <ctime> > 101 double start_time; string timer() > 102 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 103 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 104 { os << "{ "; > 105 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 106 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 107 void verify_case(const int& Expected, const int& Received) { > 108 bool ok = (Expected == Received); > 109 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 110 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 111 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 112 #define END verify_case(_, KingdomAndCities().howMany(N, M, K));} > 113 int main(){ > 114 > 115 CASE(0) > 116 int N = 3; > 117 int M = 0; > 118 int K = 3; > 119 int _ = 1; > 120 END > 121 CASE(1) > 122 int N = 4; > 123 int M = 1; > 124 int K = 4; > 125 int _ = 9; > 126 END > 127 CASE(2) > 128 int N = 5; > 129 int M = 2; > 130 int K = 11; > 131 int _ = 0; > 132 END > 133 CASE(3) > 134 int N = 5; > 135 int M = 0; > 136 int K = 8; > 137 int _ = 45; > 138 END > 139 CASE(4) > 140 int N = 10; > 141 int M = 2; > 142 int K = 20; > 143 int _ = 150810825; > 144 END > 145 CASE(5) > 146 int N = 3; > 147 int M = 2; > 148 int K = 3; > 149 int _ = 1; > 150 END > 151 /* > 152 CASE(6) > 153 int N = ; > 154 int M = ; > 155 int K = ; > 156 int _ = ; > 157 END > 158 */ > 159 } > 160 // END CUT HERE