解いた問題

2/28/2012

SRM527 Div2 Hard

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

0 件のコメント :

コメントを投稿