Nultá série

Celý leták, který posíláme také papírově, v PDF.

Od 1. července do 20. srpna si můžete zasoutěžit v nezvyklých úlohách, alespoň pro KSP. Říkáme tomu „nultá série“, ale do 24. ročníku získané body započítávat nebudeme – očekáváme od vás, že budete řešit čistě z touhy dostat se za samou hranici možností svých neuronových sítí. Vaše snaha nám však může pomoct při výběru, koho pozvat jako náhradníka na Podzimní soustředění 2011.

V čem spočívá nezvyklost úloh? Předně, nečekáme popis správného řešení pro obecná data velikosti N, ale řešení samo pro daná data o přibližně šesti tisících položkách, které odevzdáte formuláři, který vyhodnotí správnost i kvalitu a hned zapíše výsledek do listiny.

Předem upozorňujeme, že od vás nečekáme optimální řešení úloh 4–6. Ve výsledkové listině bude na tomto místě uvedeno, jak moc dobrý byl váš pokus vzhledem k pokusům ostatních, a podle těchto čísel bude ona tabulka řazena. Odevzdávat bude moci kdokoliv (možná se zúčastní i někteří orgové), ale pořadí budeme číslovat jen u řešitelů přihlášených do 24. ročníku.

Výsledky

Výsledkovou listinu najdete na samostatné stránce. Vizualizace dat

Zadání

Stáhněte si přichystaný soubor se seznamem obcí České republiky. (Za poskytnutí dat, která by měla být platná k začátku roku 2011, děkujeme ČSÚ.) Na každém z jeho 6 251 řádek najdete následující údaje oddělené mezerou:

UTM? Neděste se, nemusíte zkoumat, o co jde. Máme prostě kartézský systém souřadnic a na jeho bodech sedí obce republiky. Vzdálenost mezi dvěma body tak můžete počítat Pythagorovou větou. Může vás potěšit, že jednotka v tomto souřadném systému odpovídá jednomu metru.

Jméno obce nebude potřeba – uvádíme ho jen, abyste si mohli zobrazit výsledek své práce v lidštější formě. Důležité je pořadové číslo obce, které je určeno implicitně, pořadím záznamů. Praha má pořadové číslo 0, Benešov 1, …

1. Osa

Občané prahnou po občanské válce, ale chtějí, aby to bylo fér. Najděte takovou svislici (přímku s konstantní x-ovou souřadnicí), aby byl rozdíl v součtech obyvatel obcí na obou stranách co nejmenší. Tato svislice ale nesmí procházet žádnou obcí, protože by ji pak frontová linie poničila. To by byla škoda.

Jako řešení odevzdejte jediné celé číslo – x-ovou souřadnici libovolné svislice, která řeší úlohu.

2. Těžiště

Nechť každá obce „váží“ tolik, kolik má obyvatel. Prostor mezi obcemi neváží nic. Která obec je nejblíže těžišti republiky?

Jako řešení odevzdejte jediné celé číslo – pořadové číslo hledané obce.

3. Nová hranice

Vláda se rozhodla, že je naše hranice zbytečně složitá. Nalezněte lepší!

Chceme, aby pro každé dvě obce byla úsečka, která je spojuje, v každém svém bodě součástí země, popř. součástí hranice, a aby bylo území státu nejmenší možné.

Odevzdejte soubor, kde bude na jediném řádku uveden mezerami oddělený seznam pořadových čísel obcí na hranici. Je jedno, kterou obci zvolíte za počátek.

4. Letáky

Letadlo potřebuje každému občanovi shodit na hlavu leták, ale zároveň ho převoz hromad papíru stojí drahé palivo. Abychom tuto spotřebu lépe uchopili, zavedeme si jednotku letákometry: když letadlo uletí s pěti letáky tři metry, musí na palivu zaplatit 15 letákometrů.

Najděte takovou posloupnost všech obcí v zemi, aby letadlo, které vystartuje z první obce, obletí všechny následující a přistane v poslední a které v každé obci ze seznamu postupně vyhodí tolik letáků, kolik tam žije obyvatel, spotřebovalo co možná nejméně letákometrů. Na začátku má samozřejmě právě tolik letáků, kolik je obyvatel ve všech obcích dohromady.

Odevzdejte soubor, jehož jediný řádek bude obsahovat seznam obcí pro cestu letadla. Řešení projde, pokud bude seznam obsahovat každou obec právě jednou. Bude tím kvalitnější, čím méně letákometrů letadlo spálí.

5. Rozvody

ČEPS se rozhodl, že stávající elektrická přenosová soustava nestačí nárokům třetího tisíciletí, celou ji zboural a má pět let na to, aby postavil novou. Pokud to nestihne, všichni občané si na život bez proudu zvyknou a rozvodová síť bude zbytečná.

Chce proto najít co možná nejkratší síť takovou, aby dosáhla do každé obce.

Odevzdejte soubor, který bude mít na každém řádku dvojici ne nutně celočíselných souřadnic s nejvíce 5 desetinými místy, které určují, z kterého místa na mapě na které chcete vést proud. Řešení projde, pokud bude možno z každé obce po vedení dojít do každé jiné. Ve výsledkovce se objeví součet délek všech vedení.

6. Kraje

Zatímco největší kraj, Středočeský, má přes milion obyvatel, Karlovarský kraj jich má jen 315 tisíc. To je nehorázná nespravedlnost, kterou je potřeba napravit!

Navrhněte nové rozdělení krajů, aby všech 13 současných krajských měst mělo každý svůj kraj, aby každý trojúhelník definovaný obcemi jednoho kraje neobsahoval (ani na své hranici) obce kraje jiného a aby byl součet rozdílů počtu obyvatel mezi každými dvěma kraji co nejmenší.

Praha má v systému krajů trochu zvláštní postavení a bude ho mít i v naší úloze. Budeme ji počítat za krajské město, které potřebuje svůj (Středočeský) kraj, ale zapomeneme na to, že má nějaké obyvatele – nebudeme je do počtu obyvatel kraje počítat.

Odevzdejte soubor, který bude obsahovat třináct řádek. Na každém řádku bude seznam pořadových čísel obcí kraje. Řešení projde, pokud budou splněny první dvě podmínky druhého odstavce. Třetí podmínka bude určovat kvalitu řešení.

Problémy?

Technické potíže s načítáním souborů a s odevzdáváním konzultujte na fóru. Diskuzi o tom, jak jste kterou úlohu řešili, si prosím nechte na září. Docela se na ni těšíme.