4a28d1c3b1 2015-02-18 kinaba: #include <iostream> 4a28d1c3b1 2015-02-18 kinaba: #include <sstream> 4a28d1c3b1 2015-02-18 kinaba: #include <iomanip> 4a28d1c3b1 2015-02-18 kinaba: #include <vector> 4a28d1c3b1 2015-02-18 kinaba: #include <string> 4a28d1c3b1 2015-02-18 kinaba: #include <map> 4a28d1c3b1 2015-02-18 kinaba: #include <set> 4a28d1c3b1 2015-02-18 kinaba: #include <algorithm> 4a28d1c3b1 2015-02-18 kinaba: #include <numeric> 4a28d1c3b1 2015-02-18 kinaba: #include <iterator> 4a28d1c3b1 2015-02-18 kinaba: #include <functional> 4a28d1c3b1 2015-02-18 kinaba: #include <complex> 4a28d1c3b1 2015-02-18 kinaba: #include <queue> 4a28d1c3b1 2015-02-18 kinaba: #include <stack> 4a28d1c3b1 2015-02-18 kinaba: #include <cmath> 4a28d1c3b1 2015-02-18 kinaba: #include <cassert> 4a28d1c3b1 2015-02-18 kinaba: #include <tuple> 4a28d1c3b1 2015-02-18 kinaba: using namespace std; 4a28d1c3b1 2015-02-18 kinaba: typedef long long LL; 4a28d1c3b1 2015-02-18 kinaba: typedef complex<double> CMP; 4a28d1c3b1 2015-02-18 kinaba: 4a28d1c3b1 2015-02-18 kinaba: class CartInSupermarket { public: 4a28d1c3b1 2015-02-18 kinaba: int calcmin(vector <int> a, int b) 4a28d1c3b1 2015-02-18 kinaba: { 4a28d1c3b1 2015-02-18 kinaba: int L=0, R=*max_element(a.begin(), a.end()); // can do in (L,R] minutes 4a28d1c3b1 2015-02-18 kinaba: while(R-L>1) { 4a28d1c3b1 2015-02-18 kinaba: int C = (L+R)/2; 4a28d1c3b1 2015-02-18 kinaba: (can(a,b,C) ? R : L) = C; 4a28d1c3b1 2015-02-18 kinaba: } 4a28d1c3b1 2015-02-18 kinaba: return R; 4a28d1c3b1 2015-02-18 kinaba: } 4a28d1c3b1 2015-02-18 kinaba: 4a28d1c3b1 2015-02-18 kinaba: bool can(vector<int> a, int b, int C) { 4a28d1c3b1 2015-02-18 kinaba: int sp = 0; 4a28d1c3b1 2015-02-18 kinaba: for(auto ai: a) { 4a28d1c3b1 2015-02-18 kinaba: int spx; 4a28d1c3b1 2015-02-18 kinaba: if(!need_split(ai, C, &spx)) 4a28d1c3b1 2015-02-18 kinaba: return false; 4a28d1c3b1 2015-02-18 kinaba: sp += spx; 4a28d1c3b1 2015-02-18 kinaba: } 4a28d1c3b1 2015-02-18 kinaba: return sp <= b; 4a28d1c3b1 2015-02-18 kinaba: } 4a28d1c3b1 2015-02-18 kinaba: 4a28d1c3b1 2015-02-18 kinaba: // Can we process A in C minutes? If so, return minimal necessary split to *spx. 4a28d1c3b1 2015-02-18 kinaba: bool need_split(int A, int C, int* spx) { 4a28d1c3b1 2015-02-18 kinaba: LL preM = 0; 4a28d1c3b1 2015-02-18 kinaba: for(int b=max(0,A/C-1) ;; ++b) { 4a28d1c3b1 2015-02-18 kinaba: LL M = cover(C, b); 4a28d1c3b1 2015-02-18 kinaba: if(M <= preM) 4a28d1c3b1 2015-02-18 kinaba: return false; 4a28d1c3b1 2015-02-18 kinaba: preM = M; 4a28d1c3b1 2015-02-18 kinaba: if(A<=M) { 4a28d1c3b1 2015-02-18 kinaba: *spx = b; 4a28d1c3b1 2015-02-18 kinaba: return true; 4a28d1c3b1 2015-02-18 kinaba: } 4a28d1c3b1 2015-02-18 kinaba: } 4a28d1c3b1 2015-02-18 kinaba: } 4a28d1c3b1 2015-02-18 kinaba: 4a28d1c3b1 2015-02-18 kinaba: // C minutes, b splits. How many we can cover. 4a28d1c3b1 2015-02-18 kinaba: LL cover(int C, int b) { 4a28d1c3b1 2015-02-18 kinaba: vector<pair<int,int>> stock(1, make_pair(C,1)); 4a28d1c3b1 2015-02-18 kinaba: while(b) { 4a28d1c3b1 2015-02-18 kinaba: if(b>=stock[0].second) { 4a28d1c3b1 2015-02-18 kinaba: b -= stock[0].second; 4a28d1c3b1 2015-02-18 kinaba: stock[0] = make_pair(stock[0].first-1, stock[0].second*2); 4a28d1c3b1 2015-02-18 kinaba: } else { 4a28d1c3b1 2015-02-18 kinaba: stock[0].second -= b; 4a28d1c3b1 2015-02-18 kinaba: stock.emplace_back(stock[0].first-1, b*2); 4a28d1c3b1 2015-02-18 kinaba: break; 4a28d1c3b1 2015-02-18 kinaba: } 4a28d1c3b1 2015-02-18 kinaba: } 4a28d1c3b1 2015-02-18 kinaba: 4a28d1c3b1 2015-02-18 kinaba: LL ans = 0; 4a28d1c3b1 2015-02-18 kinaba: for(auto cn: stock) { 4a28d1c3b1 2015-02-18 kinaba: if(cn.first<=0) 4a28d1c3b1 2015-02-18 kinaba: return -1; 4a28d1c3b1 2015-02-18 kinaba: ans += LL(cn.first)*cn.second; 4a28d1c3b1 2015-02-18 kinaba: } 4a28d1c3b1 2015-02-18 kinaba: return ans; 4a28d1c3b1 2015-02-18 kinaba: } 4a28d1c3b1 2015-02-18 kinaba: }; 4a28d1c3b1 2015-02-18 kinaba: 4a28d1c3b1 2015-02-18 kinaba: // BEGIN CUT HERE 4a28d1c3b1 2015-02-18 kinaba: #include <ctime> 4a28d1c3b1 2015-02-18 kinaba: double start_time; string timer() 4a28d1c3b1 2015-02-18 kinaba: { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 4a28d1c3b1 2015-02-18 kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 4a28d1c3b1 2015-02-18 kinaba: { os << "{ "; 4a28d1c3b1 2015-02-18 kinaba: for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 4a28d1c3b1 2015-02-18 kinaba: os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 4a28d1c3b1 2015-02-18 kinaba: void verify_case(const int& Expected, const int& Received) { 4a28d1c3b1 2015-02-18 kinaba: bool ok = (Expected == Received); 4a28d1c3b1 2015-02-18 kinaba: if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 4a28d1c3b1 2015-02-18 kinaba: cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 4a28d1c3b1 2015-02-18 kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 4a28d1c3b1 2015-02-18 kinaba: #define END verify_case(_, CartInSupermarket().calcmin(a, b));} 4a28d1c3b1 2015-02-18 kinaba: int main(){ 4a28d1c3b1 2015-02-18 kinaba: 4a28d1c3b1 2015-02-18 kinaba: CASE(0) 4a28d1c3b1 2015-02-18 kinaba: int a_[] = {8}; 4a28d1c3b1 2015-02-18 kinaba: vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); 4a28d1c3b1 2015-02-18 kinaba: int b = 3; 4a28d1c3b1 2015-02-18 kinaba: int _ = 4; 4a28d1c3b1 2015-02-18 kinaba: END 4a28d1c3b1 2015-02-18 kinaba: CASE(1) 4a28d1c3b1 2015-02-18 kinaba: int a_[] = {6,6,5}; 4a28d1c3b1 2015-02-18 kinaba: vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); 4a28d1c3b1 2015-02-18 kinaba: int b = 3; 4a28d1c3b1 2015-02-18 kinaba: int _ = 4; 4a28d1c3b1 2015-02-18 kinaba: END 4a28d1c3b1 2015-02-18 kinaba: CASE(2) 4a28d1c3b1 2015-02-18 kinaba: int a_[] = {12,5,6,2,6,8}; 4a28d1c3b1 2015-02-18 kinaba: vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); 4a28d1c3b1 2015-02-18 kinaba: int b = 4; 4a28d1c3b1 2015-02-18 kinaba: int _ = 6; 4a28d1c3b1 2015-02-18 kinaba: END 4a28d1c3b1 2015-02-18 kinaba: CASE(3) 4a28d1c3b1 2015-02-18 kinaba: int a_[] = {15,20,11,13,18,24,25,21,22,10,15,14,19}; 4a28d1c3b1 2015-02-18 kinaba: vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); 4a28d1c3b1 2015-02-18 kinaba: int b = 0; 4a28d1c3b1 2015-02-18 kinaba: int _ = 25; 4a28d1c3b1 2015-02-18 kinaba: END 4a28d1c3b1 2015-02-18 kinaba: CASE(4) 4a28d1c3b1 2015-02-18 kinaba: int a_[] = {671122748,846444748,84701624,608579554,672060899,967957440,31438849,734849843,376589643,904285209 4a28d1c3b1 2015-02-18 kinaba: ,80693344,211737743,85405464,444633541,293184188,935462519,146753109,972886045,496631016,601669536 4a28d1c3b1 2015-02-18 kinaba: ,257574086,958464570,6294570,546189534,668105964,601197313,784337929,921840143,70408284,722040626 4a28d1c3b1 2015-02-18 kinaba: ,253400894,56411549,811940644,152086353,122638884,776352066,118932182,177589709,538122558,127914469 4a28d1c3b1 2015-02-18 kinaba: ,523761221,290027568,734517444,819458123,699130727,784698122,810265337,283326309,593596316,368671876}; 4a28d1c3b1 2015-02-18 kinaba: vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); 4a28d1c3b1 2015-02-18 kinaba: int b = 6478; 4a28d1c3b1 2015-02-18 kinaba: int _ = 3805054; 4a28d1c3b1 2015-02-18 kinaba: END 4a28d1c3b1 2015-02-18 kinaba: CASE(5) 4a28d1c3b1 2015-02-18 kinaba: int a_[] = {977827843, 601538780, 476956916, 821358251, 646377015, 479421294, 631863623, 446866211, 147800371, 777376159, 997915782, 317155640, 611683333, 461303085, 473215018, 363166652, 39746841, 109934430, 391345044, 41220128, 379970887, 445787345, 801764390, 886145854, 494435459, 974163022, 126739284, 708338618, 775199509, 378383243, 928615727, 606884963}; 4a28d1c3b1 2015-02-18 kinaba: vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); 4a28d1c3b1 2015-02-18 kinaba: int b = 278304610; 4a28d1c3b1 2015-02-18 kinaba: int _ = -1; 4a28d1c3b1 2015-02-18 kinaba: END 4a28d1c3b1 2015-02-18 kinaba: 4a28d1c3b1 2015-02-18 kinaba: /* 4a28d1c3b1 2015-02-18 kinaba: CASE(6) 4a28d1c3b1 2015-02-18 kinaba: int a_[] = ; 4a28d1c3b1 2015-02-18 kinaba: vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); 4a28d1c3b1 2015-02-18 kinaba: int b = ; 4a28d1c3b1 2015-02-18 kinaba: int _ = ; 4a28d1c3b1 2015-02-18 kinaba: END 4a28d1c3b1 2015-02-18 kinaba: */ 4a28d1c3b1 2015-02-18 kinaba: } 4a28d1c3b1 2015-02-18 kinaba: // END CUT HERE