Overview
| SHA1 Hash: | 17966b23b6094a343114b8ce221084dc743c0b6b |
|---|---|
| Date: | 2015-02-10 15:21:03 |
| User: | kinaba |
| Comment: | 646 |
| 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/646-U/1A.cpp version [8b8fcd4c1b87b026]
> 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 <tuple> > 18 using namespace std; > 19 typedef long long LL; > 20 typedef complex<double> CMP; > 21 > 22 static const char* BAD = "XXX"; > 23 > 24 class AB { public: > 25 map<tuple<int,int,int>, string> memo; > 26 string create(int N, int KPair, int NumB) > 27 { > 28 if(N==0) > 29 return (KPair==0 && NumB==0 ? "" : BAD); > 30 > 31 tuple<int,int,int> key(N, KPair, NumB); > 32 if(memo.count(key)) > 33 return memo[key]; > 34 > 35 auto a = create(N-1, KPair-NumB, NumB); > 36 if(a != BAD) > 37 return memo[key] = "A" + a; > 38 if(NumB>=1) { > 39 auto b = create(N-1, KPair, NumB-1); > 40 if(b != BAD) > 41 return memo[key] = "B" + b; > 42 } > 43 return memo[key] = BAD; > 44 } > 45 > 46 string createString(int N, int K) > 47 { > 48 for(int NumB=0; NumB<=N; ++NumB) { > 49 auto s = create(N, K, NumB); > 50 if(s != BAD) > 51 return s; > 52 } > 53 return ""; > 54 } > 55 }; > 56 > 57 // BEGIN CUT HERE > 58 #include <ctime> > 59 double start_time; string timer() > 60 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 61 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 62 { os << "{ "; > 63 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 64 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 65 void verify_case(const string& Expected, const string& Received) { > 66 bool ok = (Expected == Received); > 67 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 68 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 69 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 70 #define END verify_case(_, AB().createString(N, K));} > 71 int main(){ > 72 > 73 CASE(0) > 74 int N = 3; > 75 int K = 2; > 76 string _ = "ABB"; > 77 END > 78 CASE(1) > 79 int N = 2; > 80 int K = 0; > 81 string _ = "BA"; > 82 END > 83 CASE(2) > 84 int N = 5; > 85 int K = 8; > 86 string _ = ""; > 87 END > 88 CASE(3) > 89 int N = 10; > 90 int K = 12; > 91 string _ = "BAABBABAAB"; > 92 END > 93 /* > 94 CASE(4) > 95 int N = ; > 96 int K = ; > 97 string _ = ; > 98 END > 99 CASE(5) > 100 int N = ; > 101 int K = ; > 102 string _ = ; > 103 END > 104 */ > 105 } > 106 // END CUT HERE
Added SRM/646-U/1B-U.cpp version [2515d87ff53e852d]
> 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 <tuple> > 18 using namespace std; > 19 typedef long long LL; > 20 typedef complex<double> CMP; > 21 > 22 static const unsigned MODVAL = 1000000007; > 23 struct mint > 24 { > 25 unsigned val; > 26 mint():val(0){} > 27 mint(int x):val(x%MODVAL) {} > 28 mint(unsigned 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 mint POW(mint x, LL e) { mint v=1; for(;e;x*=x,e>>=1) if(e&1) v*=x; return v; } > 38 > 39 // cnt, ith > 40 typedef tuple<LL,LL> item; > 41 struct cmp { > 42 bool operator()(const item& lhs, const item& rhs) { > 43 LL e1,b1,e2,b2; > 44 tie(e1,b1) = lhs; > 45 tie(e2,b2) = rhs; > 46 // b1 2^e1 > b2 2^e2 ? > 47 > 48 LL e = abs(e1-e2); > 49 if(e1==e2) > 50 return b1 > b2; > 51 if(e1 > e2) { > 52 // b1 2^e > b2 ? > 53 LL bb=b1; > 54 for(int i=0; i<e; ++i) { > 55 bb *= 2; > 56 if(bb>b2) return true; > 57 } > 58 return false; > 59 } else { > 60 // b1 < b2 2^e ? > 61 LL bb=b2; > 62 for(int i=0; i<e; ++i) { > 63 bb *= 2; > 64 if(b1<bb) return true; > 65 } > 66 return false; > 67 } > 68 } > 69 }; > 70 > 71 class KitayutaMart { public: > 72 int lastPrice(int N, int K) > 73 { > 74 // Invariant: Can buy N apples with max in (K*2^(L-1), K*2^(R-1) > 75 int L=0, R=N; > 76 while(R-L>1) { > 77 int C=(L+R)/2; > 78 (N<=max_buy(K, C) ? R : L) = C; > 79 } > 80 // L+1==R > 81 > 82 // Invariant: Can buy N apples with max in (LL*2^(R-1), RR*2^(R- > 83 int Ll=K/2, RR=K; > 84 while(RR-Ll>1) { > 85 int CC=(Ll+RR)/2; > 86 (N<=max_buy(K, R, CC) ? RR : Ll) = CC; > 87 } > 88 //Ll+1==RR > 89 > 90 // Should be close enough. Do naively. > 91 LL total = K*L + Ll; > 92 > 93 priority_queue<item, vector<item>, cmp> Q; > 94 Q.emplace(R, RR); > 95 int c=R+1; > 96 for(LL div=2;; div*=2,++c) { > 97 total += Ll/div; > 98 Q.emplace(c, Ll/div+1); > 99 if(Ll/div==0) > 100 break; > 101 } > 102 > 103 int ans = 0; > 104 for(; total<=N; ++total) { > 105 LL cnt,ith; > 106 tie(cnt,ith) = Q.top(); > 107 Q.pop(); > 108 > 109 ans = (mint(ith)*POW(2,cnt-1)).val; > 110 > 111 if(ith==1) > 112 Q.emplace(cnt+1,ith); > 113 if(ith<K) > 114 Q.emplace(cnt, ith+1); > 115 } > 116 return ans; > 117 } > 118 > 119 LL max_buy(LL K, LL C) { > 120 return max_buy(K,C,K); > 121 } > 122 > 123 LL max_buy(LL K, LL C, LL Km) { > 124 // Buy many apples with max<=Km*2^(C-1) ? > 125 LL total = K*(C-1) + Km; > 126 for(LL div=2; Km/div>=1; div*=2) > 127 total += Km/div; > 128 return total; > 129 } > 130 }; > 131 > 132 // BEGIN CUT HERE > 133 #include <ctime> > 134 double start_time; string timer() > 135 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 136 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 137 { os << "{ "; > 138 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 139 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 140 void verify_case(const int& Expected, const int& Received) { > 141 bool ok = (Expected == Received); > 142 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 143 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 144 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 145 #define END verify_case(_, KitayutaMart().lastPrice(N, K));} > 146 int main(){ > 147 > 148 CASE(0) > 149 int N = 3; > 150 int K = 1; > 151 int _ = 4; > 152 END > 153 CASE(1) > 154 int N = 3; > 155 int K = 2; > 156 int _ = 2; > 157 END > 158 CASE(2) > 159 int N = 5; > 160 int K = 3; > 161 int _ = 4; > 162 END > 163 CASE(3) > 164 int N = 1000000000; > 165 int K = 1; > 166 int _ = 570312504; > 167 END > 168 CASE(4) > 169 int N = 987654321; > 170 int K = 876543210; > 171 int _ = 493827168; > 172 END > 173 /* > 174 CASE(5) > 175 int N = ; > 176 int K = ; > 177 int _ = ; > 178 END > 179 CASE(6) > 180 int N = ; > 181 int K = ; > 182 int _ = ; > 183 END > 184 */ > 185 } > 186 // END CUT HERE