42b1307ad5 2014-02-15 kinaba: #include <iostream> 42b1307ad5 2014-02-15 kinaba: #include <sstream> 42b1307ad5 2014-02-15 kinaba: #include <iomanip> 42b1307ad5 2014-02-15 kinaba: #include <vector> 42b1307ad5 2014-02-15 kinaba: #include <string> 42b1307ad5 2014-02-15 kinaba: #include <map> 42b1307ad5 2014-02-15 kinaba: #include <set> 42b1307ad5 2014-02-15 kinaba: #include <algorithm> 42b1307ad5 2014-02-15 kinaba: #include <numeric> 42b1307ad5 2014-02-15 kinaba: #include <iterator> 42b1307ad5 2014-02-15 kinaba: #include <functional> 42b1307ad5 2014-02-15 kinaba: #include <complex> 42b1307ad5 2014-02-15 kinaba: #include <queue> 42b1307ad5 2014-02-15 kinaba: #include <stack> 42b1307ad5 2014-02-15 kinaba: #include <cmath> 42b1307ad5 2014-02-15 kinaba: #include <cassert> 42b1307ad5 2014-02-15 kinaba: #include <tuple> 42b1307ad5 2014-02-15 kinaba: using namespace std; 42b1307ad5 2014-02-15 kinaba: typedef long long LL; 42b1307ad5 2014-02-15 kinaba: typedef complex<double> CMP; 42b1307ad5 2014-02-15 kinaba: 42b1307ad5 2014-02-15 kinaba: class MysticAndCandies { public: 42b1307ad5 2014-02-15 kinaba: int minBoxes(int C, int X, vector <int> low, vector <int> high) 42b1307ad5 2014-02-15 kinaba: { 42b1307ad5 2014-02-15 kinaba: sort(low.begin(), low.end()); 42b1307ad5 2014-02-15 kinaba: int t1 = 0, c1 = 0; 42b1307ad5 2014-02-15 kinaba: while(t1 < X) { 42b1307ad5 2014-02-15 kinaba: t1 += low.back(); 42b1307ad5 2014-02-15 kinaba: c1 += 1; 42b1307ad5 2014-02-15 kinaba: low.pop_back(); 42b1307ad5 2014-02-15 kinaba: } 42b1307ad5 2014-02-15 kinaba: 42b1307ad5 2014-02-15 kinaba: sort(high.begin(), high.end()); 42b1307ad5 2014-02-15 kinaba: int t2 = accumulate(high.begin(), high.end(), 0), c2 = 0; 42b1307ad5 2014-02-15 kinaba: while(t2 > C-X) { 42b1307ad5 2014-02-15 kinaba: t2 -= high.back(); 42b1307ad5 2014-02-15 kinaba: c2 += 1; 42b1307ad5 2014-02-15 kinaba: high.pop_back(); 42b1307ad5 2014-02-15 kinaba: } 42b1307ad5 2014-02-15 kinaba: 42b1307ad5 2014-02-15 kinaba: return min(c1, c2); 42b1307ad5 2014-02-15 kinaba: } 42b1307ad5 2014-02-15 kinaba: }; 42b1307ad5 2014-02-15 kinaba: 42b1307ad5 2014-02-15 kinaba: // BEGIN CUT HERE 42b1307ad5 2014-02-15 kinaba: #include <ctime> 42b1307ad5 2014-02-15 kinaba: double start_time; string timer() 42b1307ad5 2014-02-15 kinaba: { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 42b1307ad5 2014-02-15 kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 42b1307ad5 2014-02-15 kinaba: { os << "{ "; 42b1307ad5 2014-02-15 kinaba: for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 42b1307ad5 2014-02-15 kinaba: os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 42b1307ad5 2014-02-15 kinaba: void verify_case(const int& Expected, const int& Received) { 42b1307ad5 2014-02-15 kinaba: bool ok = (Expected == Received); 42b1307ad5 2014-02-15 kinaba: if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 42b1307ad5 2014-02-15 kinaba: cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 42b1307ad5 2014-02-15 kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 42b1307ad5 2014-02-15 kinaba: #define END verify_case(_, MysticAndCandies().minBoxes(C, X, low, high));} 42b1307ad5 2014-02-15 kinaba: int main(){ 42b1307ad5 2014-02-15 kinaba: 42b1307ad5 2014-02-15 kinaba: CASE(0) 42b1307ad5 2014-02-15 kinaba: int C = 15; 42b1307ad5 2014-02-15 kinaba: int X = 12; 42b1307ad5 2014-02-15 kinaba: int low_[] = {1, 2, 3, 4, 5}; 42b1307ad5 2014-02-15 kinaba: vector <int> low(low_, low_+sizeof(low_)/sizeof(*low_)); 42b1307ad5 2014-02-15 kinaba: int high_[] = {1, 2, 3, 4, 5}; 42b1307ad5 2014-02-15 kinaba: vector <int> high(high_, high_+sizeof(high_)/sizeof(*high_)); 42b1307ad5 2014-02-15 kinaba: int _ = 3; 42b1307ad5 2014-02-15 kinaba: END 42b1307ad5 2014-02-15 kinaba: CASE(1) 42b1307ad5 2014-02-15 kinaba: int C = 60; 42b1307ad5 2014-02-15 kinaba: int X = 8; 42b1307ad5 2014-02-15 kinaba: int low_[] = {5, 2, 3}; 42b1307ad5 2014-02-15 kinaba: vector <int> low(low_, low_+sizeof(low_)/sizeof(*low_)); 42b1307ad5 2014-02-15 kinaba: int high_[] = {49, 48, 47}; 42b1307ad5 2014-02-15 kinaba: vector <int> high(high_, high_+sizeof(high_)/sizeof(*high_)); 42b1307ad5 2014-02-15 kinaba: int _ = 2; 42b1307ad5 2014-02-15 kinaba: END 42b1307ad5 2014-02-15 kinaba: CASE(2) 42b1307ad5 2014-02-15 kinaba: int C = 58; 42b1307ad5 2014-02-15 kinaba: int X = 30; 42b1307ad5 2014-02-15 kinaba: int low_[] = {3, 9, 12, 6, 15}; 42b1307ad5 2014-02-15 kinaba: vector <int> low(low_, low_+sizeof(low_)/sizeof(*low_)); 42b1307ad5 2014-02-15 kinaba: int high_[] = {8, 12, 20, 8, 15}; 42b1307ad5 2014-02-15 kinaba: vector <int> high(high_, high_+sizeof(high_)/sizeof(*high_)); 42b1307ad5 2014-02-15 kinaba: int _ = 2; 42b1307ad5 2014-02-15 kinaba: END 42b1307ad5 2014-02-15 kinaba: CASE(3) 42b1307ad5 2014-02-15 kinaba: int C = 207581165; 42b1307ad5 2014-02-15 kinaba: int X = 172146543; 42b1307ad5 2014-02-15 kinaba: int low_[] = {4725448, 2753824, 6019698, 4199708, 4070001, 3589497, 5358499, 3637585, 5393667, 2837466, 42b1307ad5 2014-02-15 kinaba: 2747807, 2918199, 3638042, 5199002, 3072044, 3858909, 3762101, 3657754, 3218704, 3888861, 42b1307ad5 2014-02-15 kinaba: 3195689, 4768935, 3137633, 4124272, 4125056, 6087486, 3632970, 3620489, 2748765, 5917493, 42b1307ad5 2014-02-15 kinaba: 3958996, 3335021, 3517186, 5543440, 2951006, 3403270, 3299481, 3093204, 4092331}; 42b1307ad5 2014-02-15 kinaba: vector <int> low(low_, low_+sizeof(low_)/sizeof(*low_)); 42b1307ad5 2014-02-15 kinaba: int high_[] = {5702812, 6805664, 6823687, 5337687, 4286533, 4999849, 6567411, 4563235, 6618139, 6260135, 42b1307ad5 2014-02-15 kinaba: 6249469, 3821449, 5963157, 6385012, 4255959, 5786920, 6112817, 4103918, 6371537, 4231698, 42b1307ad5 2014-02-15 kinaba: 3409172, 6806782, 5623563, 4511221, 6407338, 6491490, 5209517, 6076093, 6530132, 6111464, 42b1307ad5 2014-02-15 kinaba: 5833839, 6253088, 5595160, 6236805, 5772388, 5285713, 5617002, 4650978, 5234740}; 42b1307ad5 2014-02-15 kinaba: vector <int> high(high_, high_+sizeof(high_)/sizeof(*high_)); 42b1307ad5 2014-02-15 kinaba: int _ = 31; 42b1307ad5 2014-02-15 kinaba: END 42b1307ad5 2014-02-15 kinaba: CASE(4) 42b1307ad5 2014-02-15 kinaba: int C = 43873566; 42b1307ad5 2014-02-15 kinaba: int X = 32789748; 42b1307ad5 2014-02-15 kinaba: int low_[] = {2053198, 2175819, 4260803, 1542497, 1418952, 5000015, 1381849, 2462882, 6466891, 1827580, 6943641, 5775477}; 42b1307ad5 2014-02-15 kinaba: vector <int> low(low_, low_+sizeof(low_)/sizeof(*low_)); 42b1307ad5 2014-02-15 kinaba: int high_[] = {2827461, 3726335, 5410505, 4781355, 4925909, 5621160, 7325774, 5025476, 7876037, 8072075, 6979462, 6647628}; 42b1307ad5 2014-02-15 kinaba: vector <int> high(high_, high_+sizeof(high_)/sizeof(*high_)); 42b1307ad5 2014-02-15 kinaba: int _ = 7; 42b1307ad5 2014-02-15 kinaba: END 42b1307ad5 2014-02-15 kinaba: /* 42b1307ad5 2014-02-15 kinaba: CASE(5) 42b1307ad5 2014-02-15 kinaba: int C = ; 42b1307ad5 2014-02-15 kinaba: int X = ; 42b1307ad5 2014-02-15 kinaba: int low_[] = ; 42b1307ad5 2014-02-15 kinaba: vector <int> low(low_, low_+sizeof(low_)/sizeof(*low_)); 42b1307ad5 2014-02-15 kinaba: int high_[] = ; 42b1307ad5 2014-02-15 kinaba: vector <int> high(high_, high_+sizeof(high_)/sizeof(*high_)); 42b1307ad5 2014-02-15 kinaba: int _ = ; 42b1307ad5 2014-02-15 kinaba: END 42b1307ad5 2014-02-15 kinaba: CASE(6) 42b1307ad5 2014-02-15 kinaba: int C = ; 42b1307ad5 2014-02-15 kinaba: int X = ; 42b1307ad5 2014-02-15 kinaba: int low_[] = ; 42b1307ad5 2014-02-15 kinaba: vector <int> low(low_, low_+sizeof(low_)/sizeof(*low_)); 42b1307ad5 2014-02-15 kinaba: int high_[] = ; 42b1307ad5 2014-02-15 kinaba: vector <int> high(high_, high_+sizeof(high_)/sizeof(*high_)); 42b1307ad5 2014-02-15 kinaba: int _ = ; 42b1307ad5 2014-02-15 kinaba: END 42b1307ad5 2014-02-15 kinaba: */ 42b1307ad5 2014-02-15 kinaba: } 42b1307ad5 2014-02-15 kinaba: // END CUT HERE