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


可复制的 PDF 提取文本
Japanese Olympiad in Informatics 2010/2011
Qualifying Trial
April 23–24, May 3–5, 2011, Tokyo/Osaka
Contest Day 1 – Dragon
ドラゴン(Dragon)
IOI の競技会場にドラゴンたちが入ってきてしまった.競技会場は長方形の部屋であり,H 行W 列のマ
スに区切られている.行には1 からH まで,列には1 からW までの番号がふられていて,x 行目y 列目
のマスを(x, y) で表す.入ってきたドラゴンはN 匹であり,i 匹目のドラゴンは(Xi, Yi) にいる.同じマス
にドラゴンが2 匹以上いることはない.ドラゴンと同じ行または同じ列のマスには,ドラゴンが炎を吹い
て攻撃することがある.選手は,ドラゴンのいないマスに,1 マスに1 人まで入ることができるが,ドラ
ゴンに攻撃される可能性のあるマスには入ることができない.JOI のM 理事長は,少しでも参加可能な選
手の数を増やすため,防火装置をもってドラゴンのいないどこかのマスに立つことにした.選手とドラゴ
ンが同じ行または列にいる場合でも,間にM 理事長がいれば炎を通さないので,選手はそのドラゴンから
は攻撃されない.ただし,M 理事長は全ての問題の答えを知っているので,M 理事長のいるマスには選手
は入れない.
課題
競技会場の大きさの情報と,ドラゴンの位置の情報が与えられたとき,M 理事長が最適なマスに立った
場合の競技会場に入れる選手の人数の最大値を求めるプログラムを作成せよ.
制限
1 ≦H ≦1 000 000 000 競技会場の行数
1 ≦W ≦1 000 000 000 競技会場の列数
1 ≦N ≦100 000 ドラゴンの数
1 ≦Xi ≦H, 1 ≦Yi ≦W i 番目のドラゴンの位置
入力
標準入力から以下の入力を読み込め.
• 1 行目には整数H, W, N が空白を区切りとして書かれている.
• 続くN 行にはドラゴンの位置の情報が書かれている.i + 1 行目(1 ≦i ≦N) には,i 番目のドラゴン
の位置を表す整数Xi, Yi が空白を区切りとして書かれている.ただし,同じマスにドラゴンが2 匹以
上いることはない.また,少なくとも1 つドラゴンのいないマスがある.
出力
標準出力に,競技会場に入れる選手の人数の最大値を1 行で出力せよ.
ドラゴン– 1 / 2
Japanese Olympiad in Informatics 2010/2011
Qualifying Trial
April 23–24, May 3–5, 2011, Tokyo/Osaka
Contest Day 1 – Dragon
採点基準
採点用データのうち,配点の30%分については,H ≦1 000 かつW ≦1 000 を満たす.
採点用データのうち,配点の40%分については,N ≦1 000 を満たす.
採点用データのうち,配点の20%分については,これら2 つの条件の両方を満たす.
採点用データのうち,配点の50%分については,これら2 つの条件の少なくとも一方を満たす.
入出力の例
入力例 出力例
4 6 3 9
2 4
3 5
2 3
下図は,この入力例に対応している.D はドラゴンを表す.
D D
D
下図は,M 理事長と選手の配置例であり,M はM 理事長を,C は選手を表す.この配置では9 人の選
手が入ることができ,M 理事長をどこに配置しても10 人以上の選手が入ることはできない.
C C C
D D
C C M D
C C C C
ドラゴン– 2 / 2