lightbulbs
Day2 Tasks

European Girls'
Olympiad in Informatics
21 – 27 July 2024
The Netherlands

Japanese (JPN)

C. 電球 (Light Bulbs)
問題名

電球 (lightbulbs)

実⾏時間制限

4秒

メモリ制限

1 GB

Frederik Philips ⽒は，1891 年に Eindhoven 市の電球メーカーを設⽴した後，すごい発明をした．これは，縦⽅向または横⽅向に無限に光線が延びる電球である．彼はこの発明を使って，現代的な家の内装のデザインに⾰命を起こしたい．
いま，彼は息⼦の Gerard ⽒とともに，電球の設置を⼊念に計画している．まず，部屋は N × N のマス⽬状の区画に区切られているが，各区画にひとつずつ，合計 N 2 個の電球を設置した．彼らは電⼒使⽤量を削減するため，最⼩の数の電球を ON にすることで部屋全体を明るくしたい．ここで，各電球の向きは縦⽅向 (同じ列のすべての区画を照らす) または横⽅向 (同じ⾏のすべての区画を照らす) のいずれかである．
縦⽅向の電球 (左) と横⽅向の電球 (右) の例を以下に⽰す．

しかし，残念ながら，彼らは電球の設置をする際に不注意であったため，各電球が縦⽅向であったか横⽅向であったかを覚えていない．このままでは，どの電球を ON にすると部屋全体が明るくなるのか分からない．そこで彼らは，何回かの実験を⾏うことにした．Gerard ⽒は電球のある部屋にとどまり，Frederik ⽒は別の部屋から電球のスイッチを操作する．
各実験では，Frederik ⽒は各電球を ON にするか OFF にするかを決めて操作し，Gerard ⽒は合計何個の区画が明るく照らされているかを報告する．ここで，2 つ以上の電球に照らされている区画についても「1 つ」としてだけカウントする．ここで，各実験では何個の電球を ON にしても問題ないが，彼らは急いでいるため，実験回数をできるだけ少なく抑えたい．

lightbulbs (1 of 5)

最⼩の数の電球を ON にすることで部屋全体を明るくする⽅法を⾒つけることで，彼らを⼿伝え．彼らは最⼤ 2 000 回の実験を⾏えるが，⾼得点を得るには，実験回数をより少なくしなければならない．

インタラクション
この問題はインタラクティブ問題である．
あなたのプログラムは最初に整数 N を読み込む．N は区画の縦の個数であり，区画の横の個数でもある．
その後，あなたのプログラムは採点プログラムとやり取りを⾏う． 実験を⾏うには，最初に “?”からなる⾏を出⼒しなければならない．そして次の N ⾏では，電球の ON/OFF に関する N × Nの情報を出⼒しなければならない．ここで出⼒する情報は， 0 (OFF) と 1 (ON) からなる．その後，照らされている区画の数を表す 1 つの整数 ℓ (0 ≤ ℓ ≤ N 2 ) を読み込まなければならない．
最後に答えを出⼒したいときは，最初に “!” からなる⾏を出⼒し，その後 N ⾏にわたって上と同じ形式で区画の電球の情報を出⼒しなければならない．なお，正解 (Accepted) を出すためには，電球はすべての区画を明るく照らす必要があり，なおかつ ON にする電球の数が最⼩でなければならない．
その後，あなたのプログラムは終了しなければならない．
ここで，採点プログラムはアダプティブではない．すなわち，各電球の向きはやり取りが始まる前に決まっている．
各出⼒の最後には，必ず標準出⼒を ﬂush せよ．さもなくば，Time Limit Exceeded と判定される可能性がある．Python の場合，input() により⾃動的に ﬂush される．C++ の場合，cout << endl; によって，改⾏されるとともに⾃動的に ﬂush される．もし printfを使⽤する場合，fflush(stdout)を⽤いよ．

制約‧採点形式
3 ≤ N ≤ 100.
あなたのプログラムは最⼤ 2 000 回の実験を⾏うことができる (最後の答えの出⼒は実験回数に含まれない)．もし超過した場合，Wrong Answer と判定される．
あなたの解答は各⼩課題ごとに評価され，⼩課題にはそれぞれ配点が割り当てられている．各⼩課題は複数のテストケースからなる．各⼩課題について得点を得るためには，その⼩課題に含まれるすべてのテストケースに正解する必要がある．
⼩課題

配点制約

111N =3211N ≤ 103

最⼤ 78

追加の制約はない

lightbulbs (2 of 5)最後の⼩課題では，あなたの得点は実験回数によって決まる．具体的には，以下の式によって決められる．

⎧if 200 ≤ Q ≤ 2000,⎪(2000 − Q) ⋅ 29/900
score = ⎨58 + (200 − Q) ⋅ 4/23 if 85 ≤ Q ≤ 200,⎪⎩
78
if Q ≤ 85.
ここで，Q は実験回数が最も多かったテストケースにおける実験回数である．なお，得点は⼩数点以下切り捨てとなる．
以下のグラフは，すべてのテストケースで正解した場合における，Q の値と得点の関係を⽰している．
特に，この問題で 100 点を得るには，すべてのテストケースを 85 回以下の実験で解く必要がある．

テストのためのツール
あなたが解法をテストすることを容易にするため，簡単なツールがダウンロードできるようになっている．Kattis の問題ページ下部の attachments の項を⾒よ．ここで，本ツールを必ずしも使う必要はな
い．なお，Kattis で使⽤される実際の採点プログラムは，本ツールとは異なる．
本ツールを使うには，まず sample1.in のような⼊⼒ファイルを⽣成しなければならない．この⼊⼒ファイルでは，最初の⾏に整数 N ，次の N ⾏に各区画の情報を指定しなければならない．V は電球が縦⽅向であること，H は電球が横⽅向であることを意味する．具体例を以下に⽰す．
5
VVHVH
HVHHV
VHHVV
HHHVH
HHVVV
Python の場合，たとえば solution.py の場合，(通常は pypy3 solution.py とすれば実⾏できるが) 以下を実⾏しなければならない．

lightbulbs (3 of 5)python3 testing_tool.py pypy3 solution.py < sample1.inC++ の場合，まずコンパイルを⾏い (例: g++ -g -O2 -std=gnu++20 -static solution.cpp -osolution.out)，その後以下を実⾏しなければならない．
python3 testing_tool.py ./solution.out < sample1.in

例
サンプルテストケースでは，あなたのプログラムは最初に区画の⼤きさ N = 5 を読み込む．以下の図は，隠された各区画の情報 (プログラムはまだ知らない)，および正解例のうち 1 つを⽰している．正解
例では，5 個の電球を ON にすることで部屋全体を明るくしている．下図では，ON の電球は塗りつぶされており，照らされている区画は濃い⾊で表⽰されている．

このプログラムは下図に⽰す 2 回の実験を⾏う．1 回⽬の実験では，左上の 2 個の縦⽅向の電球を ONにすることで， 10 個の区画が照らされる． 2 回⽬の実験では 13 個の区画が照らされる．そして最後に，このプログラムは上図に⽰す答えを出⼒し，終了する．

lightbulbs (4 of 5)

採点プログラムの出⼒

あなたのプログラムの出⼒

5?
11000
00000
00000
00000
00000
10?
01000
01000
01000
00100
00000
13!
00100
00010
01000
00001
01000

lightbulbs (5 of 5)