[模拟]来一瓶82年拉菲(酒杯问题)

问题描述:

悠神最近过生日,朋友纷纷来贺。现有一瓶82年拉菲与若干酒杯。酒杯呈三角形酒塔摆放,即每一个酒杯摆放在下一层两个酒杯中间,最下面一层酒杯摆放在桌面上。共有N(1<=N<=20)层酒杯,第k层共有k个酒杯。悠神将拉菲倒进第一层的酒杯中,速度为1杯/s,倒满后酒会向左右两个方向溢出,假设会全部溢出到这个酒杯下面相邻的两个酒杯中。然而悠神有洁癖,他不喜欢浪费,更不喜欢浸湿他心爱的桌布,所以请你计算一下第几秒之后桌布会被浸湿。

eg:如图所示为3层时的情况。第一层倒满需要1s,第二次倒满需要2s,第三层首次倒满需要2s。所以共需1+2+2=5s。

img

输入:

输入N(1<=N<=20)。

输出:

桌布浸湿时至少所需时间(取整数)。

输入样例:

2

输出样例:

3

分析:

桌布浸湿只与最下层最中间位置何时倒满有关,因此只需计算最下层中间位置酒杯的状态。由于时间取整,所以只需模拟出第一杯共倒了多少杯酒,即为多少s。而每一个酒杯共倒了多少酒与上一层相邻两个酒杯相关,及第i层第j个酒杯的酒只与第i-1层第j-1个和第j个酒杯的酒相关。及wine[i][j]=wine[i-1][j-1]+wine[i-1][j];由于酒杯有两种状态,及未满状态和倒满状态,所以要判断wine[i-1]层的酒是否>1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<stdio.h>  
#include<string.h>
#define MAXN 20
int main() {
int N;
while (~scanf("%d", &N)) {
double wine[MAXN + 1][MAXN + 1] = { 0 };
double temp = 0;
while (wine[N][N / 2 + 1] < 1) {
memset(wine, 0, sizeof(wine));
temp++;
wine[1][1] = temp;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= i; j++) {
wine[i][j] += (wine[i - 1][j - 1] > 1 ? (wine[i - 1][j - 1] - 1) / 2.0 : 0) + (wine[i - 1][j] > 1 ? (wine[i - 1][j] - 1) / 2.0 : 0);
}
}
}
printf("%g\n", wine[1][1]);
}
return 0;
}

文章结束了,但我们的故事还在继续
坚持原创技术分享,您的支持将鼓励我继续创作!