【題目敘述】https://zerojudge.tw/ShowProblem?problemid=a261
【解題想法】DP
- a[i][j]：i 是丟水球的次數，j 是目前還沒破的水球的顆數。a[i][j] 表示 (i, j) 條件下可檢查的最高樓層數。
- 狀態轉移：a[i][j] = a[i-1][j-1] + 1 + a[i-1][j];
#include <iostream>
using namespace std;
int k;
long long n, a[64][105];
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
for (int i = 1; i <= 63; i++){
for (int j = 1; j <= 100; j++){
a[i][j] = a[i-1][j-1] + 1 + a[i-1][j];
}
}
while (cin >> k >> n){
if (k == 0) break;
if (n > a[63][k]){
cout << "More than 63 trials needed.\n";
continue;
}
for (int i = 1; i <= 63; i++){
if (n <= a[i][k]){
cout << i << "\n";
break;
}
}
}
}