PilsProg 2023

Výsledky Lite

#	Jméno	Příjmení	Splněných úloh	Čas
1	Ondřej	Bulka	9	5,401
2	Mattias	Kundert	9	67,512
3	David	Macner	9	96,835
4	Jan	Brichcín	9	100,423
5	Marek	Hroch	9	221,891
6	Matyáš	Vítek	9	226,589
7	Ondřej	Bartoš	9	361,826
8	Zuzana	Aubrechtová	9	456,662
9	Petr	Zaoral	8	172,960
10	Štěpán	Mikéska	1	121,833

Cena udělená za 1. místo v PilsProg Lite: Externí 2TB 2.5" HDD

Výsledky kvalifikace

#	Jméno	Příjmení	Splněných úloh	Čas	Finále
1	Ondřej	Bartoš	5	102,257	Postupuje do finále
2	Jáchym	Kouba	5	114,524	Postupuje do finále
3	Marek	Hroch	4	58,386	Postupuje do finále
4	Tomáš	Zlámal	4	63,903	Postupuje do finále
5	Matyáš	Vítek	4	105,747	Postupuje do finále
6	Daniel	Altmann	4	2 118,466	Postupuje do finále
7	Václav	Zach	4	2 130,247	Postupuje do finále
8	Vitalii	Medvid	4	2 699,916	Postupuje do finále
9	Lucian	Poljak	4	3 662,378	Postupuje do finále
10	Martin	Benda	3	38,310	Postupuje do finále
11	Zuzana	Aubrechtová	3	249,699	Postupuje do finále
12	Jan	Brichcín	3	266,053	Postupuje do finále
13	Štěpán	Kuch	3	325,239	Postupuje do finále
14	Petr	Zaoral	3	511,280	Postupuje do finále
15	Ondřej	Bulka	3	1 062,523	Postupuje do finále
16	Lenka	Poljaková	3	1 197,436	Postupuje do finále
17	Paolo	Zisa	3	1 963,337	-
18	Mattias	Kundert	3	2 031,756	-
19	Jakub	Nekvinda	3	2 351,307	-
20	Lukáš	Patejdl	3	2 508,283	-
21	Martin	Štrobl	2	9,596	-
22	Jakub	Svítek	2	116,971	-
23	Jakub	Pešek	2	1 448,556	-
24	Adam	Červenka	2	2 409,874	-
25	Viktor	Suchý	1	2,073	-
26	David	Macner	1	4,116	-
27	Michal	Spišak	1	26,487	-
28	Alexandr	Vituško	1	57,999	-
29	Tadeáš	Kulhánek	1	606,507	-

Výsledky finále

#	Jméno	Příjmení	Splněných úloh	Čas
1	Lucian	Poljak	2	3,428
2	Lenka	Poljaková	2	4,097
3	Jáchym	Kouba	1	0,561
4	Petr	Zaoral	1	0,580
5	Daniel	Altmann	1	0,895
6	Ondřej	Bulka	1	1,135
7	Jan	Brichcín	1	1,694
8	Vitalii	Medvid	1	2,547
9	Martin	Benda	1	2,899
10	Ondřej	Bartoš	1	3,853
11	Tomáš	Zlámal	1	4,291
12	Václav	Zach	1	4,294
13	Marek	Hroch	0	0,000
14	Štěpán	Kuch	0	0,000
15	Zuzana	Aubrechtová	0	0,000
16	Matyáš	Vítek	0	0,000

Vysvětlivky: Čas vyřešení je počítán v hodinách od zveřejnění úlohy.

Poznámka: Finalisté Zuzana Aubrechtová, Štěpán Kuch a Matyáš Vítek se finálové soutěže nezúčastnili.

Ilustrační úlohy

Název	Číslo	Úspěšných řešitelů
AxB	1701	15
AplusB	1702	10
Největší ze tří celých čísel	1703	8
Pascalův trojúhelník	1704	5

Lite1 úlohy

Název	Číslo	Úspěšných řešitelů
Palindrom	2311	9
Typ trojúhelníku	2312	9
Vážený studijní průměr	2313	9

Lite2 úlohy

Název	Číslo	Úspěšných řešitelů
Anagram	2314	10
Přestupný rok	2315	9
Řazení studentů	2316	8

Lite3 úlohy

Název	Číslo	Úspěšných řešitelů
Hledání obrázku	2317	9
Obsah trojúhelníku	2318	9
Teplotní odchylky	2319	9

Kvalifikační úlohy

Název	Číslo	Úspěšných řešitelů
Gurmánský tučňák	2321	3
Hledání podmapy	2322	21
Hlemýžď na víně	2323	9
Moderní trendy	2324	0
Sezame otevři se	2325	22
Turnaj	2326	29

Finálové úlohy

Název	Číslo	Úspěšných řešitelů
Doučování	2331	2
Grandiózní výmls	2332	1
Netwars	2333	11
Poslední jezdec apokalypsy	2334	0
Slevička	2335	0

A jaké bylo finále?

Harmonogram PilsProg 2023

