lightbulbs
Day2 Tasks

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

Icelandic (ISL)

C. Light Bulbs
Nafn Verkefnis

lightbulbs

Tímatakmörk

4 sekúndur

Minnistakmörk

1 gígabætStuttu eftir stofnun ljósaperufyrirtæki síns í Eindhoven árið 1981 gerði Frederik Philips mikla
uppgötvun: ljósaperur sem lýsa endalausa vegalengd í annaðhvort lóðrétta eða lárétta átt. Meðþessarri nýju uppgötvun vill hann gjörbreyta innanhúshönnun í nútímalegu húsnæði.
Hann býr til áætlun með syni sýnum Gerard um uppsetninguna. Þeir setja upp N 2 lampa í N × N
grind í herbergi. Þeir vilja lýsa allt herbergið með eins fáum lömpum og þeir geta til að spara
rafmagn. Sérhver lampi er annaðhvort lóðréttur, sem þýðir að hann lýsir upp alla reitina í eigin
dálki, eða láréttur, sem þýðir að hann lýsir alla reitina í eigin röð.
Myndin hér að neðan sýnir dæmi um lóðréttan (vinstra megin) lampa og láréttan (hægra megin)lampa.

Því miður voru þeir ekki að fylgjast með þegar þeir settu lampana upp og muna ekki hvaða lampar
eru láréttir og hvaða lampar eru lóðréttir. Í staðin framkvæma þeir tilraunir til að átta sig á hvaðalampa má nota til að lýsa allt herbergið. Gerard heldur sig inn í herberginu með lömpunum ámeðan Frederik stjórnar ﬂipunum frá öðru herbergi.
Í hverri tilraun mun Frederik kveikja eða slökkva á sérhverjum lampa og Gerard mun tilkynna
hversu margir reitir eru upplýstir. Reitur sem er upplýstur af tveimur eða ﬂeiri lömpum er talinneinu sinni. Það skiptir ekki máli hversu mörgum lömpum er kveikt á í tilraununum, en þeir eru aðdrífa sig og vilja framkvæma eins fáar tilraunir og þeir komast upp með.

lightbulbs (1 of 5)

Hjálpaðu þeim að ﬁnna val á lömpum sem lýsir allt herbergið með sem fæstum lömpum. Þeir geta
framkvæmt í mesta lagi 2 000 tilraunir. Þú færð samt ﬂeiri stig ef þeir framkvæma færri tilraunir.

Gagnvirkni
Þetta er gagnvirkt verkefni.
Forritið þitt skal fyrst lesa inn línu með einni heiltölu N , hæð og breidd grindarinnar.
Svo skal forritið þitt eiga samskipti við yﬁrferðarforritið. Til að framkvæma tilraun skaltu fyrst
skrifa línu með spurningarmerki „?“. Svo skalt þú skrifa N × N grind á næstu N línur, semtákna hvort sé kveikt eða slökkt á lömpunum. Nánar tiltekið skaltu á sérhverri þessarra línaskrifa út streng af lengd N sem samanstendur af 0 (slökkt) og 1 (kveikt). Forritið þitt skal svo
lesa eina heiltölu ℓ, þar sem 0 ≤ ℓ ≤ N 2 , fjöldi reita grindarinnar sem eru upplýstir með þvíað kveikja á tilteknu lömpunum.
Þegar þú vilt svara skaltu skrifa línu með upphrópunarmerki „!“. Svo skaltu skrifa N línur
fyrir grindina á sama formi og að ofan. Til að svarið þitt sé samþykkt þurfa lamparnir aðlýsa upp alla grindina og fjöldi lampa sem kveikt er á þarf að vera lágmarkaður.
Eftir þetta skal forritið þitt hætta keyrslu.
Yﬁrferðarforritið aðlagar sig ekki að tilraunum þínum, sem þýðir að uppsetning lampanna ágrindinni er fyrirfram ákveðin áður en gagnvirknin hefst.
Passaðu að sturta úr staðalúttaki eftir hverja tilraun, annars gæti forritið þitt fengiðdómsúrskurðinn „Time Limit Exceeded“. Í Python gerist þetta sjálfkrafa ef þú notar input() til aðlesa línur. Í C++ mun cout << endl; sturta eftir að hafa skrifað út nýja línu. Ef þú notar printf
skaltu einnig nota fflush(stdout).

