← 返回题目列表

AtCoder · joi2007ho_d

D. 最差记者

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

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

最悪の記者 - 原题 PDF 第 1 页
原题PDF第7页
最悪の記者 - 原题 PDF 第 2 页
原题PDF第8页
最悪の記者 - 原题 PDF 第 3 页
原题PDF第9页
最悪の記者 - 原题 PDF 第 4 页
原题PDF第10页
最悪の記者 - 原题 PDF 第 5 页
原题PDF第11页
可复制的 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