d258 - 11313 - Gourmet Games

🔗 前往 ZeroJudge 原題

題目描述

題目描述了一個烹飪比賽，有 n 位廚師，每集比賽選出 m 位廚師，直到剩下 1 位優勝者。題目要求判斷在給定的 n 和 m 下，是否能通過這種方式選出優勝者，如果可以，則計算所需的比賽集數。如果無法選出優勝者，則輸出 "cannot do this"。

解題思路

這個問題可以通過模擬比賽過程來解決。每次比賽，如果廚師人數能被 m 整除，則直接除以 m，得到下一輪的廚師人數。如果不能整除，則計算商和餘數，商表示下一輪的廚師人數，餘數表示直接晉級的種子廚師人數。然後將商和餘數加起來，作為下一輪的廚師人數。重複這個過程，直到廚師人數為 1。如果最終廚師人數為 1，則輸出比賽集數；否則，輸出 "cannot do this"。

複雜度分析

• 時間複雜度: O(n)
• 空間複雜度: O(1)

程式碼

#include <iostream>
using namespace std;
int m,n,t;
int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	cin >> t;
	while(t--){
		cin >> n >> m;
		int ans=0;
		while(n>=m){
			if(n%m==0){
				ans+=n/m;
				n=n/m;
			}
			else{
				ans+=n/m;
				n=n/m+n%m;
			}
		}
		if(n==1)
			cout << ans << "\n";
		else
			cout << "cannot do this\n";
	}
}