AtCoder ABC 238 A - Exponential or Quadratic (6Q, 灰色, 100 点)

ちゃんと証明しようとすると、数学的帰納法などが必要になるが、推測して答えてもいいと思う。

• 問題へのリンク

問題概要

正の整数 が与えられる。

が成り立つかどうかを判定せよ。

制約

• 

解法

この手の問題では、小さな で実験してみよう！　そうすれば法則性が見つかるかもしれない。

1	2	1
2	4	4
3	8	9
4	16	16
5	32	25
6	64	36
7	128	49
8	256	64
9	512	81
10	1024	100

こうして比較すると、 の範囲では が圧倒的に大きくなり、 の増加は緩やかなことがわかる。

このことと、 のときの値から、次の予想が立てられる。

• のとき："No"
• または のとき："Yes"

これは実際成り立つのだが、成り立つことの証明は editorial を参照。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    if (n == 2 || n == 3 || n == 4)
        cout << "No" << endl;
    else
        cout << "Yes" << endl;
}