Na řešení úloh máte 4,5 hodiny čistého času. Při soutěži je zakázáno používat jakékoliv pomůcky kromě psacích potřeb a přiděleného počítače (tzn. knihy, kalkulačky, mobily, apod.).
Řešením každého příkladu je zdrojový kód programu zapsaný v programovacím jazyce Pascal, C nebo C++. Řešení odevzdáváte pomocí soutěžního systému CMS, který ho automaticky otestuje na připravených sadách testovacích dat. Za každou úlohu můžete získat až 15 bodů. Detaily hodnocení naleznete v letáku s popisem prostředí. Podrobnější informace o testovacích datech najdete na konci zadání každé úlohy.
| Program | odpory.pas / odpory.c / odpory.cpp | Vstup a výstup | standardní vstup a výstup |
| Časový limit | řádově sekundy |
| Paměťový limit | 1 GB |
Šílený vědec sestavuje šílený experiment. Jako jednu ze součástek potřebuje odpor šíleně přesné hodnoty. Ve skříni má spoustu různých odporů, z nichž chce tento odpor sestavit. Je ovšem šíleně konzervativní a věří pouze sériovému spojení odporů (které sčítá jejich hodnoty). Navíc má v experimentálním zařízení místo pro nejvýše 4 odpory. Pomozte mu najít vhodnou kombinaci odporů.
Je dáno N navzájem různých celých čísel, udávajících hodnoty odporů v nanoohmech, a požadovaná hodnota X. Určete, zda se dá X vyjádřit jako součet nejvýše 4 ze zadaných čísel.
První řádek vstupu obsahuje dvě celá čísla X a N oddělená mezerou (1 ≤ X ≤ 109, 1 ≤ N ≤ 2 000). Na i-tém z N následujících řádků je jedno celé číslo ai (1 ≤ ai ≤ 109). Čísla a1, …, aN jsou navzájem různá.
Vypište nanejvýš 4 navzájem různá čísla oddělená mezerami. Součet těchto čísel musí být roven X a každé z nich musí být rovno jednomu z čísel a1, …, aN. Jestliže existuje více řešení, vypište libovolné z nich. Jestliže řešení neexistuje, vypište řetězec Konec sveta se odklada.
Vstup: 10 5 1 4 2 5 3 Výstup: 3 2 5
Jiná možná řešení jsou například 2 3 5 či 1 2 3 4.
Vstup: 15 5 1 4 2 5 3 Výstup: Konec sveta se odklada
Správné řešení, které úlohu efektivně vyřeší se zadanými omezeními na N a X, získá 15 bodů. V testovacích vstupech, za něž lze získat celkem 7 bodů, platí X ≤ 10 000. V testovacích vstupech, za něž lze získat celkem 3 body, je X součtem nejvýše dvou čísel ze vstupu.
| Program | kocourkov.pas / kocourkov.c / kocourkov.cpp | Vstup a výstup | standardní vstup a výstup |
| Časový limit | řádově sekundy |
| Paměťový limit | 120 MB |
Kocourkovští radní přemýšleli, jak by do svého města mohli nalákat více turistů. Při zkoumání turistických prospektů zjistili, že jejich město nemá narozdíl od mnoha dalších svůj aquapark, řeku s nábřežími, lyžařské středisko a mnoho dalších lákadel. Protože však byli limitováni rozpočtem města, rozhodli se vybudovat jen jednu z těchto atrakcí a volba padla na řeku.
Naplánovali tedy výstavbu dlouhého vodního kanálu. Na každé jeho straně vybrali místa, kde by mohly být mosty. Bohužel koordinace plánování selhala. Vybraná místa nebyla na protilehlých pozicích podél kanálu a co hůř, vícepráce při stavbě kanálu způsobily, že na výstavbu mostů již nezbyly žádné peníze. Radní se proto rozhodli mezi vybranými místy místo mostů zřídit přívozy.
Vaším úkolem je určit dvojice míst na levé a pravé straně kanálu, která mají být spojena přívozy tak, aby každé místo bylo spojeno alespoň s jedním místem na druhé straně kanálu a součet délek zřízených přívozů byl nejmenší možný. Pokud existuje více takových řešení, vypište libovolné z nich.
První řádek vstupu obsahuje čtyři celá čísla, L, S, A a B, oddělená jednou mezerou, která udávají délku kanálu, jeho šířku a počet vybraných míst na levé a pravé straně. Můžete předpokládat, že platí 1 ≤ L ≤ 2 000 000 000, 1 ≤ S ≤ 1 000 a 1 ≤ A,B ≤ 20 000.
Následuje A řádků, z nichž i-tý obsahuje vzdálenost ai i-tého vybraného místa na levé straně kanálu od počátku kanálu.
Poté následuje B řádků, z nichž j-tý obsahuje vzdálenost bj j-tého vybraného místa na pravé straně kanálu od jeho počátku.
Můžete předpokládat, že všechny vzdálenosti ai (1 ≤ i ≤ A) a bj (1 ≤ j ≤ B) jsou celá čísla, žádná dvě vybraná místa nejsou stejná a na vstupu jsou místa zadána dle rostoucí vzdálenosti od počátku kanálu, tj., že platí 0 ≤ a1 < … < aA ≤ L a 0 ≤ b1 < … < bB ≤ L.
První řádek výstupu obsahuje jedno celé číslo K, které udává, kolik přívozů je třeba zřídit. Každý z následujících K řádků obsahuje dvě celá čísla i a j, která udávají, že mezi i-tým místem na levé straně kanálu a j-tým místem na pravé straně kanálu má být zřízen přívoz.
Vstup: 10 5 3 2 0 5 10 2 8 Výstup: 3 1 1 2 2 3 2
Vstup: 1000 1 3 3 0 1 1000 0 999 1000 Výstup: 4 1 1 2 1 3 2 3 3
Správné řešení, které úlohu efektivně vyřeší se zadanými omezeními, získá 15 bodů. V testovacích vstupech, za něž lze získat celkem 10 bodů, platí A, B ≤ 1 000. V testovacích vstupech, za něž lze získat celkem 3 body, platí A, B ≤ 5.