• Zahájení registrace: 31.10.2022
• Zahájení Lite kola: 8.11.2022 14:00
  
  • Zahájení Lite1 kola: 8.11.2022 14:00
  • Ukončení Lite1 kola: 14.11.2022 14:00
  • Zahájení Lite2 kola: 22.11.2022 14:00
  • Ukončení Lite2 kola: 28.11.2022 14:00
  • Zahájení Lite3 kola: 6.12.2022 14:00
  • Ukončení Lite3 kola: 12.12.2022 14:00
• Ukončení Lite kola: 12.12.2022 14:00
• Zahájení kvalifikačního kola: 12.1.2023 14:00
• Ukončení kvalifikačního kola: 8.3.2023 14:00
• Finálové kolo: 25.3.2023 09:00 - 13:00, KIV - UC311

Lite úlohy - řešení

Nejprve je stručně popsán způsob, jakým je možno úlohu řešit. Jak úlohy řešili soutěžící, je ukázáno na vybraných příkladech zdrojových kódů odevzdaných soutěžních úloh.

Palindrom

1. Načíst počet slov.
2. Znaky každého slova si načíst do řetězce.
3. Procházet v cyklu první půlku znaků řetězce a porovnávat znaky s odpovídajícímí znaky v druhé polovině (první s posledním, druhý s předposledním, atd.). V případě lichého počtu znaků prostřední znak s ničím neporovnávat.
4. Pokud jsou všechny odpovídající si znaky stejné, jedná se o palindrom, vypsat „ano“, jinak vypsat „ne“.

Příklad zdrojového kódu:

#include <iostream> #include <string> using namespace std; void solve() { string str; cin >> str; int n = str.size(); for (int j = 0; j < n / 2; j++) { if (str[j] != str[n - j - 1]) { cout << "ne\n"; return; } } cout << "ano\n"; } int main() { int s; cin >> s; for (int i = 0; i < s; i++) { solve(); } }

Typ trojúhelníku

1. Načíst počet testovacích případů (trojúhelníků).
2. Pro každý testovací případ si načíst všechny tři strany.
3. Zjistit, zda lze trojúhleník sestrojit porovnáním součtu dvou stran a třetí strany. Součet musí být větší než strana pro všechny kombinace. Pokud trojúhelník nelze sestrojit, vypsat „Nelze sestrojit.“.
4. Pokud trojúhelník lze sestrojit, porovnat všechny tři strany.
5. Pokud jsou všechny strany stejné, vypsat „Rovnostranny trojuhelnik.“
6. Pokud jsou dvě strany stejné, vypsat „Rovnoramenny trojuhelnik.“
7. Jinak vypsat „Obecny trojuhelnik.“

Příklad zdrojového kódu:

import java.lang.reflect.Array; import java.util.*; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int t = Integer.parseInt(in.nextLine()); String[][] triangles = new String[t][3]; for(int i = 0; i < t; i++) { triangles[i] = in.nextLine().split("\\s+"); } for (int i = 0; i < triangles.length; i++) { int a = Integer.parseInt(triangles[i][0]); int b = Integer.parseInt(triangles[i][1]); int c = Integer.parseInt(triangles[i][2]); if((a + b > c) && (b + c > a) && (c + a > b)) { if(a == b && b == c){ System.out.println("Rovnostranny trojuhelnik."); } else{ if(isDuplicate(new int[]{a,b,c})){ System.out.println("Rovnoramenny trojuhelnik."); } else{ System.out.println("Obecny trojuhelnik."); } } } else{ System.out.println("Nelze sestrojit."); } } } public static <T> boolean isDuplicate(final int[] values){ return Arrays.stream(values).distinct().count() != values.length; } }

Vážený studijní průměr

1. Načítat v cyklu počty kreditů a odpovídající známky, jakmile je počet kreditů roven 0, ukončit program a vypsat výsledek.
2. V každé obrátce cyklu přičíst počet kreditů do součtu kreditů a součin počtu kreditů a známky přičíst do součtu součinů.
3. Po skončení načítání vydělit součet součinů součtem kreditů.
4. Výsledek vypsat na 2 desetinná místa.

Příklad zdrojového kódu:

program U3VazenyPrumer; uses math, sysutils; var sumK, sumKZ: Word; k, z: Byte; sum: Real; begin DefaultFormatSettings.DecimalSeparator:='.'; sumK:=0; sumKZ:=0; repeat begin Read(k); if k=0 then Break; ReadLn(z); //sum:=SimpleRoundTo(k/z, -2); //WriteLn(floatToStrF(sum, ffFixed, 0, 2)); sumK:=sumK+k; sumKZ:=sumKZ+k*z; end until False; ReadLn; sum:=SimpleRoundTo(sumKZ/sumK, -2); //WriteLn(sumK, ' ', sumKZ); WriteLn(floatToStrF(sum, ffFixed, 0, 2)); ReadLn; end.

Anagram

