f375 - 神奇肥料 Fertilizer

🔗 前往 ZeroJudge 原題

題目描述

題目描述了農夫想要生產肥料，肥料的生長速度取決於當前的肥料量。農夫初始有 t 單位肥料，目標是達到至少 g 單位肥料。每經過一天，肥料會根據以下規則增長：

• 如果肥料量 t 小於目標量 g，則進行增長。
• 如果天數 d 是 10 的倍數，則肥料量增加 1。
• 如果天數 d 是 3 的倍數，則肥料量增加 t/3 (整數除法)。
• 否則，肥料量增加 t/10 (整數除法)。

題目要求輸出達到目標所需的天數，如果永遠無法達到目標，則輸出 "unsalable"。

解題思路

這題可以使用貪心策略和模擬的方法來解決。我們模擬肥料的生長過程，每天更新肥料量，直到肥料量達到或超過目標量。如果模擬過程中天數超過了限制 s，則輸出 "unsalable"。

程式碼中，d 代表天數，t 代表當前的肥料量，g 代表目標肥料量，s 代表天數上限，a 是一個輔助變數，用於判斷是否需要增加天數。

程式碼的核心邏輯是 while 迴圈，每次迴圈模擬一天。在迴圈中，首先判斷當前肥料量是否達到目標，如果達到則輸出天數並結束迴圈。然後，增加天數 d，並根據天數的規則更新肥料量 t。如果天數是 10 的倍數，則肥料量增加 1。如果天數是 3 的倍數，則肥料量增加 t/3。否則，肥料量增加 t/10。

在迴圈結束後，如果肥料量仍然小於目標量，則輸出 "unsalable"。

複雜度分析

• 時間複雜度: O(s)，其中 s 是天數上限。因為程式碼最多模擬 s 天。
• 空間複雜度: O(1)，因為程式碼只使用了常數個變數。

程式碼

#include <iostream>
using namespace std;
int main(){
	int d=0,t,s,g,a=1;
	cin >> t >> g >> s;
	while(a<=s){
		if(g<=t){
			cout << d+1;
			break;
		}
		++d;
		if(d%10==9){
			++d;
			++a;
			continue;
		}
		if(d%3==0){
			t+=t/3;
		}
		else if(d){
			t+=t/10;
		}
	}
	if(t<g){
		cout << "unsalable";
	}
}