ZeroJudge 解題筆記：b836. kevin戀愛攻略系列題-2 說好的霸王花呢??

作者：王一哲
日期：2025年8月3日


ZeroJudge 題目連結：b836. kevin戀愛攻略系列題-2 說好的霸王花呢??

解題想法

共有 $n$ 片花瓣，第一次拔1片，接下來每次比上一次多拔 $m$ 片，假設共拔 $k$ 次，拔掉的花瓣總數為 $$ t = k + [m + 2m + 3m + \dots + (k-1)m] = k + \frac{(k-1)km}{2} = \frac{1}{2} [m k^2 + (2-m) k] $$ 若要剛好拔完，則 $t = n$，且 $k \in N$ 才能符合條件，因此 $$ mk^2 + (2-m)k - 2n = 0 $$ 若有正整數的根，輸出 "Go Kevin!!"，否則輸出 "No Stop!!"。

Python 程式碼

使用時間約為 18 ms，記憶體約為 3.3 MB，通過測試。

import sys, math

for line in sys.stdin:  # 讀取多行測資直到 EOF 為止
    n, m = map(int, line.split())  # 花瓣數量 n，每次多拔的花瓣數量 m
    if m == 0:  # 如果 m 等於 0 一定有解
        print("Go Kevin!!")  # 印出 Go Kevin!!，繼續檢測下一行
        continue
    a, b, c = m, 2-m, -2*n  # 一元二次方程式的係數
    D = b*b - 4*a*c  # 判別式
    if D < 0:  # 判別式小於 0 無實數解
        print("No Stop!!")  # 印出 No Stop!!，繼續檢測下一行
        continue
    x1 = (-b + math.sqrt(D)) / (2*a)  # 較大的根
    x2 = (-b - math.sqrt(D)) / (2*a)  # 較小的根
    if x1 > 0 and int(x1) == math.ceil(x1):  # 如果 x1 是正整數
        print("Go Kevin!!")  # 印出 Go Kevin!!，繼續檢測下一行
        continue
    elif x2 > 0 and int(x2) == math.ceil(x2):  # 如果 x2 是正整數
        print("Go Kevin!!")  # 印出 Go Kevin!!，繼續檢測下一行
        continue
    else: print("No Stop!!")  # 否則印出 No Stop!!

C++ 程式碼

n, m, a, b, c, D 要使用 long，用 int 會溢位，無法通過第2、3筆測資。使用時間約為 2 ms，記憶體約為 324 kB，通過測試。

#include <iostream>
#include <cmath>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    long n, m;  // 花瓣數量 n，每次多拔的花瓣數量 m
    while(cin >> n >> m) {  // 讀取多行測資直到 EOF 為止
        if (m == 0) {  // 如果 m 等於 0 一定有解
            cout << "Go Kevin!!\n";  // 印出 Go Kevin!!，繼續檢測下一行
            continue;
        }
        long a = m, b = 2-m, c = -2*n;  // 一元二次方程式的係數
        long D = b*b - 4*a*c;  // 判別式
        if (D < 0) {  // 判別式小於 0 無實數解
            cout << "No Stop!!\n";  // 印出 No Stop!!，繼續檢測下一行
            continue;
        }
        float x1 = (float(-b) + sqrt(float(D))) / (2.0*float(a));  // 較大的根
        float x2 = (float(-b) - sqrt(float(D))) / (2.0*float(a));  // 較小的根
        if (x1 > 0.0 && x1 - long(x1) == 0) {  // 如果 x1 是正整數
            cout << "Go Kevin!!\n";  // 印出 Go Kevin!!，繼續檢測下一行
            continue;
        } else if (x2 > 0.0 && x2 - long(x2) == 0) {  // 如果 x2 是正整數
            cout << "Go Kevin!!\n";  // 印出 Go Kevin!!，繼續檢測下一行
            continue;
        } else cout << "No Stop!!\n";  // 否則印出 No Stop!!
    }
    return 0;
}