以下是来自日本的原始新闻PDF,已完整保存和染色。




可复制的 PDF 提取文本
Japanese Olympiad in Informatics 2011/2012
Spring Training Camp/Qualifying Trial
March 19–25, 2012, Komaba/Yoyogi, Tokyo
Contest Day 1 – JOI Flag
日本情報オリンピック旗(JOI Flag)
あなたは,日本情報オリンピックの新しい旗として,レベルK のJOI Flag を作ることにした.
ただし,
• レベル0 のJOI Flag とは,1 × 1 のマス目からなる旗で,J, O, I のいずれかの文字が書かれたもので
ある.
• 整数m > 0 に対し,レベルm のJOI Flag とは,2m × 2m のマス目からなる旗で,各マスにJ, O, I の
いずれかの文字が書かれたもののうち,次の条件を満たすものである:マス目全体を2m−1 × 2m−1 の
正方形4 つに分けたとき,レベルm −1 のJOI Flag ,J の書かれたマスのみからなる部分,O の書
かれたマスのみからなる部分,I の書かれたマスのみからなる部分の4 つの部分に分かれる.
例えば,
OIJJ
JJJJ
OOII
OOII
は,レベル2 のJOI Flag である.また,
IIIIIIOO
IIIIIIOO
IIIIJOJJ
IIIIOIJJ
JJJJOOOO
JJJJOOOO
JJJJOOOO
JJJJOOOO
は,レベル3 のJOI Flag である.
あなたの手元には,いくつかのマス目にJ, O, I のいずれかの文字が書きこまれた2K × 2K の旗がある.
あなたは,この旗にいくつかの文字を書き加えたり,既に旗に書かれているいくつかの文字を修正した
りして,レベルK のJOI Flag を完成させることにした.文字が書かれていないマスにはコスト0 で文字
を書けるが,文字が書かれたマスの文字を書き換えるにはコスト1 がかかる.
レベルK のJOI Flag を完成させるのに必要なコストの最小値を求めたい.
課題
あなたの手元にある旗の情報が与えられたとき,レベルK のJOI Flag を完成させるのに必要なコスト
の最小値を求めるプログラムを作成せよ.
日本情報オリンピック旗– 1 / 4
Japanese Olympiad in Informatics 2011/2012
Spring Training Camp/Qualifying Trial
March 19–25, 2012, Komaba/Yoyogi, Tokyo
Contest Day 1 – JOI Flag
制限
1 ≦K ≦30 JOI Flag のレベル
1 ≦N ≦1 000 JOI Flag に書き込まれている文字の個数
1 ≦Xi ≦2K i 番目の文字の書かれている列番号
1 ≦Yi ≦2K i 番目の文字の書かれている行番号
Ci はJ, O, I のいずれかである.
組(Xi, Yi) はすべて異なる.
入力
標準入力から以下の入力を読み込め.
• 1 行目には整数K, N が空白を区切りとして書かれている.K はJOI Flag のレベルを,N は文字の書
かれたマス目の個数をそれぞれ表す.文字には1, 2, · · · , N の番号がつけられている.
• 続くN 行には文字の情報が書かれている.i + 1 行目にはXi, Yi,Ci が空白を区切りとして書かれてい
る.これは,文字Ci が左からXi 列目,上からYi 行目に書かれていることを表す.
出力
標準出力に,レベルK のJOI Flag を作るのに必要なコストの最小値を表す整数を1 行で出力せよ.
採点基準
採点用データのうち,配点の40% 分については,K ≦10 を満たす.
入出力の例
入力例1 出力例1
2 10 3
2 2 J
3 3 I
1 3 I
1 1 O
3 2 J
2 1 I
4 1 O
3 4 I
4 4 O
2 3 O
日本情報オリンピック旗– 2 / 4
Japanese Olympiad in Informatics 2011/2012
Spring Training Camp/Qualifying Trial
March 19–25, 2012, Komaba/Yoyogi, Tokyo
Contest Day 1 – JOI Flag
この入力は,
OI-O
-JJ-
IOI-
--IO
という旗を表す.ただし,何も書かれていないマス目を- で表すとする。
これはコスト3 で
OIJJ
JJJJ
OOII
OOII
にすることができる.
日本情報オリンピック旗– 3 / 4
Japanese Olympiad in Informatics 2011/2012
Spring Training Camp/Qualifying Trial
March 19–25, 2012, Komaba/Yoyogi, Tokyo
Contest Day 1 – JOI Flag
入力例2 出力例2
4 30 9
16 14 J
2 8 O
10 9 J
10 13 I
6 6 O
11 14 I
1 2 I
3 2 O
3 10 O
1 12 I
4 11 I
9 5 J
15 1 O
12 4 I
16 5 J
10 7 J
3 8 J
4 10 I
4 7 I
2 11 I
2 12 O
15 5 J
15 7 J
6 9 J
5 7 O
14 5 J
12 11 J
15 10 O
13 16 I
13 11 I
日本情報オリンピック旗– 4 / 4