Hide

Problem C
Codforces

ニコラスはcodforces™1 選手権で釣り競技を始めたいと思っています。 競うディビジョンはたくさんありますが、ニコラスはcodforces™に初めて参加するので、一番下のディビジョン(ディビジョン1)からスタートしなければなりません。 ニコラスの目標は、できるだけ早く最高のディビジョン(ディビジョン$K$)に到達し、そこで優勝することです。

codforces™のルールでは、1コンテストにつき1ディビジョンしか昇格できないので、彼は各ディビジョンで最低でも1コンテストをこなす必要があります。 ニコラスは自信満々で、次のディビジョンに進むためには、1ディビジョンにつき1回の出場で十分だと考えています。 codforces™のそれぞれのコンテストで開催されるのは1つのディビジョンだけで、2つのコンテストが時間的に重なることはありません。 また、コンテストは毎年同じスケジュールで行われます。

ニコラスは今年のいつからでもcodforces™で競技を始めることができます。 彼が言う「できるだけ早く」とは、最初に参加するコンテストと、最高のディビジョンで最初に獲得する勝利との間のcodforces™のコンテスト(彼がそれらに出場するかどうかに関係なく)の数を最小にすることです。 ニコラスが必要とするコンテストの数を計算するのを手伝ってください。

入力

入力の1行目は、$N$$K$の2つの整数($1 \leq K \leq N 10^6$)で、それぞれ年間のコンテスト数とディビジョン数を表します。

次の行には、$N$個の整数$x_1, \dots , x_ N$ ($1 \leq x_ i \leq K$) で、一年のスケジュールが書かれています。 $x_ i$は、年明けから数えて、$i$番目のコンテストで開催されるディビジョンです。 $1$から$K$までの各ディビジョンについて、毎年少なくとも1回のコンテストが行われます。

出力

ニコラスの最初のコンテストから部門$K$での最初の勝利までの間にcodforces™が開催するコンテストの最小の数を、単一の整数として出力します。

採点

あなたのソリューションは、一連のテストケースグループでテストされます。 グループのポイントを得るためには、グループ内のすべてのテストケースに成功する必要があります。

グループ

ポイント

制限

$1$

$15$

$N \leq 10^2$

$2$

$20$

$N \leq 10^3$

$3$

$25$

$N = K$

$4$

$40$

No further constraints

サンプル3の説明

ニコラスが目標に到達するための最速の方法は、最初のコンテストをディビジョン1の年内2番目のコンテストにすることです。 そして、4つのコンテストを待ち、翌年の最初のディビジョン2に出場します。 そして、3つのコンテストを待ち、ディビジョン3に出場します。 そして、5つのコンテストを待ち、ディビジョン4に出場します。 最後に、2つのコンテストを待ち、ディビジョン5に出場します。 合計すると、$1+(4+1)+(3+1)+(5+1)+(2+1) = 19$回のコンテストが必要になります。

サンプル入力 1 サンプル出力 1
3 3
3 2 1
5
サンプル入力 2 サンプル出力 2
3 2
1 1 2
2
サンプル入力 3 サンプル出力 3
7 5
2 1 1 4 3 2 5
19

Footnotes

  1. 訳注: codはタラ。プログラミングコンテストサイトCodeforcesのもじり
CPU Time limit 2 seconds
Memory limit 1024 MB
Languages English, 日本語, Svenska
Author
Simon Lindholm
Source Programmeringsolympiadens final 2019
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in