Search
Marko Genyk-Berezovskyj
Jakub Sláma, Josef Krška, Šimon Mandlík, Martin Němec, Emmanuil Vaganov, Charlotte Panušková, Dominik Hoftych, Lev Kolomazov, Artem Gribanov, Igor Ekisev.
Seznámení, rozvičky po prázdninách: Rozcvičky .
Práce s online vyhodnocovacím serverem
Navštivte Sphere Online Judge a zaregistrujete se. Seznam počátečních trénovacích úloh je zde: List of basics problems. Z nich vybíráme:
Přednáška: Grafy a jejich reprezentace. Převod z jedné reprezentace do jiné, ověřování jednoduchých vlastností grafu (Max a min stupeň, test zda je graf úplný, kružnicí, cestou).
Poznatky:
Referenční texty: Grafy a stromy, Reprezentace grafu, Grafy
Úlohy : Kolo a Trojúhelník.
Přednáška: Kořenové stromy, průchody stromem, rekurzivní zpracování stromů.
Úloha : Binární strom
Přednáška: Fronta a zásobník a jejich využití při prohledávání grafu (tzv. BFS a DFS).
Referenční text: Průchod grafu
Úlohy : Průchod do šířky, navrhněte postup řešení pro CERC07K - Key Task nebo MAKEMAZE - VALIDATE THE MAZE (a zkuste odevzdat kód),
Přednáška: Přehled dalších grafových úloh (nejkratší cesty, souvislost grafu) a jejich složitost, resp. praktická upočítatelnost.
Referenční text: Těžké problémy
Půlmaraton:
Prohledávání
10608 - Friends
PT07Y - Is it a tree
PT07Z - Longest path in a tree
CAM5 - prayatna PR , ALLIZWEL - ALL IZZ WELL , 11624 - Fire! , 10004 - Bicoloring , 11331 - The Joys of Farming , 705 - Slash Maze , LABYR1 - Labyrinth ,,,GCPC11J - Time to live
Directed Acyclic Graph (DAG) a topologické uspořádání:
11686 - Pick up sticks
10051 - Tower of Cubes
10029 - Edit Step Ladders
Dijkstrův algoritmus jako aplikace prioritní fronty:
10048 - Audiophobia
10099 - The Tourist Guide
Backtrack:
861 - Little Bishops
11567 - Moliu Number Generator
Jakub Černý: Základní grafové algoritmy, KAM MFF, 2010, online publikace.
Steven S. Skiena, Miguel A. Revilla: Programming Challenges (záložní link)
'Programátorské kuchařky z MFF UK'' kuchařky.
C++ priority queues
Java PriorityQueue
Účast v ACM ICPC Maratonu: link
1. Napište přeložte a spusťte Hello world.
2. Spočtěte počet slov v textovém souboru, slova jsou oddělená mezerami, soubor jinak obsahuje jen malá písmena a, b, c. , z. Vypište slova v abecedním pořadí.
3. V dané posloupnosti čísel najděte taková, která jsou součtem všech jim předcházejících čísel v posloupnosti.
Příklad. Vstup 8 1 1 4 6 2 3 17 34 Výstup 1 6 17 34
4. Ve čtvercové 0/1 matici velikosti NxN určete, jestli jedničky tvoří vyplněný čtverec velikosti alespoň 2×2.
5. Ve čtvercové 0/1 matici určete počet všech úseček. Úsečka je souvislá vodorovná nebo svislá posloupnost jedniček s délkou alespoň 2, kterou nelze dále prodloužit. Úsečky se mohou různě dotýkat i protínat. Vstup je v souboru in.txt, první řádek obsahuje velikost matice N, na dalších N řádcích vstupu je N řádků matice, každý obsahuje N znaků 0/1 oddělených mezerami. Maximální velkost N je 1000. Na výstup (stačí na konzoli) vypište počet úseček.
Příklad Vstup 7 0 0 0 1 1 0 0 1 1 1 1 0 0 1 0 1 1 1 0 0 1 0 0 1 1 0 0 1 0 0 0 1 0 0 0 0 1 1 1 1 0 1 0 0 0 1 0 1 0 Výstup 9 0 0 1 1 0 0 1
Načtěte ze vstupu (konzole nebo soubor) matici sousednosti grafu reprezentaci grafu a vypište seznam hran grafu. První řádek vstupu obsahuje pouze hodnotu N - počet uzlů grafu, následuje N řádků s maticí sousedností, hodnoty na řádcích jsou odděleny mezerami. Uzly grafu číslujte od 0, každý uzel má číslo odpovídající jeho indexu v matici sousednosti.
Příklad Vstup 6 0 0 0 1 0 0 0 0 1 1 1 0 0 1 0 0 0 1 1 1 0 0 1 0 0 1 0 1 0 1 0 0 1 0 1 0 Výstup 0 3 1 2 1 3 1 4 2 5 3 4 4 5
Načtěte ze vstupu (konzole nebo soubor) seznam hran grafu a vypište jeho matici sousednosti a jeho spojovou reprezentaci. Uzly jsou číslovány od 0 do N-1, kde N je počet uzlů grafu. Na vstupu je nejprve řádek s hodnotami N a M oddělenými mezerou, N je počet uzlů a M je počet hran grafu. Poté následuje M řádků představujících jednotlivé hrany v libovolném pořadí. Na řádku jsou oddělená mezerou čísla koncových uzlů hrany. Matici sousednosti vypisujte bez uvádění počtu uzlů. Ve spojové reprezentaci uveďte na každém řádku jeden uzel - nejprve jeho číslo a poté za pomlčkou seznam čísel jeho sousedů v libovolném pořadí oddělených mezerou.
Příklad
Vstup 6 7 4 3 3 5 0 1 1 2 2 0 2 3 3 1 Výstup 0 1 1 0 0 0 1 0 1 1 0 0 1 1 0 1 0 0 0 1 1 0 1 1 0 0 0 1 0 0 0 0 0 1 0 0 5 - 3 4 - 3 3 - 5 4 2 1 2 - 3 1 0 1 - 3 2 0 0 - 2 1
Určete, jestli je zadaný graf kolo. Kolo je kružnice s jedním přidaným uzlem uvnitř, ze kterého vedou hrany (paprsky) do všech ostatních uzlů grafu. Viz příklady.
Graf na vstupu má nejvýše N = 20000 uzlů a je zadán seznamem hran. První řádek vstupu obsahuje číslo N, dále následuje 2N-2 řádků, každý představuje jednu hranu. Na řádku jsou uvedena čísla koncových uzlů hrany oddělená mezerou. Uzly jsou číslovány 1..N.
Na výstupu je jediný řádek s řetězcem ANO resp. NE, pokud zadaný graf je resp. není kolem.
Příklad 1. Vstup 6 1 2 2 3 3 4 4 5 5 6 6 1 6 2 6 3 6 4 1 5 Výstup ANO Příklad 2. Vstup 5 5 4 4 3 3 2 2 1 1 5 1 4 1 3 2 4 Výstup NE
Další vstupní testovací data pro N = 100, N = 1000, N = 10000, N = 20000. Kontrola výsledků zde.
Trojúhelník v grafu je každá trojice uzlů (x, y, z), která je navzájem propojená hranami (x, y), (y, z), (x, z). Určete, jestli daný graf obsahuje trojúhelník.
Graf na vstupu má nejvýše 10 uzlů a je zadán maticí sousedností. První řádek obsahuje jedno číslo N, dalších N řádků obsahuje matici sousednosti, hodnoty v matici jsou odděleny mezerou.
Na výstupu je jediný řádek s řetězcem ANO resp. NE, pokud zadaný graf obsahuje resp. neobsahuje trojúhelník.
Příklad 1. Vstup 4 0 1 0 0 1 0 1 1 0 1 0 1 0 1 1 0 Výstup ANO Příklad 2. Vstup 5 0 0 1 1 1 0 0 1 1 1 1 1 0 0 0 1 1 0 0 0 1 1 0 0 0 Výstup NE
V daném binárním stromu, jehož každý uzel má určitou hodnotu, zjistěte několik věcí:
Předpokládáme, že strom má N uzlů číslovaných od 0 do N-1. Strom je zadán výčtem uzlů a jejich následníků takto:
Na prvním řádku vstupu je hodnota N a číslo kořene oddělené mezerou. Každý z dalších N řádků představuje jeden uzel stromu ve formátu číslo uzlu, hodnota uzlu, číslo levého potomka, číslo pravého potomka. Hodnoty jsou odděleny mezerami, neexistující potomek je označen číslem -1.
Na výstupu jsou postupně na jednotlivých řádcích hledané hodnoty.
Příklad Vstup 11 3 0 20 -1 -1 1 10 0 2 2 30 -1 -1 3 5 1 9 4 40 -1 -1 5 80 4 7 6 50 -1 -1 7 90 6 8 8 60 -1 -1 9 99 5 10 10 70 -1 -1 Výstup 6 270 110 359 Příklad Vstup 10 0 0 30 1 2 1 20 3 4 2 90 7 9 3 40 -1 -1 4 30 8 -1 5 40 -1 -1 6 30 -1 -1 7 10 -1 -1 8 10 5 6 9 20 -1 -1 Výstup 5 140 70 140
Malý ukázkový rekurzivní kód v Javě:
package lps; import java.util.Scanner; public class BinTree { static int N; static int root; static int nil = -1; static int [] Val; static int [] L; static int [] R; public static void main(String[] args) { loadFromStd(); print(root); System.out.printf("sum values %d\n", sumvals(root)); System.out.printf("no of leaves %d\n", noOfLeaves(root)); printIdent(root, 0); } static void loadFromStd() { Scanner input = new Scanner( System.in ); N = input.nextInt(); Val = new int [N]; L = new int [N]; R = new int [N]; root = input.nextInt(); int curr; for(int i = 0; i < N; i++) { curr = input.nextInt(); Val[curr] = input.nextInt(); L[curr] = input.nextInt(); R[curr] = input.nextInt(); } } static int sumvals(int node) { if (node == nil) return 0; return Val[node] + sumvals(L[node]) + sumvals(R[node]); } static int noOfLeaves(int node) { if (L[node] == nil && R[node] == nil) return 1; return noOfLeaves(L[node]) + noOfLeaves(R[node]); } static void print(int node) { if (node == nil) return; System.out.printf("%d %d %d %d\n", node, Val[node], L[node], R[node]); print(L[node]); print(R[node]); } static void printIdent(int node, int depth) { if (node == nil) return; printIdent(R[node], depth+4); for(int i = 0; i < depth; i++) System.out.printf(" "); System.out.printf("[%d %d]\n", node, Val[node]); //printIdent(R[node], depth+4); printIdent(L[node], depth+4); } }
V grafech uvedených na této stránce určete vzdálenost z uzlu 0 do všech ostatních uzlů. Opakovaným voláním BFS určete vzdálenosti mezi každou dvojicí uzlů v těchto grafech.