Codeforces ラウンド #256 (ディビジョン 2)D 2 ポイントanswer_html/css_WEB-ITnose

D. 九九

テストごとの制限時間

テストごとのメモリ制限

入力

出力

Bizon the Champion私たちの何人かが九九を学んでいる間、ビゾン・ザ・チャンピオンは彼なりのやり方で楽しんでいた。 Bizon the Champion は、ann?×?m の九九を描きました。ここで、i 番目の行と j 番目の列の交点の要素は i·j に等しくなります（表の行と列には 1 から始まる番号が付けられます）。次に彼は、「表の中で k 番目に大きい数字は何ですか?」と尋ねました。 Bizon the Champion は常に正確かつ即座に答えました。彼の成功を再現できますか?

与えられた九九を考えてみましょう。表からすべての n・m 個の数値を非降順で書き出す場合、書き出した k 番目の数値は k 番目に大きい数値と呼ばれます。

1 行には整数 n が含まれています。 , m and k (1?≤?n,?m?≤?5·105; 1?≤?k?≤?n·m).

a n の k 番目に大きい数値を出力します。 ?×?m 乗算表。

入力

2 2 2

2 3 4

1 10 5

A 2?×?3 九九は次のようになります:

1 2 32 4 6

题解

题目意思あり、从一n*m的乘法表（不要）问我乘法表是什么

例 2 3 4

の法表は

1 2 3

2 3 4

非順序列: 1, 2 , 2, 3, 3, 4。 4 番目の数字は 3 なので、3 が出力されます。

初めに私が望んでいたのは検索であり、n*m から検索を開始し、その後状態が発生し、多すぎると即時に検索されます。度合いは O(N * M) です。

正しい解法は 2 分です。二分法 (境界は [1, n * m]) であり、その後、福法表からより小さい数が削除されます。規則的な数表なので、各列に対して直接 O(1) 計算すると、N 回合計で計算できます。