Takmarkanir og Stigagjöf
3 ≤ N ≤ 100.
Þú mátt framkvæma mest 2 000 tilraunir. Að skrifa lokasvarið telst ekki sem tilraun. Ef þúnotar of margar tilraunir færðu dómsúrskurðinn „Wrong Answer“.
Lausnin þín verður prófuð á safni af prufuhópum og er hver hópur virði einhvers fjölda stiga. Hverprufuhópur inniheldur safn af prufutilvikum. Til að fá stigin fyrir prufuhóp þarftu að leysa sérhvert
prufutilvik í prufuhópnum.
Hópur

StigTakmarkanir

1

11N =3

2

11N ≤ 10

3allt að 78

Engar frekari takmarkanir

lightbulbs (2 of 5)Í síðasta prufuhópnum fara stigin þín eftir fjölda tilrauna sem þú framkvæmir og eru reiknuð
með eftirfarandi formúlu:⎧
ef 200 ≤ Q ≤ 2000,⎪(2000 − Q) ⋅ 29/900
score = ⎨58 + (200 − Q) ⋅ 4/23 ef 85 ≤ Q ≤ 200,⎪⎩
78
ef Q ≤ 85,
þar sem Q er hámarksfjöldi fjöldi tilrauna sem þú notaðir í einhverju prufutilviki. Stigin verðanámunduð niður að næstu heiltölu.
Graﬁð að neðan sýnir fjölda stiga, sem fall af Q, sem forritið þitt fær ef það leysir alla prufuhópa.
Til að fá fullt hús stiga í þessu verkefni, 100 stig samtals, þarftu að leysa hvert einasta prufutilvik
með mesta lagi 85 tilraunum hvert.

Prufutól
Til að bjóða þér upp á að prófa forritið þitt veitum við þér einfalt tól sem þú getur niðurhalað.
Sjáðu viðhengi („attachments“) neðst á Kattis síðunni. Notkun á tólinu er valkvæm og þú máttbreyta því. Athugaðu að alvöru yﬁrferðarforritið á Kattis er frábrugðið prufutólinu.
Til að nota tólið skaltu búa til inntaksskrá, til dæmis „sample1.in“, sem skal byrja á heiltölu N og áeftir fylgja N línur sem lýsa grindinni, þar sem V þýðir að lampinn sé lóðréttur og H þýðir aðlampinn sé láréttur. Til dæmis:
5
VVHVH
HVHHV
VHHVV
HHHVH
HHVVV
Fyrir Python forrit, eins og solution.py (venjulega keyrð með pypy3 solution.py) skal keyra
það með:lightbulbs (3 of 5)python3 testing_tool.py pypy3 solution.py < sample1.inFyrir C++ forrit skal fyrst þýða það (t.d. með g++-g-O2-std=gnu++20-staticsolution.cpp -o solution.out) og svo keyra það með:python3 testing_tool.py ./solution.out < sample1.inSýnidæmiÍ sýnidæmi gagnvirkninnar byrjar forritið á að lesa grindarstærðina N = 5. Eftirfarandi mynd sýnirföldu grindina sem forritið veit ekki og eitt af mörgum mögulegum svörum, sem notar ﬁmm
lampa til að lýsa upp alla grindina. Kveikt er á merktu lömpunum og dekkri reitirnir eru upplýstir.

Forritið framkvæmir tvær tilraunir eins og er sýnt að neðan. Í fyrri tilrauninni eru 10 reitir upplýstir
með tveimur lóðréttu lömpunum í efra vinstra horni. Í seinni tilrauninni eru 13 reitir upplýstir. Aðlokum skrifar forritið svarið sitt (sýnt að ofan) og hættir keyrslu.

lightbulbs (4 of 5)úttak yﬁrferðarforritsúttak forrits þíns5?
11000
00000
00000
00000
00000
10?
01000
01000
01000
00100
00000
13!
00100
00010
01000
00001
01000

lightbulbs (5 of 5)