aca31be9a5 2011-12-24 kinaba: #include <iostream> aca31be9a5 2011-12-24 kinaba: #include <sstream> aca31be9a5 2011-12-24 kinaba: #include <iomanip> aca31be9a5 2011-12-24 kinaba: #include <vector> aca31be9a5 2011-12-24 kinaba: #include <string> aca31be9a5 2011-12-24 kinaba: #include <map> aca31be9a5 2011-12-24 kinaba: #include <set> aca31be9a5 2011-12-24 kinaba: #include <algorithm> aca31be9a5 2011-12-24 kinaba: #include <numeric> aca31be9a5 2011-12-24 kinaba: #include <iterator> aca31be9a5 2011-12-24 kinaba: #include <functional> aca31be9a5 2011-12-24 kinaba: #include <complex> aca31be9a5 2011-12-24 kinaba: #include <queue> aca31be9a5 2011-12-24 kinaba: #include <stack> aca31be9a5 2011-12-24 kinaba: #include <cmath> aca31be9a5 2011-12-24 kinaba: #include <cassert> aca31be9a5 2011-12-24 kinaba: #include <cstring> aca31be9a5 2011-12-24 kinaba: #ifdef __GNUC__ aca31be9a5 2011-12-24 kinaba: #include <ext/hash_map> aca31be9a5 2011-12-24 kinaba: #define unordered_map __gnu_cxx::hash_map aca31be9a5 2011-12-24 kinaba: #else aca31be9a5 2011-12-24 kinaba: #include <unordered_map> aca31be9a5 2011-12-24 kinaba: #endif aca31be9a5 2011-12-24 kinaba: using namespace std; aca31be9a5 2011-12-24 kinaba: typedef long long LL; aca31be9a5 2011-12-24 kinaba: typedef complex<double> CMP; aca31be9a5 2011-12-24 kinaba: aca31be9a5 2011-12-24 kinaba: class P8XCoinChangeAnother { public: aca31be9a5 2011-12-24 kinaba: vector<long long> solve(int N, long long coins_sum, long long coins_count) aca31be9a5 2011-12-24 kinaba: { aca31be9a5 2011-12-24 kinaba: vector<LL> result; aca31be9a5 2011-12-24 kinaba: for(int i=0; i<N; ++i) { aca31be9a5 2011-12-24 kinaba: LL tick = i==N-1 ? coins_sum>>i : ((1LL<<i)&coins_sum ? 1 : 0); aca31be9a5 2011-12-24 kinaba: result.push_back( tick ); aca31be9a5 2011-12-24 kinaba: coins_count -= tick; aca31be9a5 2011-12-24 kinaba: } aca31be9a5 2011-12-24 kinaba: if( coins_count < 0 ) aca31be9a5 2011-12-24 kinaba: return vector<LL>(); aca31be9a5 2011-12-24 kinaba: aca31be9a5 2011-12-24 kinaba: for(int i=N-1; i>0; --i) { aca31be9a5 2011-12-24 kinaba: if( coins_count == 0 ) aca31be9a5 2011-12-24 kinaba: return result; aca31be9a5 2011-12-24 kinaba: else { aca31be9a5 2011-12-24 kinaba: LL& me = result[i]; aca31be9a5 2011-12-24 kinaba: LL dec = min(me, coins_count); aca31be9a5 2011-12-24 kinaba: me -= dec; aca31be9a5 2011-12-24 kinaba: result[i-1] += dec*2; aca31be9a5 2011-12-24 kinaba: coins_count -= dec; aca31be9a5 2011-12-24 kinaba: } aca31be9a5 2011-12-24 kinaba: } aca31be9a5 2011-12-24 kinaba: return coins_count == 0 ? result : vector<LL>(); aca31be9a5 2011-12-24 kinaba: } aca31be9a5 2011-12-24 kinaba: }; aca31be9a5 2011-12-24 kinaba: aca31be9a5 2011-12-24 kinaba: // BEGIN CUT HERE aca31be9a5 2011-12-24 kinaba: #include <ctime> aca31be9a5 2011-12-24 kinaba: double start_time; string timer() aca31be9a5 2011-12-24 kinaba: { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } aca31be9a5 2011-12-24 kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) aca31be9a5 2011-12-24 kinaba: { os << "{ "; aca31be9a5 2011-12-24 kinaba: for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) aca31be9a5 2011-12-24 kinaba: os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } aca31be9a5 2011-12-24 kinaba: void verify_case(const vector<long long>& Expected, const vector<long long>& Received) { aca31be9a5 2011-12-24 kinaba: bool ok = (Expected == Received); aca31be9a5 2011-12-24 kinaba: if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; aca31be9a5 2011-12-24 kinaba: cerr << "\to: " << Expected << endl << "\tx: " << Received << endl; } } aca31be9a5 2011-12-24 kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); aca31be9a5 2011-12-24 kinaba: #define END verify_case(_, P8XCoinChangeAnother().solve(N, coins_sum, coins_count));} aca31be9a5 2011-12-24 kinaba: int main(){ aca31be9a5 2011-12-24 kinaba: aca31be9a5 2011-12-24 kinaba: CASE(0) aca31be9a5 2011-12-24 kinaba: int N = 2; aca31be9a5 2011-12-24 kinaba: long long coins_sum = 4LL; aca31be9a5 2011-12-24 kinaba: long long coins_count = 3LL; aca31be9a5 2011-12-24 kinaba: long long __[] = {2, 1 }; aca31be9a5 2011-12-24 kinaba: vector<long long> _(__, __+sizeof(__)/sizeof(*__)); aca31be9a5 2011-12-24 kinaba: END aca31be9a5 2011-12-24 kinaba: CASE(1) aca31be9a5 2011-12-24 kinaba: int N = 3; aca31be9a5 2011-12-24 kinaba: long long coins_sum = 6LL; aca31be9a5 2011-12-24 kinaba: long long coins_count = 3LL; aca31be9a5 2011-12-24 kinaba: long long __[] = {0, 3, 0 }; aca31be9a5 2011-12-24 kinaba: vector<long long> _(__, __+sizeof(__)/sizeof(*__)); aca31be9a5 2011-12-24 kinaba: END aca31be9a5 2011-12-24 kinaba: CASE(2) aca31be9a5 2011-12-24 kinaba: int N = 2; aca31be9a5 2011-12-24 kinaba: long long coins_sum = 8LL; aca31be9a5 2011-12-24 kinaba: long long coins_count = 1LL; aca31be9a5 2011-12-24 kinaba: vector<long long> _; aca31be9a5 2011-12-24 kinaba: END aca31be9a5 2011-12-24 kinaba: CASE(3) aca31be9a5 2011-12-24 kinaba: int N = 1; aca31be9a5 2011-12-24 kinaba: long long coins_sum = 10000000000LL; aca31be9a5 2011-12-24 kinaba: long long coins_count = 10000000000LL; aca31be9a5 2011-12-24 kinaba: long long __[] = {10000000000 }; aca31be9a5 2011-12-24 kinaba: vector<long long> _(__, __+sizeof(__)/sizeof(*__)); aca31be9a5 2011-12-24 kinaba: END aca31be9a5 2011-12-24 kinaba: /* aca31be9a5 2011-12-24 kinaba: CASE(4) aca31be9a5 2011-12-24 kinaba: int N = ; aca31be9a5 2011-12-24 kinaba: long long coins_sum = LL; aca31be9a5 2011-12-24 kinaba: long long coins_count = LL; aca31be9a5 2011-12-24 kinaba: long long __[] = ; aca31be9a5 2011-12-24 kinaba: vector<long long> _(__, __+sizeof(__)/sizeof(*__)); aca31be9a5 2011-12-24 kinaba: END aca31be9a5 2011-12-24 kinaba: CASE(5) aca31be9a5 2011-12-24 kinaba: int N = ; aca31be9a5 2011-12-24 kinaba: long long coins_sum = LL; aca31be9a5 2011-12-24 kinaba: long long coins_count = LL; aca31be9a5 2011-12-24 kinaba: long long __[] = ; aca31be9a5 2011-12-24 kinaba: vector<long long> _(__, __+sizeof(__)/sizeof(*__)); aca31be9a5 2011-12-24 kinaba: END aca31be9a5 2011-12-24 kinaba: */ aca31be9a5 2011-12-24 kinaba: } aca31be9a5 2011-12-24 kinaba: // END CUT HERE