Nemzetközi Informatikai Diákolimpia 1994

Az alábbi ábra egy háromszöget mutat. Írj programot, amely kiírja a háromszög felső csúcsából induló és a háromszög alsó sorában végződő számsorozatok összege közül a legnagyobbat!
 

				7
			3		8
		8		1		0
	2		7		4		4
4		5		2		6		5

Szabályok:

• Minden lépésben átlósan balra lefelé vagy jobbra lefelé lehet haladni.
• A háromszög sorainak száma 1 és 100 között lehet.
• A háromszögben 0 és 99 közötti egész számok vannak.

Bemennet:

Az INPUT.TXT állomány első sorában a háromszög sorainak száma van, amelyet soronként követnek a háromszög egyes soraiban levő számok.

Kimenet:

A maximális összeget egész számként kell beírni az OUTPUT.TXT állományba.

Példa:
 

INPUT.TXT	OUTPUT.TXT
5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5	30

A következő ábra egy kastély alaprajzát mutatja Feladat:

Írj programot, amely meghatározza, hogy

1. hány szoba van a kastélyban,
2, mekkora a legnagyobb szoba,
3. melyik falat kell kivenni ahhoz, hogy olyan nagy szobát hozzunk létre, amekkorát csak lehetséges!

A kastély alapterülete M*N négyzetre van osztva (M<=50, N<=50). Egy-egy négyzet falainak száma 0 és 4 között lehet.

Bemenet:

Az INPUT.TXT állományban számok írják le az alaprajzot, mégpedig négyzetenként egy-egy egész szám.

• Az állományban az első szám az alaprajz sorainak, a második pedig az oszlopainak a számát adja meg.
• Az ezután következő sorokban egy-egy négyzetet írnak le a számok (0<=p<=15). Ez a szám a következő kódok összegeként áll elő: 1 (nyugati fal), 2 (északi fal), 4 (keleti fal), 8 (déli fal). A belső falakat kétszer adjuk meg, pl az (1,1) négyzet déli fala a (2,1) négyzet északi falaként is szerepel.
• A kastélyban legalább 2 szoba van.

Kimenet:

Az OUTPUT.TXT állományba három sort kell írni. Az első sorba a szobák számát, a második sorba a legnagyobb szoba területét (a négyzetek számával kifejezve), végül a harmadik sorba az eltávolítandó fal leírását (először az eltávolítandó fal melletti négyzet sorának, azután oszlopának a számát kell megadni, majd pedig azt, hogy ebben a négyzetben melyik égtáj felé esik az eltávolítandó fal - az égtáj nevét angolul kell kiírni). A legutolsó kérdésre vonatkozó lehetséges megoldások közül elegendő csupán egyet megadni.

Példa:
 

INPUT.TXT	OUTPUT.TXT
4 7 11  6 11  6  3 10  6  7  9  6 13  5 15  5  1 10 12  7 13  7  5 13 11 10  8 10 12 13	5 9 4 1 E

Az ábrán egy négyzet látható. Minden sora, minden oszlopa és a két főátlója egy-egy ötjegyű prímszámnak olvasható. A sorokat balról jobbra, az oszlopokat fölülről lefelé, a két főátlót pedig balról jobbra kell kiolvasni. Az INPUT.TXT állományból beolvasandó adatok alapján írj programot, amely ilyen négyzeteket készít!

• A prímszámokban a számjegyek összegének ugyanannak kell lenni (ez a példában 11).
• A bal felső sarokban levő számjegyet előre megadjuk (a példában ez a szám 1).
• Ugyanaz a prímszám egynél többször is felhasználható ugyanabban a négyzetben.
• Ha több megoldás is van, akkor az összeset meg kell adni.
• A prímszámok nem kezdődhetnek nullákkal, azaz például a 00003 nem ötjegyű prímszám.

1	1	3	5	1
3	3	2	0	3
3	0	3	2	3
1	4	0	0	3
3	3	3	1	1

Bemenet:

A program az INPUT.TXT  állományból olvassa be az adatokat. Az első szám a prímszámok számjegyeinek összege, a második pedig a bal felső sarokba írandó számjegy. Az állomány két sorból áll. (A tesztadatokra mindig van megoldás.)

Kimenet:

Minden megtalált megoldást 5 sorban, soronként egy-egy ötjegyű prímszámmal írj be az OUTPUT.TXT állományba! A megoldások között üres sor lehetséges, de nem kötelező.

Példa:
 

INPUT.TXT	OUTPUT.TXT
11 1	11351 14033 30323 53201 13313 11351 33203 30323 14003 33311 13313 13043 32303 50231 13331