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) << " msec)"; return os.str(); } 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 os; } 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() << endl; 68 - cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 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-1)] 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) << " msec)"; return os.str(); } 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 os; } 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() << endl; 143 - cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 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.