1. Načíst počet testovacích případů (dvojic slov).
2. Pro každý testovací případ si načíst obě slova jako řetězce a převést je na velká písmena.
3. Pro první slovo si určit počty jednotlivých písmen (A až Z) obsažených ve slově (lze uložit např. do pole o 26 (počet písmen anglické abecedy) prvcích). Totéž udělat pro druhé slovo.
4. Porovnat počty písmen pro obě slova (tedy např. porovnat obě vytvořená pole prvek po prvku).
5. Pokud jsou počty stejné, vypsat „ano“, jinak vypsat „ne“.

Příklad zdrojového kódu:

#include <bits/stdc++.h> using namespace std; int main() { int size; cin >> size; for (int i = 0; i < size; i++) { string first, second; cin >> first >> second; std::transform(first.begin(), first.end(), first.begin(), ::tolower); std::transform(second.begin(), second.end(), second.begin(), ::tolower); if (first == second) { cout << "ne\n"; continue; } map<char, int> firstMap; map<char, int> secondMap; for (int i = 0; i < first.size(); i++) { firstMap[first[i]]++; secondMap[second[i]]++; } bool cond = true; for(auto kvp : firstMap) { if (kvp.second != secondMap[kvp.first]) { cond = false; break; } } if (cond) cout << "ano\n"; else cout << "ne\n"; } return 0; }

Přestupný rok

1. Načíst počet roků.
2. Každý rok si načíst jako číslo.
3. U každého roku otestovat pomocí složené podmínky, zda je dělitelný 4 a zároveň nedělitelný 100 nebo dělitelný 400.
4. Pokud složená podmínka platí, vypsat „prestupny“, jinak vypsat „neprestupny“

Příklad zdrojového kódu:

import java.util.Scanner; public class Lite_2_2 { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); for (int i = 0; i < n; i++) { int year = scanner.nextInt(); if (year % 4 == 0 && year % 100 != 0 || year % 400 == 0) { System.out.println("prestupny"); } else { System.out.println("neprestupny"); } } } }

Řazení studentů

1. Načíst počet studentů a vytvořit si pole objektů/struktur/záznamů o načtené velikosti. Objekt/stuktura/záznam bude obsahovat jméno a příjmení studenta.
2. Pro každého studenta načíst jméno a příjmení a uložit ho jako prvek pole.
3. Pole seřadit vlastním nebo knihovním algoritmem řazení primárně podle příjmení, sekundárně podle jména (složenou podmínku lze zaspat přímo do řadícího algoritmu, nebo lépe do metody/funkce umožňující porovnání dvou studentů podle příjmení a podle jména).
4. Vypsat (nyní seřazené) pole studentů, každého studenta na samostatný řádek, nejdřív příjmení a následně jméno.

Příklad zdrojového kódu:

import java.io.*; import java.util.*; import java.util.stream.*; public class RazeniStudentu { public static void main(String[] args) throws IOException { BufferedReader reader = new BufferedReader(new InputStreamReader(System.in)); int count = Integer.parseInt(reader.readLine()); List<String> list = new ArrayList<>(); while (count > 0) { String s = reader.readLine(); String first = s.split(" ")[0]; String last = s.split(" ")[1]; String toReverse = last + " " + first; list.add(toReverse); count--; } List<String> sorted = list.stream().sorted().collect(Collectors.toList()); for (String s : sorted) { System.out.println(s); } } }

Hledání obrázku

1. Načíst šířku a výšku obrázku.
2. Načítat jednotlivé řádky obrázku jako řetězce a uložit si je např. do pole řetězců.
3. Načíst si podobrázek jako řetězec.
4. Projít načtené pole řetězců a v každé řádce zkusit najít podobrázek pomocí hledání podřetězce v řetězci (např. knihovní funkcí).
5. Pokud je podřetězec nalezen, vypsat index řádky a nalezenou pozici v řetězci v požadovaném formátu.
6. Pokud není podřetězec nalezen ani v jedné řádce, vypsat prázdné hranaté závorky.

Příklad zdrojového kódu:

program U1HledaniObrazku; uses sysutils; var v, i: Byte; search, output: String[50]; picture: array of String[50]; begin Read(v); ReadLn(v); SetLength(picture, v); for i:=0 to v-1 do begin ReadLn(picture[i]); end; ReadLn(search); output:='[]'; for i:=0 to v-1 do begin if Pos(search, picture[i])<>0 then begin output:='['+IntToStr(Pos(search, picture[i])-1)+'; '+IntToStr(i)+']'; Break; end; end; WriteLn(output); ReadLn; end.

Obsah trojúhelníku

1. Načíst počet testovacích případů (trojúhelníků).
2. Pro každý testovací případ si načíst všechny tři strany a, b, c.
3. Vypočítat si obsah trojúhleníku pomocí Heronova vzorce S = sqrt(s * (s - a) * (s - b) * (s - c)), kde s = (a + b + c) / 2.
4. Obsah vypsat na 2 desetinná místa.

Příklad zdrojového kódu:

import java.util.Scanner; /** * * @author zuza */ public class ObsahTrojuhelniku { public static void main(String[] args) { Scanner vstup = new Scanner(System.in); int pocet = vstup.nextInt(); for (int i = 0; i < pocet; i++) { double a = vstup.nextFloat(); double b = vstup.nextFloat(); double c = vstup.nextFloat(); double s = (a + b + c) / 2; double mezikrok = s * (s - a) * (s - b) * (s - c); double S = Math.sqrt(mezikrok); System.out.printf("%.2f\n", S); } } }

