← 返回题目列表

AtCoder · joisc2012_joi_flag

joi_flag. 日本信息奥运旗帜

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

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

日本情報オリンピック旗 - 原题 PDF 第 1 页
原题PDF第5页
日本情報オリンピック旗 - 原题 PDF 第 2 页
原题PDF第6页
日本情報オリンピック旗 - 原题 PDF 第 3 页
原题PDF第7页
日本情報オリンピック旗 - 原题 PDF 第 4 页
原题PDF第8页
可复制的 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