問題一覧 > 通常問題

No.863 計算量

レベル : / 実行時間制限 : 1ケース 1.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 339
作問者 : e869120e869120 / テスター : butsurizukibutsurizuki
4 ProblemId : 3315 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2019-08-16 14:05:42

問題文

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

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

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。