Teplotní odchylky

1. Načíst si počet teplot a vytvořit si pole o načtené velikosti.
2. Načítat jednotlivé teploty jako reálná čísla a ukládat je do pole. Zároveň si počítat součet načtených teplot.
3. Spočítat průměrnou teplotu jako podíl součtu a počtu teplot. Průměr vypsat na 1 desetinné místo v požadovaném formátu.
4. Projít pole teplot a pro každou teplotu vypsat na samostatnou řádku rozdíl teploty a průměru teplot na 1 desetinné místo.

Příklad zdrojového kódu:

#include <iostream> #include <vector> using namespace std; int main() { int d; cin >> d; vector<double> arr(d); double arrSum = 0; for (int i = 0; i < d; i++) { cin >> arr[i]; arrSum += arr[i]; } cout.precision(1); double prumer = arrSum / d; cout << "Prumer: " << fixed << prumer << '\n'; for (int i = 0; i < arr.size(); i++) { cout << fixed << arr[i] - prumer << '\n'; } }

Kvalifikační úlohy - řešení

Nejprve je stručně popsán způsob, jakým je možno úlohu řešit. Jak úlohy řešili soutěžící, je ukázáno na vybraných příkladech zdrojových kódů odevzdaných soutěžních úloh.

Gurmánský tučňák

1. Načíst rozměr výškové mapy a následně jednotlivé výšky např. do dvourozměrného pole čísel. Načíst si pozici tučňáka a pozice jednotlivých ryb.
2. Vytvořit si vzdálenostní mapu (tj. určit vzdálenosti) od tučňáka ke každé rybě a od každé ryby ke každé jiné rybě pomocí prohledávání do šířky (BFS). Při prohledávání zohledňovat, že tučňák má při přechodu na sousední políčko výškové omezení.
3. Vygenerovat všechny permutace ryb. Každá permutace udává, v jakém pořadí se tučňák pokusí sesbírat jednotlivé ryby.
4. Pro každou permutaci spočítat pomocí dříve vytvořené vzdálenostní mapy, kolik kroků tučňákovi zabere sesbírat ryby v tomto pořadí. Postupně se tedy sčítají vzdálenosti dokud nejsou dosaženy všechny ryby, nebo se narazí na nedosažitelnou rybu.
5. Vybrat permutaci s maximálním počtem dosažitelných ryb. Pokud je více permutací se stejným maximálním dosažitelným počtem ryb, vybrat tu s nejnižším počtem kroků.
6. Vypsat počet kroků vybrané permutace.

Příklad zdrojového kódu:

#include<fstream> #include<vector> #include<algorithm> #include<queue> #include<set> #include<string> #include<iostream> using namespace std; vector<vector<int>> v, w; vector<pair<int, int>> vysledek; void permutace(int n, vector<vector<int>>& vzd) { vector<int> perm; for (int i = 1; i <= n; i++) { perm.push_back(i); } vector<int> perm2 = perm; while (true) { bool b = false; int count = 0; int j = 0; int r = 0; //vyzkouset while (j < n && vzd[0][perm[j]] == -1) j++; if (j < n) { count += vzd[0][perm[j]]; r++; } for (int i = j; i < n; i++) { j = i+1; while (j<n && vzd[perm[i]][perm[j]] == -1) j++; if (j == n) break; count += vzd[perm[i]][perm[j]]; i = j - 1; r++; } /*for (int i = 0; i < n; i++) { cout << perm[i] << " "; } cout << endl << r << " " << count << endl;*/ vysledek.push_back({ r, count }); next_permutation(perm.begin(), perm.end()); if (perm == perm2) break; } }; int main() { string pp; getline(cin, pp); string ss; int p = stoi(pp); v.resize(p); w.resize(p); set<pair<int, int>> coordinates; for (int i = 0; i < p; i++) { getline(cin, ss); for (int j = 0; j < p; j++) { int x = ss[j] - '0'; v[i].push_back(x); } } int r, s; cin >> r >> s; --r; --s; int R; cin >> R; vector<pair<int, int>> coord; for (int i = 0; i < R; i++) { int x, y; cin >> x >> y; coordinates.insert({ --x, --y }); coord.push_back({ x, y }); } vector<vector<int>> vzd(R + 1, vector<int>(R + 1, -1)); //bfs for (int i = 0; i < R + 1; i++) { int count = 0; queue<pair<pair<int, int>, int>> q, q2; vector<vector<bool>> seen(p, vector<bool>(p)); if (i == 0) q.push({ { r, s }, 0 }); else q.push({ {coord[i - 1].first, coord[i - 1].second}, 0 }); while (!q.empty()) { pair<int, int> act = q.front().first; int x = q.front().second; q.pop(); if (seen[act.first][act.second]) continue; seen[act.first][act.second] = true; if (coordinates.find({ act.first, act.second }) != coordinates.end()) { for (int j = 0; j < R; j++) { if (coord[j].first == act.first && coord[j].second == act.second) { vzd[i][j + 1] = x; } } } if (act.first > 0) { int diff = v[act.first][act.second] - v[act.first - 1][act.second]; if (diff >=-1 && diff <=2) q.push({ {act.first - 1, act.second }, x + 1 }); } if (act.first < p-1) { int diff = v[act.first][act.second] - v[act.first + 1][act.second]; if (diff >= -1 && diff <= 2) q.push({ {act.first + 1, act.second }, x + 1 }); } if (act.second < p - 1) { int diff = v[act.first][act.second] - v[act.first][act.second+1]; if (diff >= -1 && diff <= 2) q.push({ {act.first, act.second +1}, x + 1 }); } if (act.second > 0) { int diff = v[act.first][act.second] - v[act.first][act.second-1]; if (diff >= -1 && diff <= 2) q.push({ {act.first, act.second-1 }, x + 1 }); } } } /*for (int i = 0; i < R + 1; i++) { for (int j = 0; j < R + 1; j++) { cout << vzd[i][j] << " "; } cout << endl; }*/ permutace(R, vzd); sort(vysledek.begin(), vysledek.end(), greater<pair<int, int>>()); int V = 1000000; for (int i = 0; i < vysledek.size(); i++) { if (vysledek[i].first==vysledek[0].first) V = min(V, vysledek[i].second); } cout << V << endl; }

