Seminář č. 5

Dračí cestování

Dračí cestování není tak jednoduché, jak by se mohlo zdát. Let je pro tvora velikosti malého dopravního letadla namáhavý, a proto se musí drak dobře živit, aby měl dost sil na mávání křídly.

Největší pochoutkou (a zároveň jedinou potravinou, která má dostatečný energetický potenciál) je pro draka síra. Při letu drak spotřebuje 1 kg síry na 1 km.

Síra se bohužel ve Škytánii vyskytuje pouze u Ohnivé hory, takže veškerou síru na cestu si musel drak nést z Velkého pohoří. Délka trasy, kterou musel uletět, je 4200 km. Navíc si drak chtěl přivést co nejvíce síry s sebou, protože nevěděl, jak kvalitní a rozsáhlé budou místní sirné zásoby.

Zjistěte, jaké maximální množství síry si drak mohl přinést, když má nosnost 42 metráků (4200 kg) a ve Velkém pohoří bylo zrovna k dispozici 14 tun (14 000 kg) síry.

Drak si pochopitelně může cestou dělat překladiště síry, kde si kousek nákladu odloží a pak se pro něj vrátí.

(zdroj: KSP)

Pluky

Na monitoru se právě schyluje k velké bitvě mezi armádou hráče a armádou jeho počítače. Síly jsou vyrovnané, obě armády mají stejný počet pluků, ovšem jednotlivé pluky mohou být tvořeny různým počtem vojáků. Na začátku bitvy se pluky obou armád seřadí do dvou řad tak, že proti každému hráčovu pluku stojí právě jeden pluk patřící počítači. Potom začne vlastní boj. Pluky stojící proti sobě na sebe zaútočí. A protože v množství je síla, zvítězí ten z nich, který má více vojáků. Pokud náhodou mají soupeřící pluky stejný počet vojáků, vyhraje pluk patřící počítači.

Hráčova armáda má schopné špióny, kteří před bitvou zjistili, kolik vojáků má nepřítel v kterém pluku a jak jsou jeho pluky rozmístěny. Vaším úkolem je rozmístit na základě těchto informací hráčovy pluky tak, aby co nejvíce z nich svůj souboj vyhrálo.

(zdroj: MOP)

Pizza kolem

Marco se rozhodl, ze zužitkuje své kulinářské i cyklistické dovednosti a založí si firmu pro výrobu a rozvoz pizzy. Firmu plánuje provozovat tak, že vždy nejdříve bude shromažďovat objednávky a když jich bude dostatek, tak pizzy upeče, sedne na kolo a rozveze je zákazníkům. Protože Marco je lepší cyklista než kuchař, tak zatím ve své nabídce plánuje pouze jeden druh pizzy. Aby se ale odlišil od konkurence, tak přijímá objednávky i na šestinové části pizzy. Lze si u něj objednat například 1/6, 4/6 nebo 15/6 pizzy. Navíc, jako speciální službu zákazníkům, chce Marco pizzy pro každého zákazníka dodat co nejméně rozřezané (aby si zákazník sám mohl rozhodnout, jak si dále pizzu rozdělí). Proto například 4/6 pizzy chce dodat jako jeden kus příslušné velikosti a 15/6 chce dodat jako 2 celé pizzy a k nim jednu polovinu pizzy (Marco chce také dodat co nejvíce pizz vcelku, takže uspokojení této objednávky třemi kusy velikosti 5/6 nepřipadá v úvahu).

Až když Marco všude rozdal letáky propagující jeho novou firmu, tak si uvědomil, že díky jeho speciální službě zákazníkům není jednoduché zkombinovat objednávky tak, aby mu moc kusů pizzy nezbylo. Obrátil se proto na vás, abyste mu napsali program, který by mu s problémem pomohl. Pro začátek by mu stačil program, který na vstupu dostane objednávky a na výstup vypíše, kolik pizz má Marco napéct.

(zdroj: MOP)

Na doma, trénovací, rozmýšlecí

SPHERE:

UVA:

Uvažte algoritmus, nemusí být hladový?:

courses/a4b36acm2/2013_ls/seminar5.txt · Last modified: 2018/10/03 03:51 (external edit)