SRM439 Div2 Medium

500

とりあえずいくつか足して貪欲に変換していったら通った。

view plainprint?

1. const int M = 10000000 + 1;  
2.   
3. class PouringWater {  
4. public:  
5.   int getMinBottles(int N, int K)  
6.   {  
7.     if (N < K) return 0;  
8.   
9.     const int B = 30;  
10.     for (int m = 0; m <= M; ++m) {  
11.       lli n = m + N;  
12.       lli b = n;  
13.       for (int i = 0; i + 1 < B; ++i) {  
14.         b -= n;  
15.         b += (n % 2) + (n / 2);  
16.         n /= 2;  
17.         if (b <= K) return m;  
18.       }  
19.     }  
20.   
21.     return -1;  
22.   }  
23. };  

const int M = 10000000 + 1;

class PouringWater {
public:
  int getMinBottles(int N, int K)
  {
    if (N < K) return 0;

    const int B = 30;
    for (int m = 0; m <= M; ++m) {
      lli n = m + N;
      lli b = n;
      for (int i = 0; i + 1 < B; ++i) {
        b -= n;
        b += (n % 2) + (n / 2);
        n /= 2;
        if (b <= K) return m;
      }
    }

    return -1;
  }
};