Hledání podmapy

1. Načíst si ze vstupu výšku a šířku a následně jednotlivé znaky mapy do dvourozměrného pole znaků, podobně načíst i hledanou podmapu. Při načítání znaků do polí nahradit středník (skoro vodní plocha) tečkou (vodní plocha) a zavináč (skoro pevnina) mřížkou (pevnina).
2. Procházet pole s mapou postupně od začátku a porovnávat všechny znaky podmapy s odpovídajícími znaky mapy.
3. Pokud jsou všechny znaky mapy a podmapy na odpovídajících pozicích stejné, podmapa byla nalezena.
4. Pokud mapa byla nalezena, předčasně ukončit procházení mapy a vypsat číslo sloupce a řádky mapy odpovídající počátku podmapy v požadovaném formátu. Pokud podmapa nalezena nebyla, vypsat „Nenalezeno.“.

Příklad zdrojového kódu:

program U2322HledaniPodmapy; type tCoord = record x: Integer; y: Byte; end; var wm, hm, wpm, hpm, i, y: Byte; map, pmap: Array of String; coord: tCoord; c: Boolean; begin Read(wm); ReadLn(hm); SetLength(map, hm); for i:=0 to hm-1 do Readln(map[i]); Read(wpm); ReadLn(hpm); SetLength(pmap, hpm); for i:=0 to hpm-1 do Readln(pmap[i]); //WriteLn(wm,hm,wpm,hpm); for y:=0 to hm-1 do begin for i:=1 to wm do begin case map[y][i] of ';': map[y][i]:='.'; '@': map[y][i]:='#'; end; end; end; for y:=0 to hpm-1 do begin for i:=1 to wpm do begin case pmap[y][i] of ';': pmap[y][i]:='.'; '@': pmap[y][i]:='#'; end; end; end; repeat begin c:=True; for i:=0 to hm-1 do begin coord.x:=Pos(pmap[0], map[i])-1; if coord.x<>-1 then Break; end; if coord.x=-1 then begin WriteLn('Nenalezeno.'); Break; end; coord.y:=i; //WriteLn('[', coord.x, '; ', coord.y, ']'); for y:=1 to hpm-1 do begin for i:=coord.x+1 to coord.x+wpm do begin if pmap[y][i-coord.x]<>map[coord.y+y][i] then begin //WriteLn('Error', pmap[y][i-coord.x], map[y][i]); map[coord.y][coord.x+1]:='-'; c:=False; Break; end; end; if c=False then Break; end; end until c=True; if coord.x<>-1 then WriteLn('[', coord.x, '; ', coord.y, ']'); ReadLn; end.

Hlemýžď na víně

1. Načíst si ze vstupu počty horizontálních a vertikálních uliček (tj. úseček) a následně horizontální a vertikální úsečky.
2. Najít průsečíky úseček s využitím zametací přímky rovnoběžné s osou y, která bude zametat horizontální úsečky.
3. Zametání relizovat jako zpracování seřazeného seznamu událostí. Z každé horizontální úsečky vytvořit dvě události - jednu pro začátek úsečky a druhou pro konec. Každá horizontální úsečka protínající zametací přímku bude mít na přímce započtenu jedničku, neprotínající nulu. Z konce každé vertikální úsečky vytvořit událost typu dotaz na počet průsečíků této úsečky s horizontální úsečkou.
4. Stav zametací přímky realizovat jako jednorozměrné pole pro všechny hodnoty y horizontálních úseček seřazených vzestupně a koncových bodů vertikálních úseček, na které lze při zametání ve směru osy x narazit. Nad tímto polem vybudovat hierarchii počtů horizontálních úseček a jejich součtů.
5. Všechny události seřadit primárně podle souřadnice x, sekundárně podle typu události (1. začátek horizontálního segmentu, 2. dotaz na počet průsečíků vertikálního segmentu, 3. konec horizontálního segmentu). Pro každý začátek horizontální úsečky na zametací přímku přičíst jedničku a upravit hierarchii. Pro každý konec horizontální úsečky odečíst jedničku a upravit hierarchii. Pro dotaz na počet průsečíků vertikální úsečky spočítat průsečíky a započíst do globálního počtu (na začátku 0).
6. Po zpracování všech událostí vypsat globální počet průsečíků.

