d234 - IOI研習營模考1-1新錢錢

🔗 前往 ZeroJudge 原題

題目描述

題目描述了新國王發行兩種面額的紙鈔 (a, b)，要求這兩種紙鈔能夠湊出所有大於等於 C 的金額。輸入包含 a, b, c 三個整數，判斷是否能用 a 和 b 湊出 C 元以上的任何金額，能則輸出 "Yes"，否則輸出 "No"。

解題思路

本題的核心思想是判斷是否存在一個金額上限，使得所有大於等於 C 的金額都可以用 a 和 b 湊成。程式碼使用了一個布林陣列 m 來記錄是否能湊成某個金額。首先，將所有能用 a 湊出的金額標記為可達，然後將所有能用 b 湊出的金額也標記為可達。最後，從 cc (2*c + 1) 開始倒序檢查，找到第一個無法湊出的金額，如果找不到，則表示所有大於等於 C 的金額都可以湊成。

具體步驟如下：

1. 初始化一個大小為 cc + 1 的布林陣列 m，所有元素初始化為 0 (表示不可達)。
2. 將所有能用 a 湊出的金額標記為 1 (可達)。
3. 將所有能用 b 湊出的金額標記為 1 (可達)。
4. 從 cc 倒序到 c，檢查 m[i] 是否為 0。如果找到一個 m[i] 為 0，則表示無法湊出金額 i，輸出 "No" 並結束。
5. 如果遍歷完所有金額都沒有找到 m[i] 為 0，則表示所有大於等於 C 的金額都可以湊成，輸出 "Yes"。

複雜度分析

• 時間複雜度: O(c)
• 空間複雜度: O(c)

程式碼

#include <iostream>
using namespace std;
int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	int a,b,c;
	while(cin >> a >> b >> c){
		int cc=c*2+1,m[cc+1]={0},s=0;
		for(int i=0;i<=cc;i+=a)
			m[i]=1;
		for(int i=0,cb=cc-b;i<=cb;++i)
			if(m[i])
				m[i+b]=1;
		for(int i=cc;i>=c;--i)
			if(m[i]==0){
				s=1;
				break;
			}
		if(s==0)
			cout << "Yes\n";
		else
			cout << "No\n";
	}
}