No.863 計算量

レベル : / 実行時間制限 : 1ケース 1.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 170
作問者 : e869120e869120 / テスター : butsurizukibutsurizuki
2 ProblemId : 3315 / 出題時の順位表

問題文

E869120 君は、yukicoder にあるソースコードを提出しました。
その時、以下のような結果が出ました。

  • $N = 5 \ 000$ の時の実行時間は小数点以下切り捨てで $A$ ミリ秒
  • $N = 200 \ 000$ の時の実行時間は小数点以下切り捨てで $B$ ミリ秒

彼は計算量がちょうど $P * N$ ($P$ は自然数) 回の計算がかかるソースコードか、ちょうど $Q * N^2$ ($Q$ は自然数) 回の計算がかかるソースコードのいずれかを提出しました。
実行時間の情報から判断して、計算量が線形時間 ($P * N$ 回) であれば $1$ を、$N^2$ に比例するのであれば $2$ と出力してください。
ただし、yukicoder のジャッジシステムは極めて安定的であるため、常に実行速度は変わらないものとします。

制約

全ての入力データは以下の制約を満たします。

  • $A$ は $1$ 以上 $25 \ 000 \ 000$ 以下の整数
  • $B$ は $1$ 以上 $1 \ 000 \ 000 \ 000$ 以下の整数
  • 入力は問題文の条件を満たす

入力

$A$
$B$

出力

計算量が線形時間 ($P * N$ 回) であれば $1$ を、$N^2$ に比例するのであれば $2$ と出力してください。
最後に改行してください。

サンプル

サンプル1
入力
2
106
出力
1

$N = 5 \ 000$ の時に $2$ ミリ秒、$N = 200 \ 000$ の時に $106$ ミリ秒かかっているので、線形時間と考えるのが妥当でしょう。

サンプル2
入力
77
124200
出力
2

$N = 5 \ 000$ の時に $77$ ミリ秒、$N = 200 \ 000$ の時に $124 \ 200$ ミリ秒 ($124.2$ 秒) かかっているので、$N^2$ に比例する時間と考えるのが妥当でしょう。

サンプル3
入力
2160000
86400000
出力
1

普通ありえませんが、この提出はどうやら非常に定数倍の重い線形時間の解法らしいです。なぜでしょう?

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。