← 返回题目列表

AtCoder · joisc2009_contest

contest. 竞赛

中文机器翻译题面 查看原题

以下页面来自日本信息收集官方发布的原题PDF,已完整保存并渲染到本地。

コンテスト (Contest) - 原题 PDF 第 1 页
原题PDF第4页
コンテスト (Contest) - 原题 PDF 第 2 页
原题PDF第5页
可复制的 PDF 提取文本
Contest: コンテスト


input ファイル“contest.in”
output 標準出力
ソースファイルcontest.c/contest.cpp
時間制限1 秒/ データ



 先日,とある国際的なプログラミングコンテストが開かれ,Nヶ国が参加した.コンテスト

に参加したNヶ国にはそれぞれ,1, 2, · · · , N の番号がつけられている.

 このコンテストには,各国から2 人の選手が派遣された.各選手ごとに競技の点数がつけら

れ,派遣した2 人の選手の得点の和が国の得点となる.そして,得点の大きい国から順に1 位,

2 位…と順位がつけられる.ただし,いくつかの国が同点となった場合は,それらの国には同じ

順位がつけられる.より正確には,ある国の順位は,その国より高い得点をとった国の数に1

を足したものである.たとえば,競技が4ヶ国で行われ,各国の得点がそれぞれ100, 90, 90, 80

だった場合,100 点の国は1 位,90 点の国の順位は両方とも2 位,80 点の国は4 位となる.

 今回このコンテストの運営に携わっているX 氏は,あるとき,不注意により競技の得点のデー

タの一部を紛失してしまった.その結果,得点の値はすべての参加者の分が残っているが,一

部の得点についてはどの国の参加者のものかがわからないという状況になってしまった.

 困り果てているX 氏のもとに,参加国の1 つから順位の問い合わせがあった.残念ながらデー

タの紛失により正確な順位はわからないので,X 氏は問い合わせに対して,残っているデータ

から考えられる最高の順位を答えることにした.そこで,得点のデータが与えられたとき,指

定された国の考えられる最高順位を出力するプログラムを作れ.

Input. 入力ファイルcontest.in の1 行目には,2 つの整数N, C(1 ≦N ≦3000, 1 ≦C ≦N)

が空白を区切りとして書かれている.N はコンテストに参加した国の数を,C は順位の問い合

わせがあった国の番号を表す.

 続く2N 行はコンテストの得点のデータを表す.i + 1 行目(1 ≦i ≦2N) には2 つの整数
si, ai(0 ≦si ≦1 000 000(= 106), 0 ≦ai ≦N) が空白を区切りとして書かれており,これはその

データが番号ai の国の参加者のもので,得点がsi であることを表す.ただしai = 0 の場合は,

そのデータがどの国の参加者のものかがわからないことを表す.


Output. 出力は,標準出力に行うこと.番号C の国の順位として考えられる最高の順位(数

値としてもっとも小さい値) を表す1 つの整数を出力せよ.





                      コンテスト–1/2

例
 contest.in 標準出力
 3 1         2
 7 0
 3 1
 5 0
 10 3
 6 0
 4 0

 この場合,国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 位となる.





                      コンテスト–2/2