53 lines
1.4 KiB
C++
53 lines
1.4 KiB
C++
#include <iostream>
|
|
|
|
constexpr size_t MAX_HEIGHT = 4e4 + 1, MAX_EGGS = 30, INF = 0x3f3f3f3f;
|
|
int eggs_amount, height;
|
|
|
|
int dp[MAX_HEIGHT][MAX_EGGS];
|
|
bool ping_pong;
|
|
|
|
void print_dp(std::ostream& os = std::clog, int h = MAX_HEIGHT - 1) {
|
|
for (int i = 0; i <= h; i++) {
|
|
for (int j = 0; j < MAX_EGGS; j++) {
|
|
os << dp[i][j] << " ";
|
|
}
|
|
os << std::endl;
|
|
}
|
|
}
|
|
|
|
void init_dp() {
|
|
for (int i = 0; i < MAX_HEIGHT; i++) {
|
|
dp[i][1] = i;
|
|
}
|
|
for (int h = 1; h < MAX_HEIGHT; h++) {
|
|
for (int eggs = 2; eggs < MAX_EGGS; eggs++) {
|
|
int min_value = +INF;
|
|
for (int i = 1; i <= h; i++) {
|
|
min_value = std::min(
|
|
min_value, std::max(dp[i - 1][eggs - 1], dp[h - i][eggs]));
|
|
}
|
|
dp[h][eggs] = min_value + 1;
|
|
if (eggs >= dp[h][eggs]) {
|
|
for (int i = eggs; i < MAX_EGGS; i++) { dp[h][i] = dp[h][eggs]; }
|
|
break;
|
|
}
|
|
}
|
|
}
|
|
print_dp(std::clog, 100);
|
|
}
|
|
|
|
int main() {
|
|
std::ios::sync_with_stdio(false);
|
|
std::cin.tie(nullptr);
|
|
|
|
init_dp();
|
|
while (std::cin >> height >> eggs_amount && height) {
|
|
// if (height >= MAX_HEIGHT || eggs_amount >= MAX_EGGS) {
|
|
// throw std::overflow_error("Oh no!");
|
|
// }
|
|
// if (eggs_amount >= MAX_EGGS) { eggs_amount = MAX_EGGS - 1; }
|
|
std::cout << dp[height][eggs_amount] << std::endl;
|
|
}
|
|
return 0;
|
|
}
|