Közép-európai Informatikai Olimpia 1999

A Zanzibár szigeti utazási iroda városnéző körutakat szervez. A legnagyobb nyereséget szeretné elérni, ezért a legrövidebb körutat kell megtalálnia.
A városban N kereszteződés van, amiket 1-től N-ig sorszámozunk. A kereszteződéseket M kétirányú él köti össze, amiket 1-től M-ig sorszámozunk. Két kereszteződés között több, különböző hosszúságú él is lehet, de egy kereszteződésből önmagába nem vezethet él.
Minden körút kereszteződések egy x₁, …, x_k sorozata, ahol k>2 és x₁, …, x_k mind különböző, valamint az x_i és az x_i+1, illetve az x_k és x₁ kereszteződéseket valamelyik megadott él köti össze. A körút hossza a benne levő élek megadott hosszának összege.
Írj programot, ami kiszámít egy legrövidebb körutat, ha van ilyen; illetve megmondja, ha nem létezik ilyen.

Bemenet:

A TRIP.IN állomány első sorában 2 pozitív egész szám van: a kereszteződések N száma (N<=100) és az élek M száma (M<=10 000). A következő M sor mindegyike egy-egy élet ad meg. Három egész szám van benne: az első és a második a két kereszteződés sorszáma, a harmadik a köztük levő él hossza (500-nál kisebb pozitív egész szám), egy-egy szóközzel elválasztva.

Kimenet:

A TRIP.OUT állományba egyetlen sort kell írni. A tartalma a ’No solution.’, ha nem létezik körút, egyébként pedig a körutat megadó kereszteződések x₁, …, x_k sorozata, egy-egy szóközzel elválasztva. A körút felsorolása a körútban levő bármelyik kereszteződés sorszámával elkezdhető. Ha több minimális hosszú körút is van, akkor bármelyik megadható.

Példa:

TRIP.IN	TRIP.OUT
5 7 1 4 1 1 3 300 3 1 10 1 2 16 2 3 100 2 5 15 5 3 20	1 3 5 2
4 3 1 2 10 1 3 20 1 4 30	No solution.

Egy 4x4-es sakktáblán 8 fehér és 8 fekete kő van, mezőnként 1. Egy ilyen elrendezést játékállásnak hívunk. Két kő szomszédos, ha oldalukkal érintkező mezőkön vannak, azaz mindegyiknek legfeljebb 4 szomszédja lehet. A játékban egy lépés azt jelenti, hogy felcserélünk két szomszédos követ. Adott kezdő és végző játékálláshoz meg kell adni egy olyan legrövidebb lépéssorozatot, amellyel a kezdőből a végző játékállás elérhető.

Bemenet:

A GAME.IN állomány első 4 sora a kezdő játékállást adja meg. Minden sorban 4 számjegy van, 0 jelenti a fehér követ, 1 pedig a feketét. A sorok felülről lefelé sorrendben vannak, a soron belül a számjegyek balról jobbra. A számjegyek között nincs szóköz! Az ötödik sor üres! Az ezt követő 4 sor a végző játékállást adja meg, a kezdőhöz hasonlóan.

Kimenet:

A GAME.OUT állomány első sorába a lépések minimális M számát kell írni. A következő M sor rendre a lépéseket adja meg. Egy sor 4 pozitív egész számot (R₁, C₁, R₂, C₂) tartalmaz, egy-egy szóközzel elválasztva. Ezek jelentése: a lépéssel az (R₁, C₁) és az (R₂, C₂) szomszédos mezőn (R a sor, C az oszlopindex) lévő köveket kell felcserélni. A sorokat 1-től 4-ig felülről lefelé, az oszlopokat pedig 1-től 4-ig balról jobbra sorszámozzuk, vagyis a tábla bal felső sarkának koordinátái: (1,1). Ha több minimális lépésszámú sorozat is létezik, közülük egyet kell megadni.

Példa:

 

GAME.IN	GAME.OUT
1111 0000 1110 0010 1010 0101 1010 0101	4 1 2 2 2 1 4 2 4 3 2 4 2 4 3 4 4

Épitőkockákból egy téglalap alakú, KxL méretű területre tornyot építünk (K a szélessége, L a hosszúsága a területnek). A KxL mező mindegyikére tehetünk egy vagy több kockát egymásra, de üresen is hagyhatjuk. Ismerjük az építendő torony vetületét elölről és jobb oldalról, de nem tudjuk, hogy melyik mezőn hány kocka van. (Lásd az ábrát az angol szövegben!)
Írj programot, ami megadja, hogy maximum, illetve minimum hány kockából állhat az a torony, aminek a két vetületét ismerjük, illetve megmondja, ha a vetületek alapján nem építhető torony.

Bemenet:

A TOWN.IN állomány első sora a K és L pozitív egész számokat tartalmazza, egyik sem nagyobb 100 000-nél. A következő K sor a elölről vett vetületet írja le. Mindegyikben egyetlen szám van, ami balról jobbra haladva megadja, hogy hány kocka látható a elölről vett vetületben, azaz mekkora a legmagasabb torony az adott oszlopban. A következő L sor a jobb oldalról vett vetületet írja le az első sortól a legutolsóig, az előbbihez hasonlóan. A torony magassága legfeljebb 5000 kocka lehet. Az építésnél felhasználható kockák száma nem haladja meg a 2 000 000 000-ot.

Kimenet:

A TOWN.OUT állományba egyetlen sort kell irni. A tartalma a ’No solution.’, ha nem létezik a vetületeknek megfelelő torony, egyébként pedig két egész szám. Az első a vetületeknek megfelelő legkevesebb, a második pedig a legtöbb kockából építhető torony kockaszáma.

Példa:

TOWN.IN	TOWN.OUT
4 3 1 3 4 2 1 4 2	10 21
2 2 4 1 1 3	No solution.