Třetí série šestého ročníku KSP

Tyto úlohy pocházejí z desetileté ročenky KSP. Jejich řešení bohužel nemáme v elektronické podobě, takže na ně budete muset přijít sami.

Zadání úloh

6-3-1 AZAAZZAAA

V království AZAAZZAAA se rozhodli vyasfaltovat některé ze svých cest. Chtějí, aby po asfaltizaci bylo možné z libovolného města přejet do jiného města s použitím pouze vyasfaltovaných silnic. Zároveň chtějí, aby je to stálo co nejméně peněz, tedy aby vyasfaltovali co nejmenší počet kilometrů stávajících cest.

Vaším úkolem je napsat program, jenž pro zadanou síť cest, které jsou v království AZAAZZAAA, určí, které cesty je třeba vyasfaltovat, aby byly splněny požadavky obyvatel království AZAAZZAAA. Křižovatky cest jsou v království označeny čísly 1, … , n a vstupem programu je délka všech cest vedoucích mezi jednotlivými křižovatkami. Výstupem pak bude seznam cest, mezi kterými křižovatkami se mají vyasfaltovat.

6-3-2 Balič

Softwarová firma produkuje 6 druhů programů. Jednotlivé programy zabírají takovéto množství disket:

Program 1 1 disketa
Program 2 3 diskety
Program 3 4 disket
Program 4 5 disket
Program 5 8 disket
Program 6 9 disket

Tyto diskety balí do krabiček, do kterých se vejde nejvýše deset disket, přičemž diskety k jednomu programu (jedné instalace) musí být vždy spolu ve stejné krabičce disket (mohou ji sdílet s jiným programem).

Firma obdrží objednávku, což je uspořádaná šestice, kde jednotlivá čísla udávají, kolikrát se daný program požaduje (počet instalací). Vaším úkolem je napsat program, který pro danou objednávku určí, jak programy zabalit, aby se spotřeboval nejmenší možný počet krabiček na diskety.

6-3-3 Pakty

Na světě je N států. Ty mezi sebou uzavírají pakty. Pakt je uspořádaná čtveřice (X,Y,Z,W), která znamená „Když stát X napadne stát Y, pak stát Z napadne stát W“. Vaším úkolem je napsat program, který pro daný seznam paktů, které jsou ve světě uzavřeny, zjistí, zda existuje stát, který když napadne jiný stát, vyvolá tímto napadením světovou válku, tj. v důsledku uzavřených paktů se do války zapojí všechny státy světa. Zároveň také program vypíše průběh zapojování se států do války.

6-3-4 Die Flöche

Máme robota pro oplocování pozemku. Robot se řídí pomocí posloupnosti příkazů tvořené příkazy:

1 – otoč se o 90° po směru hodinových ručiček
2 – popojdi o metr dopředu.

Vaším úkolem je napsat program, který z posloupnosti příkazů, které obdržel robot a které jsou vstupem vašeho programu, určí plochu ohrazeného pozemku.

Příklad: Pro posloupnost příkazů 2,2,1,2,1,2,2,1,2 program vypíše Plocha=2.

Poznámka: Pro naše účely je Země rovina a zajímá nás menší z ploch.