contest - コンテスト (Contest) Editorial /

Time Limit: 1 sec / Memory Limit: 64 MiB

AtCoder での提出方法

標準入力から入力を読み込み,標準出力へ出力すること.

配点 : 100 点

問題文

先日,とある国際的なプログラミングコンテストが開かれ,N ヶ国が参加した.コンテストに参加した N ヶ国にはそれぞれ,1, 2, \cdots, N の番号がつけられている.

このコンテストには,各国から 2 人の選手が派遣された.各選手ごとに競技の点数がつけられ,派遣した 2 人の選手の得点の和が国の得点となる.そして,得点の大きい国から順に 1 位,2 位…と順位がつけられる.ただし,いくつかの国が同点となった場合は,それらの国には同じ順位がつけられる.より正確には,ある国の順位は,その国より高い得点をとった国の数に 1 を足したものである.たとえば,競技が 4 ヶ国で行われ,各国の得点がそれぞれ 100, 90, 90, 80 だった場合,100 点の国は 1 位,90 点の国の順位は両方とも 2 位,80 点の国は 4 位となる.

今回このコンテストの運営に携わっている X 氏は,あるとき,不注意により競技の得点のデータの一部を紛失してしまった.その結果,得点の値はすべての参加者の分が残っているが,一部の得点についてはどの国の参加者のものかがわからないという状況になってしまった.

困り果てている X 氏のもとに,参加国の 1 つから順位の問い合わせがあった.残念ながらデータの紛失により正確な順位はわからないので,X 氏は問い合わせに対して,残っているデータから考えられる最高の順位を答えることにした.そこで,得点のデータが与えられたとき,指定された国の考えられる最高順位を出力するプログラムを作れ.

入力

入力ファイル contest.in の 1 行目には,2 つの整数 N, C (1 \leqq N \leqq 3000,1 \leqq C \leqq N) が空白を区切りとして書かれている.N はコンテストに参加した国の数を,C は順位の問い合わせがあった国の番号を表す.

続く 2N 行はコンテストの得点のデータを表す.i + 1 行目 (1 \leqq i \leqq 2N) には 2 つの整数 s_{i}, a_{i} (0 \leqq s_{i} \leqq 1\,000\,000(= 10^{6}),0 \leqq a_{i} \leqq N) が空白を区切りとして書かれており,これはそのデータが番号 a_{i} の国の参加者のもので,得点が s_{i} であることを表す.ただし a_{i} = 0 の場合は,そのデータがどの国の参加者のものかがわからないことを表す.

出力

出力は,標準出力に行うこと.番号 C の国の順位として考えられる最高の順位 (数値としてもっとも小さい値) を表す 1 つの整数を出力せよ.

入力例 1

3 1
7 0
3 1
5 0
10 3
6 0
4 0

出力例 1

2

この場合,国 1 の順位としては次のように 2 位または 3 位が考えられるので,2 を出力する:

  • 7 点のデータが国 1 のもので,5 点のデータと 4 点のデータが国 2 のもの,6 点のデータが国 3 のものの場合,国 1 の得点は 7+3=10,国 2 の得点は 5+4=9,国 3 の得点は 10+6=16 となり,国 1 の順位は 2 位となる.
  • 7 点のデータが国 1 のもので,5 点のデータと 6 点のデータが国 2 のもの,4 点のデータが国 3 のものの場合,国 1 の得点は 7+3=10,国 2 の得点は 5+6=11,国 3 の得点は 10+4=14 となり,国 1 の順位は 3 位となる.

Source Name

JOI 2008-2009 春季トレーニング合宿 Contest Day2