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





可复制的 PDF 提取文本
4 最悪の記者
問題
あなたはJOI 新聞社の記者であり,スポーツ記事を担当している.
昨日までに,クロアチアでは,n 個のサッカーチームによる総当りのリーグ戦が
行われた.大会実行委員会は,試合結果と規定に基づき各チームに1 位からn 位ま
での順位をつけたようである.あなたには,一部の試合の勝敗とともに,次の情報
が伝えられた.
情報1 引き分けの試合はなかった.
情報2 全てのチームに異なる順位がついた.
情報3 全ての1 ≦a < b ≦n に対し,a 位のチームとb 位のチームの試合において,
必ずa 位のチームが勝利した.
あなたは記事を作成するために,一部の試合の勝敗と,伝えられた情報1~3 をも
とに,順位表を推測することにした.
入力として一部の試合の勝敗が与えられたとき,伝えられた情報に適合する順位
表を1 つ出力するプログラムを作れ.また,出力した順位表以外に,伝えられた情
報に適合する順位表が存在するかどうかも判定せよ.
ここで,順位表とは1 位からn 位の順にチームを並べたもののことをいう.
問題4-1
例
例1 (情報に適合する順位表が1 つしかない場合)
チーム数が4 で,各チームに1 から4 までの番号が付けられており,勝敗が次の表
で与えられていたとする.
i\j 1 2 3 4
1 — ○ × ×
2 × — × ?
3 ○ ○ — ○
4 ○ ? × —
i 行j 列が○のときは,番号i のチームと番号j のチームの試合において,番号i の
チームが勝利したことを意味する.また,×のときは,番号j のチームが勝利した
ことを意味する.? は勝敗が与えられていないことを意味する.
このとき,伝えられた情報に適合する順位表は次の1 つしかない.
1 位 番号3 のチーム
2 位 番号4 のチーム
3 位 番号1 のチーム
4 位 番号2 のチーム
例2 (情報に適合する順位表が複数存在する場合)
チーム数が3 で,各チームに1 から3 までの番号が付けられており,勝敗が次の表
で与えられていたとする.
i\j 1 2 3
1 — × ?
2 ○ — ○
3 ? × —
このとき,伝えられた情報に適合する順位表は,次の2 つである.
1 位 番号2 のチーム 1 位 番号2 のチーム
2 位 番号1 のチーム 2 位 番号3 のチーム
3 位 番号3 のチーム 3 位 番号1 のチーム
問題4-2
入力
入力ファイルのファイル名はinput.txt である.
1 行目には,サッカーチームの個数n が書かれている.各チームには,1 からn ま
での番号が付けられている.
2 行目には,与えられた試合の勝敗の個数m が書かれている.
3 行目からm + 2 行目は試合の勝敗を表す.各行は空白で区切られた2 つの整数
i, j を含み,番号i のチームが番号j のチームに勝利したことを表す.
n, m は1 ≦n ≦5000, 1 ≦m ≦100000 をみたす.
採点の際に用いるテストデータのうち,30% は1 ≦n ≦7, 1 ≦m ≦15 をみた
す.また,60% は1 ≦n ≦100, 1 ≦m ≦2000 をみたす.
出力
出力ファイルのファイル名はoutput.txt である.
出力ファイルはn + 1 行からなる.
1 行目からn 行目までのn 行には,伝えられた情報に適合する順位表を出力せよ.
i 行目(1 ≦i ≦n) にi 位のチームの番号を出力せよ.
n + 1 行目には,出力した順位表以外に,伝えられた情報に適合する順位表が存在
するかどうかを表す整数を出力せよ.もし存在しなければ0 を,存在する場合は1
を出力せよ.
問題4-3
入出力の例
入出力の例1
例1 に対応する入出力は以下の通りである.
input.txt
4
5
1 2
3 1
3 2
3 4
4 1
output.txt
3
4
1
2
0
問題4-4
入出力の例2
例2 に対応する入力データは以下の通りである.
input.txt
3
2
2 1
2 3
この入力データに対して,次の2 通りの出力データが考えられる.どちらを出力
してもよい.
output.txt
2
1
3
1
output.txt
2
3
1
1
問題4-5