시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
3 초 | 1024 MB | 0 | 0 | 0 | 0.000% |
Låt oss definiera en labyrint på följande sätt:
Systrarna Rosa och Lila spelar ett spel som går ut på att Rosa först konstruerar en labyrint, varpå Lila försöker klara av den genom att gå från ingången till utgången. De har spelat några gånger nu, och Lila lyckas alltid vinna. Detta gör Rosa ganska frustrerad. Hon vill att hennes syster ska fastna i labyrinten för alltid.
Rosa har dock märkt att Lila alltid använder samma förutsägbara strategi. Närmare bestämt har hon en sträng $S$ med längden $L$, bestående av bokstäverna R
, G
och B
(röd, grön och blå). I drag nummer $i$ tittar Lila på det $i$:te tecknet, och följer korridoren med den färg som bokstaven representerar (om bokstaven är R
kommer Lila alltså gå genom den röda korridoren i det rum hon befinner sig i just nu). Efter $L$ drag börjar hon om genom att titta på det första tecknet igen. Om strängen är RGB
kommer hon med andra ord först gå genom den röda korridoren i ingången, sedan den gröna korridoren i rummet hon kom till, sedan den blå korridoren, den röda (nu har hon börjat läsa strängen från början igen), gröna, blå, röda, och så vidare. Notera att varje rum har exakt en korridor av varje färg, så det är unikt bestämt vilket rum hon går till i varje steg.
Figure 1: En exempellabyrint.
Din uppgift är att, givet $S$, konstruera en labyrint som Lila aldrig kan klara av.
Indatan innehåller strängen $S$ av längd minst $1$ och högst $1\,000\,000$.
I detta problem kan du dessutom ladda ner all indata här: labyrint.zip.
Börja med att skriva ut tre heltal $K$, $i$, $u$. $K$ ska vara antalet rum i labyrinten du konstruerar. $i$ och $u$ ska vara de noll-indexerade nummer (d.v.s mellan $0$ och $K - 1$) på rummen som är ingången och utgången i labyrinten.
Skriv sedan ut $K$ rader, ett för varje rum. Den $j$:te raden ska innehålla tre heltal $r$, $g$ och $b$ -- de rum som den röda, gröna respektive blå korridoren i det $j$:te rummet leder till.
Din labyrint måste uppfylla villkoren i problemlydelsen.
Totalt har problemet 10 testfall.
Låt $minK$ vara antalet rum i den minsta labyrinten någon deltagare lyckas konstruera på ett visst testfall, och $K$ antalet rum i din labyrint. Låt $$r_1 = \frac{K}{minK}$$ och $$r_2 = \frac{2|S|}{minK}$$ där $|S|$ är längden på strängen $S$.
Din poäng på det testfallet är då $$10 \cdot \left(1 - \frac{\log(r_1)}{\log(r_2)}\right),$$ eller 0 om K överstiger $2|S|$.
Under tävlingen kommer $minK$ sättas till ett värde beräknat utifrån en domarlösning.
RGB
4 0 3 1 3 2 0 2 3 3 1 0 2 0 1
Olympiad > Swedish Olympiad in Informatics > 2017 > KATT2 A번