Csókavár

Két programozó a buszon

Lukáccsal jöttünk fel Budapestre a hétvégén. Mikor kifogytunk a témából feldobott egy jó gondolkodós feladatot, bosszúból én is egyet. (Mégis mi mást csinálna két programozó a szabadidejében?)

1. Ez állítólag Google felvételi feladat, mármint olyan felvételi beszélgetésre való. Értik…

Van egy 1 dimenziós bolygó (számegyenes), amire ledobunk két robotot, és közéjük egy bóját:

———R———-B——————-R—————

A robotok tudnak jobbra/balra menni, mindkét irányba két sebességgel. Ezen kívül ácsoroghatnak is. Van véges memóriájuk. Nem kommunikálhatnak egymással.

Feladat: adjunk algoritmust arra, hogy megtalálják egymást.

Az pl. nem jó, hogy az egyik robot áll, a másik pedig jobbra-balra megy egyre nagyobb kitéréssel, hiszen csak véges nagy a memóriája, a másik robot pedig bármilyen messze lehet. Tehát, ha túl messze van, akkora kitérést már nem tud szegény robot fejben tartani.

2. Adott egy n x m-es mátrix. A mátrix elemei izzók. Ezek lehetnek ki- vagy bekapcsolt állapotban. Műveletek: a mátrix bármelyik sorában ill. oszlopában egyszerre átállíthatjuk a lámpákat. Pl. egy 3×3-as mátrixban, először az első oszlopot, majd az első sort átállítva ezt kapjuk:

011
100
100

Probléma: szépen le volt kapcsolva az összes lámpa, mikor Agresszív Pistike egy óvatlan pillanatban (iskola helyett) összevissza kapcsolgatta a őket. 

Állítsuk vissza a kiindulási állapotot!