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) << " msec)"; return os.str(); } 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 os; } 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() << endl; 60 - cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 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(*heights_)); 68 - int _ = 3; 69 -END 70 -CASE(1) 71 - int heights_[] = {5, 8}; 72 - vector <int> heights(heights_, heights_+sizeof(heights_)/sizeof(*heights_)); 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(*heights_)); 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(*heights_)); 83 - int _ = 251; 84 -END 85 -CASE(4) 86 - int heights_[] = {337994619,837714986,7014426,516695490,268514071,590654553,940024470,79308071,891444369,231310251,172567010,283491054,951215936,92716118,911004789,896372476,617116292,874491895,120052194,635772188,938392572,466867891,418351197,278475278,635224368,38779964,762367612,370214557,20108108,314281202,644947239,868648377,617056931,542328796,280916141,281585869,895175595,529854516,862330692,733665485,173060292,579136324,401396401,303236137,161627936,410922706,172892990,840336279,848958999,849348801}; 87 - vector <int> heights(heights_, heights_+sizeof(heights_)/sizeof(*heights_)); 88 - int _ = -1; 89 -END 90 -CASE(5) 91 - int heights_[] = {1000000000,1}; 92 - vector <int> heights(heights_, heights_+sizeof(heights_)/sizeof(*heights_)); 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()*sizeof(T)<(1<<26)); } 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]<firstDie[k] && firstDie[k]<secondDie[i+1] ) { 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.end(), 0)); 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*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) << " msec)"; return os.str(); } 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 os; } 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() << endl; 120 - cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 121 -#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 122 -#define END verify_case(_, KingdomAndDice().newFairness(firstDie, secondDie, X));} 123 -int main(){ 124 - 125 -CASE(0) 126 - int firstDie_[] = {0, 2, 7, 0}; 127 - vector <int> firstDie(firstDie_, firstDie_+sizeof(firstDie_)/sizeof(*firstDie_)); 128 - int secondDie_[] = {6, 3, 8, 10}; 129 - vector <int> secondDie(secondDie_, secondDie_+sizeof(secondDie_)/sizeof(*secondDie_)); 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(*firstDie_)); 136 - int secondDie_[] = {6, 3, 8, 10}; 137 - vector <int> secondDie(secondDie_, secondDie_+sizeof(secondDie_)/sizeof(*secondDie_)); 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(*firstDie_)); 144 - int secondDie_[] = {5, 8}; 145 - vector <int> secondDie(secondDie_, secondDie_+sizeof(secondDie_)/sizeof(*secondDie_)); 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(*firstDie_)); 152 - int secondDie_[] = {26, 100, 37}; 153 - vector <int> secondDie(secondDie_, secondDie_+sizeof(secondDie_)/sizeof(*secondDie_)); 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(*firstDie_)); 160 - int secondDie_[] = {1557, 6318, 1560, 4519, 2012, 6316, 6315, 1559, 8215, 1561}; 161 - vector <int> secondDie(secondDie_, secondDie_+sizeof(secondDie_)/sizeof(*secondDie_)); 162 - int X = 10000; 163 - double _ = 0.49; 164 -END 165 -CASE(5) 166 - int firstDie_[] = {278130165,933636493,607327308,19369203,439158229,445295066,370731340,551180273,163280323,359800317,834663837,108871632,362106962,921853660,145507840,284869553,246938492,379648759,956330140,525562675,251028940,270135098,862786589,513909283,412651940,499422899,724171306,922270222,938213346,61418124,248820926,891527589,812074952,155495258,23280465,761818758,328244247,975585791,108105856,414583437,424242761,168720992,585728188,0,0,0,0,0,0,0}; 167 - vector <int> firstDie(firstDie_, firstDie_+sizeof(firstDie_)/sizeof(*firstDie_)); 168 - int secondDie_[] = {475017760,773630717,985005264,963668637,320647204,665487259,585555327,272107932,203172682,57845645,311126817,496577583,834654861,77335024,405827438,231342594,943378345,971851607,455697802,119475931,551079372,838525393,192593102,990828850,382044077,590561977,229071016,962163538,621629435,727621063,109926457,152882146,9199017,615779540,160320904,216276208,675743894,414050471,126645085,238141513,151262148,280509327,923103663,125699296,790073355,738597671,864455279,384833125,510401421,219630179}; 169 - vector <int> secondDie(secondDie_, secondDie_+sizeof(secondDie_)/sizeof(*secondDie_)); 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,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(*firstDie_)); 176 - int secondDie_[] = {475017760,773630717,985005264,963668637,320647204,665487259,585555327,272107932,203172682,57845645,311126817,496577583,834654861,77335024,405827438,231342594,943378345,971851607,455697802,119475931,551079372,838525393,192593102,990828850,382044077,590561977,229071016,962163538,621629435,727621063,109926457,152882146,9199017,615779540,160320904,216276208,675743894,414050471,126645085,238141513,151262148,280509327,923103663,125699296,790073355,738597671,864455279,384833125,510401421,219630179}; 177 - vector <int> secondDie(secondDie_, secondDie_+sizeof(secondDie_)/sizeof(*secondDie_)); 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,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(*firstDie_)); 184 - int secondDie_[] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50}; 185 - vector <int> secondDie(secondDie_, secondDie_+sizeof(secondDie_)/sizeof(*secondDie_)); 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(*firstDie_)); 192 - int secondDie_[] = {1,2}; 193 - vector <int> secondDie(secondDie_, secondDie_+sizeof(secondDie_)/sizeof(*secondDie_)); 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(N-NA, K-KA); 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-2-KA); 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-NA,K-2-KA); 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-KA); 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) << " msec)"; return os.str(); } 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 os; } 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() << endl; 110 + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 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