b836 - kevin戀愛攻略系列題-2 說好的霸王花呢??

🔗 前往 ZeroJudge 原題

題目描述

題目描述了 Kevin 想要告白，但需要透過拔花瓣來判斷是否能成功。花瓣的拔取方式是每次比上次多拔 m 片，直到花瓣被拔完。如果花瓣剛好被拔完，則 Kevin 告白成功，輸出 "Go Kevin!!"，否則輸出 "No Stop!!"。

解題思路

題目要求判斷是否存在一個 n，使得花瓣總數 s 可以被表示成一個等差數列的和，首項為 1，公差為 m。等差數列的和的公式為 sum = n * (2 * a + (n - 1) * d) / 2，其中 a 是首項，d 是公差。在本題中，a = 1，d = m，所以 sum = n * (2 + (n - 1) * m) / 2。題目給定的花瓣總數是 s，因此需要判斷是否存在一個正整數 n 使得 s = n * (2 + (n - 1) * m) / 2。

程式碼中，將花瓣總數 s 乘以 2，然後使用迴圈來尋找滿足條件的 n。迴圈條件是 s >= n * (2 + (n - 1) * m)。如果找到一個 n 使得等式成立，則輸出 "Go Kevin!!"，否則輸出 "No Stop!!"。

複雜度分析

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

程式碼

#include <iostream>
using namespace std;
int main(){
	std::ios::sync_with_stdio(false);
    std::cin.tie(0);
	long long int s,d;
	while(cin >> s >> d){
		s*=2;
		if(d==0)
			cout << "Go Kevin!!" << endl;
		else{
			int n=1;
			while(s>=n*(1+((n-1)*d)+1)){
				n++;
			}
			n--;
			if(s==n*(1+((n-1)*d)+1)){
				cout << "Go Kevin!!" << endl;
			}
			else
				cout << "No Stop!!" << endl;
		}
	}
}