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



可复制的 PDF 提取文本
Japanese Olympiad In Informatics 2009/2010
Spring Training Camp
March 19 - 25, 2010, Komaba/Yoyogi, Tokyo
Contest day 4 - Plugs
プラグ(Plugs)
JOI 国には電気プラグを作っている会社がN 社あり,JOI 国は各社に1 からN までの整数をID として
割り当てている.各電気プラグ会社は1 組の電気プラグとソケットを作っているが,困ったことにすべて
の会社の電気プラグおよびソケットは他社のそれらとは違った形状をしている.
JOI 国の法律でソケットには電気プラグ会社のID を印字することになっているのだが,電気プラグには
ID は印字されていない.とある電気店の店長は,そのようなJOI 国の事情もあって,顧客の要求にすばや
く対応できるように,JOI 国に存在するN 種類すべての電気プラグを1つずつ会社のID 順に入れた道具箱
を持っていた.しかしある日,ふとした拍子に店長は道具箱の中身をバラバラにしてしまった.店長はあ
る種のソケットにある種の電気プラグが入らないことは見抜けても,電気プラグを見てどの電気プラグ会
社の電気プラグかを判断することはできないため,道具箱の中身を元に戻すことができなくなってしまっ
た.店長は困り果ててしまった末,どのような困難な問題でもいとも簡単に解いてしまうことで名高いL
教授に解決を依頼した.
L 教授は順番がばらばらになった電気プラグに整理のため1 からN までの番号をふり,それを元に店長
からM 個の証言を引き出した.店長のk 個目の証言は「電気プラグ会社のID がAk からBk のソケットに
は,Ck 番目からDk 番目のいずれの電気プラグも入らない」というものである.その後,L 教授は「謎は
解決した.このM 個の証言を満たす電気プラグと会社の対応関係は1 つに決まった.あとは君にまかせた
よ.」と言って帰ってしまった.非常に理不尽な話であるが,弟子であるあなたは問題を解決し電気プラグ
と会社の対応関係を店長に知らせなければならない.
課題(TASK)
店長の証言から電気プラグの対応関係を特定するプログラムを作成せよ.
図1
Page 1 of 3
Japanese Olympiad In Informatics 2009/2010
Spring Training Camp
March 19 - 25, 2010, Komaba/Yoyogi, Tokyo
Contest day 4 - Plugs
制限(CONSTRAINTS)
1 ≦N ≦3, 000 JOI 国に存在する電気プラグ会社の数
1 ≦M ≦100, 000 店長の証言の数
1 ≦Ak ≦Bk ≦N, 1 ≦Ck ≦Dk ≦N, 1 ≦k ≦M k 個目の証言の内容
入力(INPUT)
標準入力から以下の入力を読み込め.
• 1 行目には整数N とM が空白を区切りとして書かれている.
• 続くM 行は,1 行につき1 つの証言について記述している.これらの行のうちのk 行目はk 番目の
証言について記述しており,整数Ak, Bk,Ck,Dk が空白を区切りとして書かれている.
出力(OUTPUT)
標準出力に以下のデータを出力せよ.
• データはN 行からなり,i 行目はID がi の会社が作っている電気プラグの番号を含む.
採点基準(GRADING)
20 点分のテストグループにおいてN およびM は100 を超えない.
入出力例(EXAMPLE)
入力例(Sample Input) 出力例(Sample Output)
3 2 1
1 1 2 3 2
1 2 3 3 3
上記の例は図1 と一致する.図1 の点線は店長の証言により入らないことがわかっている組み合わせで
ある.
Page 2 of 3
Japanese Olympiad In Informatics 2009/2010
Spring Training Camp
March 19 - 25, 2010, Komaba/Yoyogi, Tokyo
Contest day 4 - Plugs
入力例(Sample Input) 出力例(Sample Output)
8 7 2
2 4 2 3 4
4 7 1 2 1
6 8 1 4 6
3 4 3 5 3
5 6 6 8 5
6 7 6 7 8
7 8 6 6 7
Page 3 of 3