- class P8XCoinChangeAnother {
- public:
- vector<long long> solve(int N, long long sum, long long cnt)
- {
- vector<long long> ret(N, 0);
- ret[0] = sum;
- for (int i = 0; i + 1 < N; ++i) {
- ret[i + 1] = ret[i] / 2LL;
- ret[i] %= 2LL;
- }
- lli rem = cnt - accumulate(ALL(ret), 0LL);
- if (rem) {
- for (int i = N - 1; 0 < i; --i) {
- lli n = min(rem, ret[i]);
- ret[i] -= n;
- ret[i - 1] += n * 2LL;
- rem -= n;
- }
- for (int i = 0; i < N; ++i) {
- if (ret[i] < 0) return vector<lli>();
- }
- if (rem) return vector<lli>();
- return ret;
- }
- for (int i = 0; i < N; ++i) {
- sum -= ret[i] * (1LL << i);
- }
- if (sum) return vector<lli>();
- return ret;
- }
- };
2/28/2012
SRM527 Div2 Hard
950
登録:
コメントの投稿
(
Atom
)
0 件のコメント :
コメントを投稿