c036 - 00573 - The Snail
題目描述
題目描述了一隻蝸牛試圖爬出井口的過程。蝸牛白天向上爬，晚上向下滑。蝸牛每天爬的高度會因疲勞因子而減少。題目要求計算蝸牛在第幾天成功爬出井口，或者在第幾天滑回井底。
解題思路
這題可以使用模擬的方法來解決。我們需要模擬蝸牛每天的爬行和滑落過程，直到蝸牛爬出井口或滑回井底。在模擬過程中，需要考慮蝸牛的疲勞因子，每天爬的高度會減少。此外，蝸牛的高度不能為負數，如果蝸牛的高度為負數，則表示蝸牛滑回井底。
複雜度分析
- 時間複雜度: O(N)，其中 N 是蝸牛爬出或滑回井底的天數。在最壞的情況下，蝸牛可能需要很長時間才能爬出井口或滑回井底。
- 空間複雜度: O(1)，因為我們只需要常數級別的空間來存儲蝸牛的高度、爬行距離和天數。
程式碼
#include <iostream>
using namespace std;
int main(){
double a,b,c,d;
while(cin >> a >> b >> c >> d){
d=b*d/100;
if(a==0)break;
double day=0,n=0;
while(1){
day++;
n+=b;
if(n>a){
cout << "success on day " << day << "\n";
break;
};
n-=c;
if(n<0){
cout << "failure on day " << day << "\n";
break;
};
b=max(b-d,0.0);
}
}
}