Overview
| SHA1 Hash: | 16853a9ca72f75c1cffe2054508b4768a52f348c |
|---|---|
| Date: | 2015-02-10 15:22:39 |
| User: | kinaba |
| Comment: | 648 datta. |
| 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/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 <
Deleted 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 <
Name change from from SRM/646-U/1A.cpp to SRM/648-U/1A.cpp.
Name change from from SRM/646-U/1B-U.cpp to SRM/648-U/1B-U.cpp.