IPSC 1999

Bulbville egy kisváros. A főtere mintha Las Vegasban lenne, tele a helyi cégek színesen villogó reklámtábláival. Azonban egyik, főtéren lakó befolyásos család panaszkodni kezdett, hogy bizonyos reklámtáblák bevilágítanak házuk ablakain. Ezért azt követelték, hogy azokat kapcsolják ki éjszakára.

A reklámtáblák négyzet alakúak, N izzósorból állnak, s minden sorban pontosan N izzó van. A táblához N kapcsoló tartozik, minden sorhoz és minden oszlophoz egy-egy. Az adott sorhoz tartozó kapcsoló kioltja a működő izzókat és bekapcsolja a többit. (Hasonló a helyzet az oszlopokkal.) Lehetséges, hogy nem lehet egyszerre minden izzót kikapcsolni.

Határozd meg a reklámtábla olyan beállítását, amelyben a minimális számú izzó világít, amely elérhető a kapcsolók használatával.

Bemenet:

A bemeneti állomány egy reklámtábla kezdeti állapotát írja le. Az első sor N értékét tartalmazza, amely a tábla méretét határozza meg. A következő N sorban egy-egy N elemű számsor található, szóközzel elválasztva. A szám 1, ha az izzó világít és 0, ha nem.

Kimenet:

A kimeneti állomány első sora az M számot tartalmazza, amely a világító izzók minimális számát adja meg. A következő sorok a bemenethez hasonló formában írják le a reklámtábla kiinduló állapotból elérhető egyik lehetséges állapotát, amikor pontosan M izzó világít.

Példa:
 

PANEL.IN	PANEL.OUT
4 1 0 1 1 1 0 1 0 1 1 1 0 0 1 0 0	3 0 0 0 0 0 0 0 1 0 1 0 1 0 0 0 0

Doktor Jones híres archeológus. Az utóbbi időben a Tiribaki szigeteken kutatott. Leghíresebb felfedezése a Meteoronome volt - egy gép, amelyet a tiribaki főpapok használtak időjóslásra. A Meteoronome-ot az istenek alkották a világ keletkezésekor. A tiribakiak minden nap használták a gépet. Eredményként a gép előállított egy számot, a következő napra várható csapadékmennyiséget. A gomb i-edik megnyomását követően (a gombnyomásokat a világ kezdetétől számolják), a Meteoronome megadja a várható csapadékmennyiséget a világ keletkezésétől számított i-edik napra.

Sajnos a Meteoronome-ot nem használták néhány ezer évig, így senkisem tudta, hogy hány lépést kell tenni az aktuális dátum eléréséig. A kutatók nagy erőfeszítéseket tettek, hogy megállapítsák, hogy működik a Meteoronome. Matematikai modelt állítottak fel: A Meteoronome-ot inicializálták két egésszel, az s[0], t[0] értékekkel. Az i-edik lépésben a Meteoronome a következő értékeket számította ki.

s[i] = (78901 + 31*s[i-1]) mod  699037
t[i] = (23456 + 64*t[i-1]) mod 2097151

a kimenet az i-edik lépésben
a[i]=(s[i] mod 100 + 1) * (t[i] mod 100 + 1)

Doktor Jones barátja, Linda Watson most tervezi a szabadságát a Tiribaki szigetekent tölteni. Szeretne addig maradni, amíg csak lehet, de utálja az esőt. Addig marad, míg nem esik M miliméter csapadék Tiribakin otttartózkodása alatt.

Doktor Jones segíteni akar barátjának és meg akarja keresni a leghosszabb periódust, amelyet biztonságosan Tiribakin tölthet. Ennek érdekében N lépést tesz a Meteoronome-mal. Így megkapja az a[1], a[2], ..., a[N] sorozatot, amely jóslás a következő N napra. Meg akarja találni a legnagyobb K értéket, amelynél minden K nap hosszúságú pediódusban az i-edik naptól a j-edik napig a jósolt csapadék összege (a[i]+a[i+1]+...+a[j]) nem haladja meg az M milimétert. Linda így biztos lehet benne, ha nem marad K napnál tovább, el tudja viselni az esőt. (Az N értéke elég nagy.)

Bemenet:

A bemeneti állomány néhány adatsorból áll. Az első sorában álló szám az adatsorok száma. Minden adatsor 4 egész számot tartalmaz, szóközzel elválasztva egymástól. Az első két érték s[0] és t[0], vagyis a Meteoronom kezdőértékei, a harmadik szám N értéke, vagyis a vizsgált időszak hossza, a negyedik M értéke pedig a maximális csapadékmennyiség.

Kimenet:

A kimeneti állományban tesztesetenként egyetlen sornak, benne egyetlen számnak kell szerepelnie. Annak a K értéknek, amely a fenti feltételeknek megfelelel.

Példa:
 

RAIN.IN	RAIN.OUT
1 123456 123456 10 10000	2

A fenti bemenetre a következő a[i] értékeket kapjuk: 4664,1248,267,4900,837,4048,990,6935,1155,490 Van három egymást követő nap, amikor a csapadék mennyisége meghaladja a 10000 millimétert, így a K értéke a 2 lesz.

Rómeó és Júlia egymásba habarodtak. Családja megtiltotta Júliának, hogy találkozzon Rómeóval, s Rómeó családja is hasonlóképpen cselekedett. Szerencsére Júliát vasárnap délutánonként elengedték énekelni a kórusba. Pontosan 4 órakor indulhatott el otthonról, és a legrövidebb úton kellett a templomba mennie. Rómeó hasonló helyzetben van, minden vasárnap csak a legközelebbi futballstadionba mehet el. Ő is pontban négykor indul, s neki is a legrövidebb úton kell haladnia.

Júlia a templomba menet minden vasárnap reménykedik, hogy találkozik a futballozni siető Rómeóval.

Bemenet:

A bemenet több adatsort tartalmaz. Minden adatsor egy-egy várost ír le.
Az első sor két egészet, az N és M számokat tartalmazza, ahol az N a városbeli útkereszteződések száma, M pedig az utcák számát adja meg. A kereszteződéseket 1-től N-ig sorszámozzuk. Minden utca pontosan két kereszteződéshez kapcsolódik. A második sorban négy egész szám található, a JS, JG, RS, RG. Júlia a JS-sel jelölt kereszteződésben lakik, és a JG kereszteződésben lévő templomba jár. Rómeó az RS-ben lakik, a stadion pedig RG-ben van. Az ezt követő M sorban három-három szám áll, amelyek egy-egy utcát írnak le. Az első két szám az utcavégi kereszteződéseket adja meg, a harmadik pedig a végigsétáláshoz szükséges percek száma.
Az utolsó adatsort a -1 érték követi.

Kimenet:

Meg kell határoznod, hogy Rómeó és Júlia találkozik-e. Ne feledjük, hogy mindkettőjüknek a legrövidebb úton kell haladniuk. Ugyanakkor indulnak, s csak akkor találkoznak, ha egy kereszteződésbe ugyanakkor érkeznek. Ha nem találkoznak, a kimeneti állományba a -1 értéket kell írni, egyébként pedig az indulástól a találkozásig eltelt időt.

Példa:
 

RJ.IN	RJ.OUT
7 9 1 4 7 1 2 10 2 3 10 3 4 10 4 5 15 5 1 15 1 6 10 2 7 5 5 7 15 5 6 10 2 1 1 2 2 1 1 2 10 -1	15 -1