Az X planéta lakói csak háromszög alalkú házakat építenek különleges módszerrel. Először egy egyenes falat építenek meg. Ezután egy már meglevő falhoz csatlakoztatva két új falat, egy új háromszög alakú házat alakítanak ki. Minden meglevő fal lehet kiinduló fala egy újabb háznak. Előfordulhat, hogy ezzel az építési módsszerrel épült ház teljesen tartalmazhat egy másikat (mint az ábrán látható).
Az ábrán a példának megfelelő házak építésének egy lehetséges sorrendjét láthatjuk. Azon sarkok sorszáma alá van húzva, amelyekben elhelyezett lámpák kezdetben égnek.
Minden sarokban elhelyeznek egy lámpát és egy kapcsolót. Egy kapcsoló az adott sarokban levő lámpa, és az összes olyan lámpa állapotát ellenkezőjére változtatja (ég vagy nem ég), amelyek egy itt kezdődő fal másik végén vannak.
Feladat:
Írj programot, amely meghatároz egy kapcsolási sorozatot, amelynek hatására az összes lámpa égni fog.Bemenet:Állománynév: X.INKimenet:
1. sor: N (Egyetlen egész szám, a sarkok száma. A sarkokat 1-től N-ig számozzuk)2..(2*N – 2). sorok: I J (Két egész szám, egyetlen szóközzel elválaszt-va, azt jelenti, hogy az I-edik és a J-edik sarok közé egy falat építettek)
2*N – 1. sor: S1 S2 ... SN (N egész szám (egy-egy szóközzel elválasztva), csak 0 vagy 1 lehet, a lámpák kezdeti állapotát adja meg; 0 jelenti, hogy nem ég a lámpa; 1 pedig, hogy ég.)
A bemenet biztosan a fenti feltételek szerint épített házakat ír le.
Állomány név: X.OUTKorlátok:
1. sor: L1 L2 ... LK (K egész szám, egy-egy szóközzel elválasztva, azon sarkok sorszámai, amelyekben elhelyezett kapcsolót átkapcsoljuk.)Ha több megoldás is van, csak egyet kell kiírni.
Ha nincs megoldás, akkor az állományba egyetlen sort kell írni, ami 0-t tartalmazzon.
3 < = N < = 1000Példa:
X.IN X.OUT 6
1 3
1 4
1 5
2 3
2 4
3 4
3 6
4 5
4 6
0 1 1 1 0 01 6
A közlekedési minisztérium útfelújítást tervez. Az úthálózat minden útja kétirányú, és pontosan két várost köt össze. Ugyanazon két város között legfeljebb 1 út van. A meglevő utakon bármely városból bármely másik városba el lehet jutni, egy vagy több lépésben.Egyszerre csak egy utat javítanak, ehhez azt le kell zárni, azonban biztosítani kell, hogy ekkor is el lehessen jutni bárhonnan bárhova. Ahhoz, hogy ez teljesüljön, először új utakat kell építeni, természetesen a lehető legkevesebbet. Új út nem lehet olyan városok között, ahol már van út.
Feladat:
Írj programot, ami megadja a lehető legkevesebb építendő utat.Bemenet:
Ha több megoldás is van, csak egyet kell kiírni.Állomány név: ROADS.INKimenet:
1. sor: N M (Két egész szám, egyetlen szóközzel elválasztva, a városok N száma és az utak M száma. A városokat 1-től N-ig sorszámozzuk.)
2..M+1. sorok: T1 T2 (Két egész szám, szóközzel elválasztva: azon városok sorszáma, amelyek között van út.)Állomány név: ROADS.OUTMegjegyzés:
1. sor: K (Egy egész szám, az építendő utak minimá-lis száma.)
2..K+1. sorok: C1 C2 (Két egész szám, egyetlen szóközzel elvá-lasztva: egy új út által összekötött két vá-ros sorszáma.)A kimenetben a várospárok sorrendje tetszőleges lehet.Korlátok:3 < = N < = 2500Példa:
2 < = M < = 20000
ROADS.IN ROADS.OUT 4 3
1 2
2 3
2 42
1 4
1 3
Definíció: A caterpillar egy speciális fa a következő tulajdonsággal: létezik olyan lánc, amelyre igaz, hogy minden pont vagy rajta van a láncon, vagy egyetlen él köti össze egy láncon levő ponttal. Az alábbi ábrákon két caterpillar látható. A szürke pontok alkotják a láncot.
1. ábra 2. ábra A lánc többféleképpen is felépíthető: például a 2. ábrán a 3-2-5-9 pontok is alkothatnák a láncot.
Feladat:
Adott egy N pontot tartalmazó caterpillar. Írj programot, amely az 1..N számokkal címkézi meg a pontokat, úgy, hogy teljesüljön:A 2. ábrán látható caterpillart az alábbi ábra szerint lehet megcímkézni, ahol az élekhez rendelt érték a végpontok címkéi különbségének abszolút értéke:
- Minden címke pontosan egyszer használható;
- Nem lehet a fának két olyan (különböző) éle, melyek végpontjain levő címkék különbségének abszolút értéke megegyezne.
Bemenet:Állomány név: CP.INKimenet:
1. sor: N (Egyetlen egész szám, a pontok száma)
2..N. sorok: X Y (Két egész szám, egyetlen szóközzel elválasztva, az X és Y pontok között van él.)
A bemenet helyes, és a fa biztosan caterpillar.Állomány név: CP.OUTKorlátok:
1. sor: L1 L2 ... LN (N egész szám, egy-egy szóközzel elválaszt-va, ahol Li az i-edik ponhoz rendelt címke.)
Ha több megoldás lenne, csak egyet kell kiírni. Ha nem létezik a leírásnak megfelelő címkézés, akkor az állomány egyetlen sorába az IMPOSSIBLE szót kell írni.2 < = N < = 10000Példa:Az alábbi bemenet (CP.IN) a 2. ábrán látható caterpillart adja meg és a címkézés a 3. ábrának megfelelő (CP.OUT).
CP.IN CP.OUT 9
1 2
6 5
5 7
4 2
2 3
8 5
2 5
5 98 1 5 2 9 4 6 3 7
