题解：The Snail（P1563）

一、题目分析

本题描述了蜗牛爬井的问题，需要计算蜗牛何时能爬出井或滑回井底。关键规则：

• 蜗牛白天爬升距离每天递减，递减量为初始爬升距离的F%
• 夜晚固定下滑D英尺
• 当某天白天爬升后高度超过井深H时，成功爬出
• 当某天夜晚下滑后高度为负时，滑回井底

二、解题思路

1. 模型建立：
   设初始爬升距离为U，疲劳因子F%，则第n天白天爬升距离为：
   [ u_n = u_{n-1} - u_0 \times \frac{F}{100} ]
   其中(u_0 = U)，且当(u_n \leq 0)时，当天白天不爬升。

2. 模拟过程：
   逐日模拟蜗牛的高度变化：

   • 白天爬升后检查是否超过井深H（成功）
   • 夜晚下滑后检查是否小于0（失败）
   • 记录天数直到满足终止条件。

三、代码解析

#include <iostream>
using namespace std;

int main() {
    double h, u, d, p;
    while (1) {
        cin >> h >> u >> d >> p;
        if (h == 0 && u == 0 && d == 0 && p == 0) break;  // 输入结束条件
        
        double daily_decrease = (p / 100.0) * u;  // 每日爬升距离递减量
        int day = 1;
        double height = 0;
        int flag = 0;  // 0表示未结束，1表示失败
        
        while (1) {
            if (u > 0) {
                height += u;  // 白天爬升
                if (height > h) break;  // 成功爬出
                u -= daily_decrease;  // 更新次日爬升距离
                if (u < 0) u = 0;  // 爬升距离不为负
            }
            height -= d;  // 夜晚下滑
            day++;
            
            if (height < 0) {  // 滑回井底
                flag = 1;
                break;
            }
        }
        
        if (flag) {
            cout << "failure on day " << day << endl;
        } else {
            cout << "success on day " << day << endl;
        }
    }
    return 0;
}

四、关键步骤解析

1. 输入处理
   读取井深H、初始爬升U、下滑D、疲劳因子F，当H=U=D=F=0时结束输入。

2. 递减量计算
   每日爬升距离递减量为：
   [ \text{daily_decrease} = U \times \frac{F}{100} ]
   注意转换为浮点数计算（$p/100.0$）。

3. 逐日模拟

   • 白天爬升：若当前爬升距离u>0，累加高度并检查是否超过H
   • 爬升衰减：u按递减量减少，若u<0则置为0
   • 夜晚下滑：高度减去D，天数加1
   • 终止条件：高度>h（成功）或高度<0（失败）

4. 结果输出
   根据flag标记输出"success"或"failure"及对应天数。

五、示例解析

以输入$6 3 1 10$为例：

1. 参数：H=6，U=3，D=1，F=10
2. 逐日计算：
   • 第1天：
     白天爬升3，高度3（3>6？否）→ 夜晚下滑1，高度2
   • 第2天：
     u=3-0.3=2.7 → 白天爬升2.7，高度4.7（4.7>6？否）→ 夜晚下滑1，高度3.7
   • 第3天：
     u=2.7-0.3=2.4 → 白天爬升2.4，高度3.7+2.4=6.1>6 → 成功，输出"success on day 3"

六、注意事项

1. 浮点数精度
   所有计算使用double类型，避免整数除法误差，如$p/100.0$而非$p/100$。

2. 爬升距离处理
   当u递减至≤0时，当天白天不爬升（height不增加）。

3. 终止条件顺序
   先检查白天爬升后是否成功，再处理夜晚下滑，确保逻辑正确。

4. 天数计算
   夜晚下滑后天数加1，如示例中第3天白天爬升成功，天数为3。

七、复杂度分析

• 时间复杂度：O(1)，每个测试用例的循环次数有限（最多几百次）。
• 空间复杂度：O(1)，仅使用常数级变量。

八、可能的优化

1. 提前终止判断
   当爬升距离u≤D时，若当前高度+u≤H且高度-D<0，可提前判断失败。

2. 数学推导
   可通过数学公式推导临界条件，减少循环次数，但代码复杂度会增加。