Příklad zdrojového kódu:

#include <iostream> #include <vector> using namespace std; struct Line { int x, y, d; }; int main() { char temp, temp2; int h, v; cin >> temp >> h >> temp2 >> v; vector<Line> horizontal; horizontal.reserve(h); for (int i = 0; i < h; i++) { int x, y, d; cin >> x >> y >> d; d += x; horizontal.push_back({ min(x, d), y, max(x, d)}); } int count = 0; for (int i = 0; i < v; i++) { int x, y, d; cin >> x >> y >> d; d += y; if (y < d) { for (Line h : horizontal) { if (h.x <= x && x <= h.d && y <= h.y && h.y <= d) count++; } } else { for (Line h : horizontal) { if (h.x <= x && x <= h.d && y >= h.y && h.y >= d) count++; } } } cout << count << '\n'; }

Moderní trendy

1. Načíst ze vstupu počet ryb. Pro každou rybu si načíst číslo ryby a počet rovnic. Pro každou rovnici načíst typ hranice ryby (horní či dolní), interval a koeficienty rovnice.
2. Pro každou rybu si spočítat její obsah, pro výpočet použít určitý integrál. Je třeba počítat každou rovnici zvlášť a zohlednit, zda se jedná o horní nebo dolní hranici, ryba nemusí ležet na ose x. Dále je potřeba použít racionální čísla, aby nedocházeko k zaokouhlovacím chybám, je např. možno vytvořit si vlastní zlomkový počet.
3. Všechny ryby seřadit libovolným řadícím algoritmem vzestupně dle vypočtené plochy.
4. Vypsat seřazená čísla ryb.

Příklad zdrojového kódu:

Tuto úlohu žádný soutěžící nevyřešil.

Sezame otevři se

1. Načíst si ze vstupu počet kódů. Pro každý kód si načíst nejvyšší přípustnou cifru jako znak a jednotlivé sčítance např. jako řetězce.
2. Jednotlivé znaky (tj. číslice) sčítanců si uložit např. do dvourozměrného pole čísel (tj. znak převést na odpovídající číselnou hodnotu).
3. Určit si základ soustavy na základě nejvyšší přípustné cifry (stačí k hodnotě cifry přičíst 1).
4. Použít algoritmus sčítání více čísel na papíře pod sebou pro sčítance uložené v dvourozměrném poli, přenos doleva určit pomocí základu soustavy. Výsledek ukládat do jednorozměrného pole čísel.
5. Jednotlivé hodnoty výsledku převést na číslice v příslušné soustavě a vypsat je.

Příklad zdrojového kódu:

package Year_2023; import java.util.Arrays; import java.util.Scanner; public class Qualification_5 { public static void main(String[] args) { final Scanner scanner = new Scanner(System.in); final int sumsCount = scanner.nextInt(); for (int i = 0; i < sumsCount; i++) { final int max = Integer.parseInt(scanner.next(), 36) + 1; scanner.nextLine(); int sum = 0; for (String s : scanner.nextLine().split(" ")) { sum += Integer.parseInt(s, max); } System.out.println(Integer.toString(sum, max).toUpperCase()); } } }

Turnaj

1. Načíst si ze vstupu počet soupeřů a jejich jednotlivá jména např. do pole.
2. Jména seřadit libovolným řadícím algoritmem.
3. Vytvořit všechny dvojice (kombinace bez opakování) např. pomocí dvojitého cyklu procházejícího seřazené pole jmen soupeřů.
4. Každou vytvořenou dvojici rovnou vypsat v požadovaném formátu.

Příklad zdrojového kódu:

#include <iostream> #include <fstream> #include <vector> #include <string> #include <algorithm> using namespace std; int main() { int n; string ss; getline(cin, ss); n = stoi(ss); vector<string> s(n); for (int i = 0; i < n; i++) { getline(cin, s[i]); } sort(s.begin(), s.end()); int x = 1; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { cout << x << ". " << s[i] << " : " << s[j] << endl; x++; } } }

Finálové úlohy - řešení

Nejprve je stručně popsán způsob, jakým je možno úlohu řešit. Následně je ukázán zdrojový kód řešení vytvořeného jedním z finalistů.

K nahlédnutí je rovněž prezentace s popisem řešení předvedená po skončení finále.

Doučování

