lightbulbs
Day2 Tasks
English (ISC)

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

C. Light Bulbs
Problem Namelightbulbs

Time Limit

4 seconds

Memory Limit

1 gigabyte

Shortly after founding his lightbulb company in Eindhoven in 1891, Frederik Philips made a great
discovery: lightbulbs that light up an inﬁnite ray in the horizontal or vertical direction. With thisnew discovery, he wants to revolutionize the interior design of modern homes.
He plans an elaborate installation with his son, Gerard. They install N 2 lamps in an N × N grid ina room. They want to light up the whole room with as few lamps turned on as possible to saveelectricity. Each lamp is either vertical, meaning it lights up all squares in its column, or horizontal,
meaning it lights up all squares in its row.
The illustration below shows an example of a vertical (left) and a horizontal (right) lamp.

Unfortunately, they did not pay attention when installing the lamps and do not remember whichlamps light up horizontally or vertically. Instead, they conduct some experiments to ﬁgure out
which lamps to use to light up the whole room. Gerard stays in the room with the lamps, while
Frederik operates the switches from another room.
In each experiment, Frederik turns each lamp on or oﬀ and Gerard reports how many squares are
lit up in total; a square that is lit up by two or more separate lamps is only counted once. It does
not matter how many lamps are turned on during the experiments, but they are in a rush andideally want to conduct as few experiments as possible.

lightbulbs (1 of 5)

Help them ﬁnd an arrangement of lamps that lights up the whole room and uses the fewest lamps.
They can conduct at most 2 000 experiments. However, you will get a higher score if they use fewer
experiments.

Interaction
This is an interactive problem.
Your program should start by reading a line with an integer N , the height and width of thegrid.
Then, your program should interact with the grader. To conduct an experiment, you shouldﬁrst print a line with a question mark “?”. On the next N lines, output an N × N grid
specifying which lamps are lit. Speciﬁcally, on each of these lines, output a string of length
N , consisting of 0's (turned oﬀ) and 1's (turned on). Then, your program should read a single
integer ℓ (0 ≤ ℓ ≤ N 2 ), the number of grid squares lit up by turning on the lamps speciﬁed.
When you want to answer, print a line with an exclamation mark “!”, followed by N lines
with the grid in the same format as above. In order for your answer to be accepted, thelamps must light up the whole grid and the number of turned-on lamps must be thefewest possible.
After this, your program should exit.
The grader is non-adaptive, meaning that the grid of lamps is determined before the interaction
begins.
Make sure to ﬂush standard output after issuing each experiment; otherwise, your program might
get judged as “Time Limit Exceeded”. In Python, this happens automatically as long as you use
input() to read lines. In C++, cout << endl; ﬂushes in addition to printing a newline; if using
printf, use fflush(stdout).

Constraints and Scoring
3 ≤ N ≤ 100.
You can issue at most 2 000 experiments (printing the ﬁnal answer does not count as anexperiment). If you exceed this, you will get the verdict “Wrong Answer”.
Your solution will be tested on a set of test groups, each worth a number of points. Each test groupcontains a set of test cases. To get the points for a test group, you need to solve all test cases in thetest group.

lightbulbs (2 of 5)Group

Score

Limits111N =3

211N ≤ 10

3up to 78

No additional constraints

In the ﬁnal test group, your score depends on the number of experiments you conduct,calculated by the following formula:⎧if 200 ≤ Q ≤ 2000,⎪(2000 − Q) ⋅ 29/900
score = ⎨58 + (200 − Q) ⋅ 4/23 if 85 ≤ Q ≤ 200,⎪⎩
78if Q ≤ 85,
where Q is the maximum number of experiments used on any test case. The score will be rounded
down to the nearest integer.
The plot below shows the number of points, as a function of Q, your program will get if it solves all
test groups. To obtain a full score of 100 points on this problem, you must solve each test caseusing at most 85 experiments.

Testing ToolTo facilitate the testing of your solution, we provide a simple tool that you can download. See“attachments” at the bottom of the Kattis problem page. The tool is optional to use. Note that theoﬃcial grader program on Kattis is diﬀerent from the testing tool.
To use the tool, create an input ﬁle, such as “sample1.in”, which should start with a number N
followed by N lines specifying the grid, where V means that the lamp lights up its column and H
means that it lights up its row. For example:

lightbulbs (3 of 5)

5
VVHVH
HVHHV
VHHVV
HHHVH
HHVVV
For Python programs, say solution.py (normally run as pypy3 solution.py):
python3 testing_tool.py pypy3 solution.py < sample1.in
For C++ programs, ﬁrst compile it (e.g. with g++-g-O2-std=gnu++20-static

solution.cpp -o solution.out) and then run:python3 testing_tool.py ./solution.out < sample1.in

ExampleIn the sample interaction, the program starts by reading the grid size N = 5. The following ﬁgureshows the hidden grid (which the program does not know) and one of many potential answers,
using ﬁve lamps to light up the whole grid. The marked lamps are turned on and the darker
squares are lit up.

The program performs two experiments as illustrated below. In the ﬁrst experiment, a total of 10squares are lit up using the two vertical lamps in the top left corner. The second experiment lights
up a total of 13 squares. Finally, the program writes its answer (illustrated above) and exits.

lightbulbs (4 of 5)

grader output

your output

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

lightbulbs (5 of 5)