以下是来自日本的官方日本新闻原版PDF,已完整保存并按原样染色。



可复制的 PDF 提取文本
The 16th Japanese Olympiad in Informatics (JOI 2016/2017)
Spring Training Camp/Qualifying Trial
March 19–25, 2017 (Komaba/Yoyogi, Tokyo)
Contest Day 1 – Cultivation
開拓(Cultivation)
21XX 年,IOI 星の住人は新たに発見された惑星に移住することになった.
移住先の惑星には縦R 行,横C 列のマス目状に区切られた畑があり,畑の縦方向は南北方向に平行であ
り,横方向は東西方向に平行である.北からi 行目,西からj 列目にあるマスをマス(i, j) と呼ぶ.畑の北
西の隅のマスはマス(1,1) であり,南東の隅のマスはマス(R,C) である.毎年,IOI 星の住人は,その年に
畑に吹く風の向きを東西南北のいずれかに設定する.
移住先で農業を行うため,移住先にある畑いっぱいにJOI 草を生息させることになった.移住開始時の
春,畑のうちN マスにはJOI 草が自生している.
JOI 草は風によって生息圏を広げる.毎年夏になると,IOI 星の住人が設定した風の方向に種子を飛ばす.
飛んだ種子はその風の向きに1 マス進んた場所に着地する.その場所が畑のマスであり,かつ,そのマス
がまだJOI 草の生息圏でないなら,翌年の春にそのマスはJOI 草の生息圏となる.すでにJOI 草の生息圏
となっているマスが,その後,JOI 草の生息圏でなくなることはない.
風の向きをうまく設定することで,畑のすべてのマスをJOI 草の生息圏にするためにかかる年数の最小
値を求めたい.
課題
風の向きをうまく設定することで,畑のすべてのマスをJOI 草の生息圏にするためにかかる年数の最小
値を求めるプログラムを作成せよ.
入力
標準入力から以下の入力を読み込め.
• 1 行目には2 個の整数R, C が空白を区切りとして書かれている.これらは畑が縦R 行,横C 列のマ
ス目状に区切られていることを表す.
• 2 行目には整数N が書かれている.これは移住開始時の春に,JOI 草が自生しているマスの個数を
表す.
• 続くN 行のうちのi 行目(1 ≦i ≦N)には2 個の整数S i, Ei が空白を区切りとして書かれている.
これは移住開始時の春に,マス(S i, Ei) にJOI 草が自生していることを表す.
出力
標準出力に,風の向きをうまく設定することで,畑のすべてのマスをJOI 草の生息圏にするためにかか
る年数の最小値を1 行で出力せよ.
開拓– 1 / 3
The 16th Japanese Olympiad in Informatics (JOI 2016/2017)
Spring Training Camp/Qualifying Trial
March 19–25, 2017 (Komaba/Yoyogi, Tokyo)
Contest Day 1 – Cultivation
制限
すべての入力データは以下の条件を満たす.
• 1 ≦N ≦300.
• 1 ≦R ≦1 000 000 000.
• 1 ≦C ≦1 000 000 000.
• 1 ≦S i ≦R (1 ≦i ≦N).
• 1 ≦Ei ≦C (1 ≦i ≦N).
• 移住開始時の春に,JOI 草が自生していない畑のマスがある.
• (S i, Ei) , (S j, E j) (1 ≦i < j ≦N).
小課題
この課題では小課題は全部で6 個ある.各小課題の配点および追加の制限は以下の通りである.
小課題1 [5 点]
• R ≦4.
• C ≦4.
小課題2 [10 点]
• R ≦40.
• C ≦40.
小課題3 [15 点]
• R ≦40.
小課題4 [30 点]
• N ≦25.
小課題5 [20 点]
• N ≦100.
開拓– 2 / 3
The 16th Japanese Olympiad in Informatics (JOI 2016/2017)
Spring Training Camp/Qualifying Trial
March 19–25, 2017 (Komaba/Yoyogi, Tokyo)
Contest Day 1 – Cultivation
小課題6 [20 点]
追加の制限はない.
入出力例
入力例1 出力例1
3 4 3
3
1 2
1 4
2 3
入力例1 では,移住開始時の春に以下のようにJOI 草が自生している.
0 0
0
畑の様子.‘0’ は移住開始時の春にJOI 草が自生しているマスを表す.
この入力例では,3 年間の畑に吹く風の向きを西,南,南の順番に設定することで,3 年後の春にすべて
のマスがJOI 草の生息圏となる.下の表の数値は,何年後の春に各マスがJOI 草の生息圏となるかを表し
ている.これが最小の年数である.
1 0 1 0
2 1 0 2
3 2 2 3
入力例2 出力例2
4 4 4
4
1 1
1 4
4 1
4 4
開拓– 3 / 3