1. Načíst si počet rozvrhových akcí a následně jednotlivé akce např. do pole objektů či záznamů.
2. Vygenerovat všechny kombinace pěti rozvrhových akcí bez opakování, např. pomocí pěti vnořených cyklů.
3. Pro každou pětici spočítat, zda obsahuje tři metematiky a dvě informatiky. Dále ověřit, zda se rozvrhové akce pětice vzájemně nepřekrývají, např. pomocí dvourozměrného pole příznaků představující tabulku rozvrhu. Dále ověřit že jsou stejné předměty v různý den, např. pomocí dvou polí příznaků představující dny týdne.
4. Pro každou platnou pětici inkrementovat čítač.
5. Vypsat hodnotu čítače.

Příklad zdrojového kódu:

#include <iostream> #include <algorithm> #include <math.h> #include <cmath> #include <vector> #include <string> using namespace std; int main() { int r; cin >> r; char a; int mat = 0; int inf = 0; vector<int> matden(r); vector<int> infden(r); vector<int> mathod1(r); vector<int> mathod2(r); vector<int> infhod1(r); vector<int> infhod2(r); int den, b, c; int vysledek = 0; int matpomoc = 0; int infpomoc = 0; for (int i = 0; i < r; i++) { cin >> a >> den >> b >> c; if (a == int('M')) { mat++; matden[matpomoc] = den; mathod1[matpomoc] = b; mathod2[matpomoc] = c; matpomoc ++; } else if (a == int('I')) { inf++; infden[infpomoc] = den; infhod1[infpomoc] = b; infhod2[infpomoc] = c; infpomoc++; } } if (mat < 3 || inf < 2) { cout << "0" << endl; } else { for (int i = 0; i < matpomoc; i++) { for (int j = i+1; j < matpomoc; j++) { for(int k = j+1; k < matpomoc; k++) { if (matden[i] == matden[j] || matden[j] == matden[k] || matden[k] == matden[i]) continue; else { for (int l = 0; l < infpomoc; l++) { for (int m = l + 1; m < infpomoc; m++) { if (infden[l] == infden[m]) continue; else { bool odpoved = 1; if (matden[i] == infden[l]) { if (mathod1[i] <= infhod1[l] && infhod1[l] <= mathod2[i]) odpoved = 0; if (mathod1[i] <= infhod2[l] && infhod2[l] <= mathod2[i]) odpoved = 0; } if (matden[i] == infden[m]) { if (mathod1[i] <= infhod1[m] && infhod1[m] <= mathod2[i]) odpoved = 0; if (mathod1[i] <= infhod2[m] && infhod2[m] <= mathod2[i]) odpoved = 0; } if (matden[j] == infden[l]) { if (mathod1[j] <= infhod1[l] && infhod1[l] <= mathod2[j]) odpoved = 0; if (mathod1[j] <= infhod2[l] && infhod2[l] <= mathod2[j]) odpoved = 0; } if (matden[j] == infden[m]) { if (mathod1[j] <= infhod1[m] && infhod1[m] <= mathod2[j]) odpoved = 0; if (mathod1[j] <= infhod2[m] && infhod2[m] <= mathod2[j]) odpoved = 0; } if (matden[k] == infden[l]) { if (mathod1[k] <= infhod1[l] && infhod1[l] <= mathod2[k]) odpoved = 0; if (mathod1[k] <= infhod2[l] && infhod2[l] <= mathod2[k]) odpoved = 0; } if (matden[k] == infden[m]) { if (mathod1[k] <= infhod1[m] && infhod1[m] <= mathod2[k]) odpoved = 0; if (mathod1[k] <= infhod2[m] && infhod2[m] <= mathod2[k]) odpoved = 0; } if(odpoved == 1) vysledek++; } } } } } } } } cout << vysledek << endl; }

Grandiózní výmls

1. Pro každou mapu (testovací případ) si načíst akční limit mravenečníka a počet jednotlivých mravenišť.
2. Připravit si akumulační matici 1025 x 1025 s nulovými hodnotami odpovídající mapě.
3. Načítat jednotlivá mraveniště a v okolí odpovídající akčnímu limitu mravenečníka (čtvercová oblast) každého mraveniště přičíst do buněk akumulační matice počet mravenců mraveniště.
4. Projít celou akumulační matici a najít maximální hodnotu, která má nejnižší souřadnici x a y.
5. Vypsat souřadnice nalezené maximální hodnoty a maximální hodnotu.

Příklad zdrojového kódu:

#include <iostream> #include <string> #include <vector> struct mrav { int x, y; int val; }; int main() { int mc; std::cin >> mc; std::vector<mrav> res; for (int i = 0; i < mc; i++) { int** map = new int* [1025] {}; for (int i = 0; i < 1025; i++) { map[i] = new int[1025] {}; } int a, pm; std::cin >> a >> pm; for (int t = 0; t < pm; t++) { mrav m; std::cin >> m.x >> m.y >> m.val; for (int j = -a; j <= a; j++) { for (int k = -a; k <= a; k++) { if (m.y + j >= 0 && m.y + j < 1025 && m.x + k >= 0 && m.x + k < 1025) map[m.y + j][m.x + k] += m.val; } } } mrav max = { 0, 0, 0 }; for (int i = 0; i < 1025; i++) { for (int j = 0; j < 1025; j++) { int sum = map[i][j]; if (sum > max.val) { max.val = sum; max.y = i; max.x = j; } else if (sum == max.val) { if (max.x > j) { max.x = j; max.y = i; } if (max.x == j) { if (max.y > i) { max.x = j; max.y = i; } } } } } res.push_back({ max.x, max.y, max.val }); for (int i = 0; i < 1025; i++) { delete[] map[i]; } delete[] map; } for (int i = 0; i < res.size(); i++) { auto a = res[i]; std::cout << a.x << " " << a.y << " " << a.val << std::endl; } // zjisi return 0; }

