SRM527 Div2 Hard

950

view plainprint?

1. class P8XCoinChangeAnother {  
2. public:  
3.   vector<long long> solve(int N, long long sum, long long cnt)   
4.   {  
5.     vector<long long> ret(N, 0);  
6.   
7.     ret[0] = sum;  
8.     for (int i = 0; i + 1 < N; ++i) {  
9.       ret[i + 1] = ret[i] / 2LL;  
10.       ret[i] %= 2LL;  
11.     }  
12.   
13.     lli rem = cnt - accumulate(ALL(ret), 0LL);  
14.     if (rem) {  
15.       for (int i = N - 1; 0 < i; --i) {  
16.         lli n = min(rem, ret[i]);  
17.         ret[i] -= n;  
18.         ret[i - 1] += n * 2LL;  
19.         rem -= n;  
20.       }  
21.       for (int i = 0; i < N; ++i) {  
22.         if (ret[i] < 0) return vector<lli>();  
23.       }  
24.                   
25.       if (rem) return vector<lli>();  
26.       return ret;  
27.     }  
28.   
29.     for (int i = 0; i < N; ++i) {  
30.       sum -= ret[i] * (1LL << i);        
31.     }  
32.     if (sum) return vector<lli>();  
33.     return ret;  
34.   }  
35.   
36. };  

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;
  }

};