← 返回题目列表

AtCoder · joisc2009_logo

logo. 标志标记(Logo)

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

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

ロゴマーク (Logo) - 原题 PDF 第 1 页
原题PDF第5页
ロゴマーク (Logo) - 原题 PDF 第 2 页
原题PDF第6页
可复制的 PDF 提取文本
Logo: ロゴマーク


input ファイル“logo.in”
output 標準出力
ソースファイルlogo.c/logo.cpp
時間制限3 秒/ データ



 来る20XX 年, 国際情報学祭り(International Omatsuri in Informatics) が日本で開かれること

になった.そこでその開催に向けて,あなたはこの祭りのロゴマークを作成することになった.

 国際情報学祭りのロゴマークは,毎回,ある一定の絵が下地となって作られている.この絵

は,横W 個,縦H 個の長方形状に並んだ正方形のマス目のうちのいくつかのマス目から構成

されている.今回あなたは,この絵を日本の国旗の色である赤と白で塗り分けてロゴマークと

することにした.色塗りの作業を煩雑にしないため,1 つのマス目には1 つの色しか使うことは

できない.

 どのように塗り分けるのがよいかを決めるため,あなたは知り合いのデザイナーに助言を求

めた.彼のすばらしい美的感覚によれば,赤く塗られた領域,白く塗られた領域がどちらも線

対称な図形になっているデザインが望ましいという.また,色のバランスを考えると,赤く塗

るマス目の個数はK 個にするのが良いとも言われた.これらの条件にしたがった塗り方を彼は

教えてくれなかったので,あなたは自分で塗り方を求める必要がある.絵およびK の値が与え

られたとき,条件をみたす塗り方を1 つ求めるプログラムを作成せよ.

Input. 入力ファイルlogo.in の1 行目には,3 つの整数W, H, K(1 ≦W ≦40, 1 ≦H ≦

40, 1 ≦K ≦WH −1) が空白を区切りとして書かれている.これは,与えられた絵の横幅,縦

幅と,赤く塗るマス目の個数を表す.

 続くH 行は絵のデータを表す.i + 1 行目(1 ≦i ≦H) にはW 個の0 または1 が空白を区切

りとして書かれている.i + 1 行目のj 個目(1 ≦j ≦W) の整数が1 のときは,上からi 番目,

左からj 番目のマス目が絵に使われていることを,0 のときはそのマス目が絵に使われていない

ことを表す.絵には必ず2 つ以上のマス目が使われている.K の値は,絵に使われているマス

目の個数より小さいことが保証される.

 採点に使われるどの入力においても,条件をみたす塗り方は少なくとも1 つ存在する.


Output. 出力は,標準出力に行うこと.塗り方を表す整数を,1 行に空白区切りでW 個,H

行にわたって出力せよ.i 行目のj 個目の整数が1 の場合,上からi 番目,左からj 番目のマス

目を赤く塗ることを,2 の場合,そのマス目を白く塗ることを表す.絵に使われていないマス目

については0 を出力せよ.


                      ロゴマーク–1/2

複数の塗り方が可能な場合は,そのうちのどれを出力してもよい.

採点基準採点に用いるデータのうち,配点の20%分についてはW, H ≦5 である.


例
 logo.in 標準出力
 4 3 2    0 2 0 0
 0 1 0 0  1 0 2 1
 1 0 1 1  2 0 0 0
 1 0 0 0

 この出力は次のような塗り方に対応している. 灰色のマスは赤く塗ることを, 白のマスは白く

塗ることを表す. 破線と点線がそれぞれ赤い領域, 白い領域の対称軸である.





 次のような塗り方は条件をみたさない:





     赤い領域が線対称でない      赤く塗られたマスの個数が2 でない





                      ロゴマーク–2/2