Netwars

1. Načíst si počet účastníků a následně jednotlivé účastníky např. do pole objektů či záznamů.
2. Při načítání účastníka si uložit jeho přezdívku a následně číst jednotlivé počty požadavků a přičítat je do celkového počtu požadavků účastníka, dokud není prázdná řádka (ukládat jednotlivé počty není potřeba).
3. Seřadit účastníky sestupně podle celkového počtu požadavků pomocí libovolného algoritmu řazení.
4. Vypsat první tři účastníky v požadovaném formátu.

Příklad zdrojového kódu:

#include <iostream> #include <set> #include <vector> #include <algorithm> #include <cmath> #include <string> using namespace std; int main() { string s; getline(cin, s); int n = stoi(s); vector<pair<int, string>> uc(n); for (int i = 0; i < n; i++) { getline(cin, uc[i].second); int x = 0; while (1) { getline(cin, s); if (s == "") { uc[i].first = x; break; } x += stoi(s); } } sort(uc.begin(), uc.end(), greater<pair<int, string>>()); cout << uc[0].second << " (" << uc[0].first << ") " << endl; cout << uc[1].second << " (" << uc[1].first << ") " << endl; cout << uc[2].second << " (" << uc[2].first << ") " << endl; }

Poslední jezdec apokalypsy

1. Vytvořit si mapu vzdáleností jednotlivých políček na maximální šachovnici pomocí prohledávání do šířky ze středu šachovnice. Je třeba ošetřit speciální případy v rozích a pro šachovnici 4 x 4. Minimální vzdálenost políček (v počtu skoků jezdce) lze pak určit dotazem do této mapy i pro menší mapy.
2. Pro každý testovací případ si načíst velikost mapy a pozice zajímavých políček.
3. Návštěva všech zajímavých políček je problém obchodního cestujícího, který lze pro malý počet vrcholů řešit např. pomocí dynamického programování s bitovou maskou:
   • Políčka očíslovat 0, 1, ..., k-2, k-1. Startovací i cílové políčko bude k-1. Vytvořit si tabulku (dvourozměné pole) o velikosti (k-1) x 2^k-1.
   • Do tabulky postupně vyplňovat minimální počet skoků jezdce ze startu (k-1) končícího na políčku odpovídímu indexu řádky tabulky při využití navštívené podmnožiny všech políček (v libovolném pořadí).
   • Konkrétní podmnožina odpovídá sloupci tabulky a její prvky (tj. navštívená zajímavá políčka) jsou popsány pomocí bitové masky.
   • Při určování prvků tabulky využít již vypočtené hodnoty z tabulky a dříve vytvořenou mapu vzdáleností políček.
   • Po vyplnění tabulky lze z posledního sloupce tabulky zjistit minimálmí počet skoků při navštívení všech zajímavých políček.
4. Vypsat minimální hodnotu zjištěnou z tabulky.

Příklad zdrojového kódu:

Tuto úlohu žádný soutěžící nevyřešil.

Slevička

1. Pro každý testovací případ si načíst si ceny jednotlivých jídel, složení a ceny výhodných menu a složení objednávek.
2. Pomocí dynamického programování si určit minimální ceny pro všechny možné objednávky:
   • N-tici čísel 0 až 9 reprezentovat jako celočíselný index 0 až 10^N.
   • Vytvořit tabulku (jednorozměrné pole), kde index odpovídá N-tici a hodnota minimální ceně, za kterou lze N-tici koupit.
   • Tabulku vyplňovat sekvenčně od indexu 0. Cenu na indexu 0 inicializovat na 0, zbytek na maximální hodnotu.
   • Pro každý index se známou minimální cenou spočítat další indexy, na které se z něj lze dostat ať už nákupem nějakého jednotlivého jídla nebo výhodného menu, a též spočítat cenu (známé cenové minimum na výchozím indexu plus nákupní cena za uvažovaný nákup pro cílový index). Na těchto indexech minimalizovat stávající hodnoty v tabulce.
   • Po vyhodnocení všech indexů jsou známé minimální ceny pro všechny možné objednávky.
3. Sečíst minimální ceny všech načtených objednávek zjištěné z vyplněné tabulky a výsledek vypsat.

Příklad zdrojového kódu:

Tuto úlohu žádný soutěžící nevyřešil.

 

© 2017 PilsProg tým | Katedra informatiky a výpočetní techniky | Fakulta aplikovaných věd Západočeské univerzity v Plzni