Malý chlapec vyrábí korálky. Má mnoho číslovaných korálků. Každý korálek má jedinečné číslo – celé číslo v rozsahu od 1 do N. Všechny korálky rozloží na podlahu a korálky náhodným způsobem spojí dohromady, aby nevznikly uzavřené obrysy. Každý z korálků je spojen s jiným korálkem. Je nutné určit maximální počet kuliček zapojených do série, které jsou přítomny ve výsledném obrázku.
Vstupní data
Výstup
Výstup do souboru “beads.out” jedno číslo je požadovaný počet korálků.
5 2 1 23 2
Výstup
časový limit na zkoušku
limit paměti na test
128 megabajtů
Ve městě postaveném během středověku začala šířka ulic bránit provozu, který byl původně obousměrný na každé z ulic. Pro vyřešení tohoto problému bylo navrženo, aby provoz na každé ulici byl jednosměrný. Starosta tímto úkolem pověřil svého prvního zástupce. Po dlouhém přemýšlení oznámil, že na některých ulicích bude muset být provoz ponechán obousměrný, jinak by nebylo možné cestovat z jakéhokoli místa ve městě na jiné. Podle této mapy města musíte najít všechny takové ulice.
Vstupní data
Výstup
Na první řádek vytiskněte číslo B — počet ulic, na kterých není možné organizovat jednosměrný provoz. Na další řádek vytiskněte B celá čísla — čísla těchto ulic ve vzestupném pořadí. Ulice jsou číslovány od jedné v pořadí, v jakém jsou uvedeny ve vstupním souboru.
10 16 2 6 3 7 6 5 5 9 5 4 1 2 9 8 6 4 2 10 3 8 7 9 1 4 2 4 10 5 1 6 6
Výstup
časový limit na zkoušku
limit paměti na test
64 megabajtů
Artikulační body
Nový premiér se rozhodl cestovat napříč Ruskem z Moskvy do Vladivostoku po železnici a poté se vrátit zpět. Nařídil svým asistentům, aby vypracovali trasu, aby nemuseli dvakrát projíždět stejným městem. Pomocníci však hlásili, že to bylo pro ruské železnice nemožné. Určete, která města bude premiér nucen navštívit dvakrát.
Vstupní data
Výstup
Na první řádek vytiskněte číslo B — počet měst, která bude muset premiér navštívit dvakrát. Na následujících řádcích vytiskněte B celá čísla — čísla těchto měst ve vzestupném pořadí.
Známkovací systém
Skupina 0 Testy ze stavu. Skóre 0 bodů.
Skupina 1 Úplná omezení. Ohodnoceno 100 body. Každý test je hodnocen samostatně.
příklad
3 2 1 2 2 3 3 1
časový limit na zkoušku
limit paměti na test
64 megabajtů
K účastníci shromáždění byli požádáni o řešení K úkoly. Účastníci se rozhodli, že si problémy mezi sebou rozdělí, u každého vyřeší jeden problém a řešení si následně vymění (nebrali v úvahu, že je systém ejudge schopen tuto skutečnost sledovat J ). Je známa přibližná doba, za kterou může každý účastník výcvikového kempu vyřešit každý z navržených problémů.
Pomozte účastníkům soustředění rozdělit úkoly tak (jeden pro každého účastníka), aby celkový čas strávený jejich řešením byl minimální.
Vstupní soubor nejprve obsahuje číslo K (0 K < 101) dále K 2 nezáporná celá čísla nepřesahující 20000 popisující matici K x K, čas potřebný pro každého účastníka k vyřešení každého problému.
Výstup do souboru celkový minimální čas na řešení všech problémů za předpokladu, že každý účastník vyřeší právě jeden problém.
| input.txt | výstup.txt |
| 2 |
časový limit na zkoušku
limit paměti na test
64 megabajtů
Péťa potřebuje dopravit stádo krav přes bažinu. Ke křížení můžete použít desky, které spojují hummoky. Poté, co byl někdo na humnu, se potopí. Musíte přepravit maximální počet krav bažinou.
Vstupní data
Výstup
Vyveďte maximální počet krav, které lze přepravit
8 0 0 1 0 1 0 2 1 1 0 2 -1 2 1 3 0 2 -1 3 0 1 0 4 0 3 0 4 0 0 0 3 0 0 0 4 0
Výstup
Zdroje: [Týmové olympiády, VKOSHP, 2006, Problém H]
časový limit na zkoušku
limit paměti na test
256 megabajtů
Je upřesněn počet linek metra a pořadí přestupních stanic na každé lince (linka nemá více než jeden přestup na druhou, kromě kruhové, v jedné stanici může být přestup na více linek). Mimo stanice se linky nekříží. Je nutné zjistit, zda takové metro může existovat,
Zhenya obdržel dopis od Leshy se slovním popisem mapy metra v jeho městě. Metro obsahuje jednu okružní linku. Každá ze zbývajících linií se protíná s okružní linií nejvýše na dvou místech a na křižovatkách jsou organizovány přestupní stanice. Na jednom místě může okružní linku protínat více linek se společnou přestupní stanicí.
Kromě těchto přestupních stanic nemá každá z linek více než jednu přestupní stanici pro přestup na jiné linky než okružní. Na takové stanici lze zorganizovat i přestup na více linek najednou.
U každé přestupní stanice Lesha popsal, které linky se na ní protínají, a uvedl pořadí umístění přestupních stanic na okružní lince. Tvrdí, že všechny tratě jsou umístěny ve stejné hloubce a kromě přestupních uzlů nemají žádné jiné křižovatky. Aby Zhenya ověřil toto tvrzení, začal kreslit mapu metra na základě slovního popisu, ale neuspěl.
Pomozte Zhenyovi napsat program, který zkontroluje, zda skutečně může existovat schéma metra, které odpovídá danému popisu.
Obrázek ukazuje možné schéma metra odpovídající druhému příkladu.
Zadejte číslo do prvního řádku k – počet linek metra ve městě (1k10). Všechny řádky jsou číslovány od 0 do k — 1, vyzváněcí řádek má číslo 0. Druhý řádek obsahuje číslo n – počet předávacích stanic. Každý z následujících n čáry popisuje čáry, které se protínají v odpovídající předávací stanici, přičemž na prvním místě jsou popisy předávacích stanic umístěných na kruhové čáře v pořadí jejich umístění na ní. Popis každého uzlu začíná počtem čar, které se v něm protínají, následovanými čísly čar.
Vytiskněte slovo ANO, pokud vám popis umožňuje sestavit mapu metra, a jinak NE.
4 6 2 0 1202203201202203 XNUMX XNUMX
Výstup
Vstupní data
6 6 3 0 1 4 2 0 1 3 0 2 3 3 0 2 3 3 1 3 5 2 2 4
Výstup
Zdroje: [Týmové olympiády, VKOSHP, 2005, Problém A]
časový limit na zkoušku
limit paměti na test
64 megabajtů
Je dán nevážený graf, jehož vrcholy jsou obarveny jednou ze tří barev. Je nutné přebarvit vrcholy grafu tak, aby neexistovaly dva sousední vrcholy stejné barvy a každý vrchol změnil barvu.
Péťa kreslil na papír n kruhy a propojili několik párů kruhů čarami. Poté vybarvil každý kruh jednou ze tří barev – červenou, modrou nebo zelenou.
Teď chce Péťa změnit jejich zbarvení. Chce totiž přebarvit každý kruh jinou barvou, aby žádné dva kruhy stejné barvy nebyly spojeny čárou. Zároveň chce mít jistotu, že každý kruh přemaluje a není dovoleno přemalovat kruh stejnou barvou, ve které byl původně namalován.
Pomozte Péťovi rozhodnout, jakými barvami by měly být hrnky přelakovány, aby byla splněna zadaná podmínka.
První řádek obsahuje dvě celá čísla n и m – počet kruhů a počet čar, které Petya nakreslil (1n1 000, 0m20).
Další řádek obsahuje n postavy ze sady – iTh z těchto symbolů znamená barvu, ve které je namalován ikruh („R“ – červená, „G“ – zelená, „B“ – modrá).
Dále dovnitř m každý řádek obsahuje dvě celá čísla – dvojice kružnic spojených segmenty.
Vytiskněte jeden řádek sestávající z n symboly ze sady – barvy kruhů po přemalování. Pokud existuje několik řešení, vytiskněte libovolné.
Pokud neexistuje žádné řešení, vytiskněte slovo „Nemožné“.
4 5 RRRG 1 3 1 4 3 4 2 4 2 3
SGBR
4 5 RGRR 1 3 1 4 3 4 2 4 2 3
Nemožný
Zdroje: [Týmové olympiády, VKOSHP, 2005, Problém D]
časový limit na zkoušku
limit paměti na test
64 megabajtů
Jsou uvedeny souřadnice bodů na rovině a strom. Body na rovině je nutné sladit s vrcholy stromu tak, aby se při umístění stromu v rovině hrany neprotínaly.
V Flatlandu n města na různých místech letadla. Je známo, že žádná tři města neleží na stejné přímce.
Vláda se rozhodla vybudovat v zemi síť superdálnic. Dálniční síť by měla být taková, aby bylo možné po vybudovaných dálnicích cestovat z jakéhokoli města do kteréhokoli jiného. A aby se ušetřilo, bylo rozhodnuto, že cesta spojující jakákoli dvě města by měla být jediná. Každá dálnice je úsek spojující určitou dvojici měst.
Závod naplňující toto nařízení vlády připravil projekt dálniční sítě. Projekt je popis n — 1 dálnice. Každá dálnice je definována městy, která spojuje. Pro účely utajení byly v projektu místo názvů měst použity kódy – čísla od 1 do n.
Když však došlo k realizaci projektu, ukázalo se, že dokument, ve kterém byla uvedena shoda čísel s městy, byl ztracen. Protože se projekt kryje s 500. výročím kulturního hlavního města Flatlandu, nebylo možné projekt zcela předělat. Proto bylo rozhodnuto zavést nějakou novou korespondenci mezi čísly a městy.
Při pokusu o to vývojáři projektu narazili na následující problém. V souladu s technickými stavebními normami je nepřijatelné, aby se dálnice křížily mimo města. Proto není přijatelné žádné srovnání čísel s městy. Po pár bezesných nocích se hlavní inženýr elektrárny rozhodl svěřit záchranu projektu vám.
Vaším úkolem je porovnat čísla od 1 do n města, aby se po realizaci projektu dálnice nekřížily mimo města, která spojují.
První řádek obsahuje celé číslo n – počet měst v Flatland (2n1500).
Následuje následující n popisy měst. Popis každého města se skládá ze dvou řádků. První řádek obsahuje název města – řetězec sestávající ze znaků s ASCII kódy od 33 do 127. Názvy různých měst nejsou stejné. Délka názvu města nepřesahuje 60 znaků. Druhý řádek popisu města obsahuje dvě celá čísla x и y – souřadnice města. Souřadnice nepřesahují 10 4 v absolutní hodnotě.
Následován n — 1 řádků, které popisují projekt výstavby dálniční sítě v současném stavu. Každý řádek obsahuje dvě celá čísla – počty měst spojených dálnicemi v projektu. Žádná dálnice v projektu nespojuje město samo se sebou a žádná dvě města nejsou spojena více než jednou dálnicí.
Výstup n linky, i-první z těchto řádků by měl obsahovat název města, který by měl odpovídat číslu i v projektu. Pokud existuje několik řešení, vytiskněte libovolné.
Pokud neexistuje žádné řešení, vytiskněte řádek „Žádné řešení“.
7 Moskva 2 2 Petrohrad 0 4 Kirov 6 3 Saratov 5 0 Rybinsk 1 1 Petrozavodsk 2 6 Barnaul 10 -1 1 2 2 4 3 5 4 3 4 7 3 6
Petrohrad Rybinsk Kirov Saratov Moskva Petrozavodsk Barnaul
Zdroje: [Týmové olympiády, VKOSHP, 2004, Problém A]
Jsou dány dva protínající se kruhy. Je nutné najít nejkratší cestu z bodu do bodu po kruzích.
Péťa jezdí do školy rád na kole. Jízda na kole po chodnících je ale zakázána a jízda po silnici je nebezpečná. Péťa proto jezdí jen po speciálních cyklostezkách. Naštěstí se Petyin dům i Petyina škola nacházejí v těsné blízkosti takových cest.
Ve městě, kde Péťa žije, jsou rovnou dvě cyklostezky. Každá dráha má tvar kruhu. V místech jejich průsečíku se můžete pohybovat z jedné cesty na druhou.
Péťa ví, kde vjíždí na příjezdovou cestu a kde musí vyjít, aby se dostal do školy. Péťu zajímala otázka: jakou minimální vzdálenost by měl ujet po cestách, aby se dostal z domova do školy.
Budeme předpokládat, že ve městě byl zaveden pravoúhlý kartézský souřadnicový systém.
První dva řádky vstupu popisují cyklostezky. Každý z nich obsahuje tři celá čísla – souřadnice středu kružnice, kterou příslušná stopa představuje, a její poloměr. Souřadnice a poloměr nepřesahují v absolutní hodnotě 200, poloměr je kladné číslo. Je zaručeno, že se stopy neshodují.
Další dva řádky obsahují každý dvě reálná čísla – souřadnice bodu, kde Péťa vstoupí na dráhu, a bodu, ve kterém Péťa dráhu opustí. Je zaručeno, že každý z bodů leží na jedné z drah s vysokou přesností (vzdálenost bodu ke středu jedné z kružnic se od jejího poloměru neliší o více než 10 -8 ). Body mohou ležet na stejné dráze nebo na různých.
Vytiskněte minimální vzdálenost, kterou musí Péťa urazit po cyklostezkách, aby se dostal z domova do školy. Odpověď by se od správné odpovědi neměla lišit o více než 10 -4.
Není-li možné se dostat z domova do školy po cyklostezkách, vytiskněte číslo -1.
