시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
3 초 | 512 MB | 38 | 23 | 20 | 64.516% |
あなたは,日本情報オリンピックの新しい旗として,レベル K の JOI Flag を作ることにした. ただし,
例えば,
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 を完成させるのに必要なコスト の最小値を求めるプログラムを作成せよ.
標準入力から以下の入力を読み込め.
標準出力に,レベル K の JOI Flag を作るのに必要なコストの最小値を表す整数を 1 行で出力せよ.
2 10 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
3
この入力は,
OI-O -JJ- IOI- --IO
という旗を表す.ただし,何も書かれていないマス目を - で表すとする。
これはコスト 3 で
OIJJ JJJJ OOII OOII
にすることができる.
4 30 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
9