PilsProg 2022

Výsledky Lite

#JménoPříjmeníSplněných úlohČas
1JáchymKouba932,666
2DenisaVítková9181,634
3OndřejNový9872,245
4MatějMazánek7403,370

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

Výsledky kvalifikace

#JménoPříjmeníSplněných úlohČasFinále
1DanielSkýpala6156,498Postupuje do finále
2KristýnaPetrlíková6360,093Postupuje do finále
3JáchymKouba6710,108Postupuje do finále
4MartinBenda3950,656Postupuje do finále
5DenisaVítková31 255,222Postupuje do finále
6LukášTomoszek33 528,279Postupuje do finále
7ŠtěpánKuch2102,673Postupuje do finále
8LukášProtiva2229,421Postupuje do finále
9OndřejBulka21 647,361Postupuje do finále
10OndřejBartoš21 929,242Postupuje do finále
11JanMátl22 456,452Postupuje do finále
12VojtěchŠebek11 233,470-
13JosefMaštalíř11 253,030-

Výsledky finále

#JménoPříjmeníSplněných úlohČas
1DanielSkýpala46,195
2KristýnaPetrlíková46,480
3LukášTomoszek10,890
4JanMátl12,783
5OndřejBartoš12,924
6LukášProtiva00,000
7JáchymKouba00,000
8DenisaVítková00,000
9ŠtěpánKuch00,000
10MartinBenda00,000
11OndřejBulka00,000

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

Poznámka: Finalista Štěpán Kuch a Denisa Vítková se finálové soutěže nezúčastnili.

Ilustrační úlohy

NázevČísloÚspěšných řešitelů
AxB17015
AplusB17023
Největší ze tří celých čísel17034
Pascalův trojúhelník17043

Lite1 úlohy

NázevČísloÚspěšných řešitelů
Cik cak22113
Převod teplot22124
Řazení osob22134

Lite2 úlohy

NázevČísloÚspěšných řešitelů
Součet matice22144
Úplné vyhledávání22154
Uživatelská jména22164

Lite3 úlohy

NázevČísloÚspěšných řešitelů
Plocha pevniny22174
Rodné číslo22184
Součet účtu22193

Kvalifikační úlohy

NázevČísloÚspěšných řešitelů
Číselný úděl22217
Garance čerstvosti22223
Ptačí hodinka222313
Roboúklid22243
Síla magie22253
Zamotaná matice222610

Finálové úlohy

NázevČísloÚspěšných řešitelů
Dračí jezdec22315
Matemagik22322
Netradiční výzva22330
Ohmova záchranná mise22342
Sociální bublina22352

A jaké bylo finále?

Finále začíná ...

Harmonogram PilsProg 2022

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.

Cik cak

  1. Načíst počet řádek a sloupců matice.
  2. Určit si hodnotu maximálního prvku matice (stačí vynásobit počet řádek a sloupců a odečíst 1 - hodnoty prvků začínají na 0).
  3. Určit si počet cifer maximálního prvku matice (např. postupným dělením 10).
  4. Vypsat prvky matice s nevýznamovými mezerami podle počtu cifer maximálního prvku. V lichých řádkách vypisovat rostoucí hodnoty zleva doprava a v sudých řádkách vypisovat klesající hodnoty rovněž zleva doprava. Hodnotu aktuálního prvku spočítat z aktuálních indexů řádky a sloupce.

Příklad zdrojového kódu:

#include <iostream> #include <iomanip> int main() { size_t rows {0}; size_t columns {0}; std::cin >> rows; std::cin >> columns; bool oddRow = false; size_t lastKnownNumber {0}; size_t temp = rows * columns - 1; int digitsCount {}; while (temp != 0) { digitsCount++; temp /= 10; } for (size_t i {}; i < rows; i++) { if (oddRow) { lastKnownNumber += (columns - 1); for (size_t j {}; j < columns; j++) { std::cout << std::setw(digitsCount) << lastKnownNumber-- << " "; } lastKnownNumber += (columns + 1); } else { for (size_t j {}; j < columns; j++) { std::cout << std::setw(digitsCount) << lastKnownNumber++ << " "; } } std::cout << "\n"; oddRow = !oddRow; } return 0; }

Převod teplot

  1. Načíst řetězec do prvního bílého znaku ze vstupu.
  2. Pokud řetězec začíná znakem „X“ nebo „x“, skončit.
  3. Pokud ne, převést řetězec na celé číslo (teplotu) a načíst další řetězec do prvného bílého znaku (tj. řetezec bude jeden znak vyjadřující stupnici).
  4. Podle zadaného znaku stupnice přepočítat zadanou teplotu do zbylých dvou stupnic a zaokrouhlit na celé stupně.
  5. Převedené teploty vytisknout ve správném pořadí v zadaném formátu.

Příklad zdrojového kódu:

import java.util.ArrayList; import java.util.List; import java.util.Scanner; public class Teplota { public static void main(String[] args){ Scanner sc = new Scanner(System.in); int rows = 0; List<Integer> n = new ArrayList<>(); List<String> y = new ArrayList<>(); int tempN; String tempY; tempN = sc.nextInt(); tempY = sc.next(); while(!tempY.equals("x") && !tempY.equals("X")) { n.add(tempN); y.add(tempY); rows++; if(sc.hasNextInt())tempN = sc.nextInt(); tempY = sc.next(); } for(int i=0; i<rows; i++) { switch (y.get(i)){ case "f": case"F": if(rows-i==1) System.out.print(Math.round((n.get(i)-32)/1.8) + " C, " + Math.round(((n.get(i)-32)/1.8)+273.15) + " K"); else System.out.println(Math.round((n.get(i)-32)/1.8) + " C, " + Math.round(((n.get(i)-32)/1.8)+273.15) + " K"); break; case "c": case "C": if(rows-i==1) System.out.print(Math.round((n.get(i)*1.8)+32) + " F, " + Math.round(n.get(i)+273.15) + " K"); else System.out.println(Math.round((n.get(i)*1.8)+32) + " F, " + Math.round(n.get(i)+273.15) + " K"); break; case "k": case"K": if(rows-i==1) System.out.print(Math.round(n.get(i)-273.15) + " C, " + Math.round(((n.get(i)-273.15)*1.8)+32) + " F"); else System.out.println(Math.round(n.get(i)-273.15) + " C, " + Math.round(((n.get(i)-273.15)*1.8)+32) + " F"); break; } } } }

Řazení osob

  1. Načíst počet osob.
  2. Načíst si jména a příjmení osob a uložit je do pole objektů/záznamů, kde každý objekt/záznam odpovídá jedné osobě se jménem a příjmením.
  3. Pole seřadit libovolným algoritmem řazení, přičemž při porovnávání jednotlivých osob je třeba zohlednit primárně příjmení a, pokud jsou příjmení stejná, sekundárně i jména.
  4. Vypsat seřazené osoby (příjmení a jméno).

Příklad zdrojového kódu:

#include <iostream> #include <string> #include <vector> #include <algorithm> using namespace std; int main() { int o{}; cin >> o; cin.ignore(); string first_name{}; string last_name{}; vector<string> names(o); for(int i{0}; i<o; i++) { cin >> first_name >> last_name; names[i] = (last_name + " " + first_name); } sort(names.begin(), names.end()); for(int i{0}; i<o; i++) { cout << names[i] << endl; } return 0; }

Součet matice

  1. Načíst počet matic (testovacích případů).
  2. Pro každou matici načíst její řád (počet řádek/sloupců).
  3. Určit počet prvků matice (druhá mocnina jejího řádu).
  4. Určit hodnotu posledního prvku matice (počet prvků zmenšený o 1 - prvky začínají od 0).
  5. Součet prvků matice spočítat pomocí vzorce pro součet prvních n členů aritmetické řady a součet vypsat.

Příklad zdrojového kódu:

#include <iostream> using namespace std; int main() { int m; cin >> m; for (int i = 0; i < m; i++) { int n; cin >> n; n = n * n - 1; cout << (n * (n + 1) / 2) << endl; } return 0; }

Úplné vyhledávání

  1. Načíst počet vyhledávání (testovacích případů) a počet prvků posloupnosti.
  2. Načíst prvky posloupnosti a uložit si je do pole celých čísel.
  3. Načítat jednotlivá hledaná čísla.
  4. Pro každé hledané číslo projít celé pole od začátku do konce a porovnávat hledané číslo s prvky pole. Při shodě inkrementovat čítač nalezných výskytů a vypsat aktuální index.
  5. Pokud prvek nebyl nalezen (tj. čítač nalezených výskytů bude 0), vypsat „Nenalezeno“.

Příklad zdrojového kódu:

#include <iostream> using namespace std; int main() { int v, p; cin >> v >> p; int* pole = new int[p]; for (int i = 0; i < p; i++) cin >> pole[i]; for (int i = 0; i < v; i++) { int c; cin >> c; bool bylo = 0; for (int j = 0; j < p; j++) if (pole[j] == c) { if (bylo == 1) cout << ", "; bylo = 1; cout << j; } if (bylo == 0) cout << "Nenalezeno."; cout << endl; } delete[] pole; return 0; }

Uživatelská jména

  1. Načíst počet osob.
  2. Načítat si jména a příjmení osob.
  3. Pro každou osobu vytvořit uživatelské jméno zřetězením prvního znaku jména a maximálně 7 znaků příjmení. Pro uživatelské jméno se tedy použije celé příjmení, pokud je jeho počet znaků menší nebo roven 7, nebo podřetězec z příjmení o délce 7 znaků.
  4. Pro každou osobu vypsat jméno (jak bylo načteno) příjmení velkými písmeny a vytvořené uživatelské jméno.

Příklad zdrojového kódu:

import java.util.ArrayList; import java.util.Scanner; public class Uzivatele { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int s; ArrayList<String> jmeno = new ArrayList<String>(); ArrayList<String> prijmeni = new ArrayList<String>(); s = sc.nextInt(); for (int i = 0;i < s;i++) { jmeno.add(sc.next()); prijmeni.add(sc.next()); } for (int i = 0;i < jmeno.size();i++) { if (prijmeni.get(i).length() > 6) System.out.println(jmeno.get(i) + " " + prijmeni.get(i).toUpperCase() + " " + jmeno.get(i).toLowerCase().charAt(0) + prijmeni.get(i).toLowerCase().substring(0, 7)); else System.out.println(jmeno.get(i) + " " + prijmeni.get(i).toUpperCase() + " " + jmeno.get(i).toLowerCase().charAt(0) + prijmeni.get(i).toLowerCase().substring(0, prijmeni.get(i).length())); } } }

Plocha pevniny

  1. Načíst počet řádek a sloupů mapy světa.
  2. Načítat jednotlivé řádky mapy.
  3. Pro každou řádku projít všechny načtené znaky. Při nalezení znaku „#“ inkrementovat čítač plochy pevniny o 1.0 a při nalezení znaku „*“ o 0.5.
  4. Spočítat procentuální podíl pevniny jako poměr plochy pevniny ku celkové ploše mapy světa (lze spočítat jako součin počtu řádek a sloupců).
  5. Výsledek zaokrouhlit na celá čísla a vypsat v požadovaném formátu.

Příklad zdrojového kódu:

#include <iostream> #include <math.h> using namespace std; int main() { int r{}; int s{}; cin >> r >> s; double pevnina{}; char policko{}; for(int i{0}; i<r; i++) { for(int j{0}; j<s; j++) { cin >> policko; if(policko == '#') { pevnina += 1; } else if(policko == '*'){ pevnina += 0.5; } } } double procent = round(pevnina*100/(r*s)); cout << procent << "%" << endl; return 0; }

Rodné číslo

  1. Načíst počet rodných čísel (testovacích případů).
  2. Načítat jednotlivá rodná čísla jako řetězce.
  3. Pro každé rodné číslo extrahovat údaje o pohlaví a datu narození z prvních šesti číslic.
  4. Rok určit z prvních dvou číslic zprava. Pokud je větší než 21, přičíst 1900, jinak přičíst 2000.
  5. Měsíc určit z druhých dvou číslic zprava. Pokud je větší než 50, odečíst 50 a zaznamenat si ženské pohlaví.
  6. Den určit z třetích dvou číslic zprava.
  7. Ověřit platnost rodného čísla určením zbytku po dělení 11 - z řetězce s rodným číslem odstranit lomítko, převést ho na číslo (pozor, je nutný celočíselný datový typ s dostatečným rozsahem) a zjistit zbytek po celočíselném dělení operací modulo.
  8. Vypsat pohlaví, datum narození a platnost rodného čísla v požadovaném formátu.

Příklad zdrojového kódu:

#include <iostream> #include <string> #include <vector> #include <charconv> #include <sstream> using namespace std::string_literals; int main() { std::vector<std::string> idNumbers{}; std::string input{}; std::getline(std::cin, input, '\n'); int8_t idNumberCount{-1}; std::from_chars( input.data(), input.data() + input.length(), idNumberCount, 10 ); for (int8_t i{}; i < idNumberCount; i++) { std::getline(std::cin, input, '\n'); idNumbers.emplace_back(input); } for (int8_t i{}; i < idNumberCount; i++) { std::string &idNumber = idNumbers[i]; int32_t year{}; int32_t month{}; int32_t day{}; int32_t afterSlash{}; { std::from_chars( idNumber.data(), idNumber.data() + 2, year, 10 ); std::from_chars( idNumber.data() + 2, idNumber.data() + 4, month, 10 ); std::from_chars( idNumber.data() + 4, idNumber.data() + 6, day, 10 ); std::from_chars( idNumber.data() + 7, idNumber.data() + 10, afterSlash, 10 ); (year > 21) ? year += 1900 : year += 2000; } { printf("%s ", ((month > 12) ? "zena" : "muz")); } { printf("%d.%d.%d ", day, ((month > 12) ? month - 50 : month), year); } { std::string st {idNumber.substr(0, 6) + idNumber.substr(7, 4)}; uint64_t fullIdNumber{}; std::stringstream ss{}; ss << st; ss >> fullIdNumber; printf("%s\n", (((fullIdNumber % 11) == 0) ? "platne" : "neplatne")); } } return 0; }

Součet účtu

  1. Načíst si počet položek účtu.
  2. Načíst si množství a jednotkovou cenu jednotlivých položek a uložit je do pole objektů/záznamů, kde každý objekt/záznam odpovídá jedné položce účtu.
  3. Pro každou položku účtu si spočítat její cenu.
  4. Seřadit pole položek podle ceny, přičemž je potřeba použít stabilní algoritmus řazení (tedy takový, který zachová pořadí prvků se stejnou hodnotou - např. řazení vkládáním nebo slučováním).
  5. Projít celé pole položek a vypisovat jednotlivé položky v požadovaném formátu na jednotlivé řádky. Cenu každé položky přičíst do celkového součtu a zaznamenat si nevyšší délku vypsané řádky.
  6. Vypsat pomlčky, přičemž jejich počet bude odpovídat délce nejdelší vypsané řádky s položkou účtu.
  7. Vypsat celkovou cenu účtu v požadovaném formátu.

Příklad zdrojového kódu:

#include <iostream> #include <vector> #include <algorithm> #include <string> #include <sstream> using namespace std; vector<long long int> vysledna; bool comp(const long long int& a, const long long int& b) { return vysledna[a] > vysledna[b]; } int main() { int polozek{}; cin >> polozek; vector<int> mnozstvi; vector<int> ceny; vector<int> indexy; int pocet{}; int cena{}; for(int i{0}; i<polozek; i++) { cin >> pocet >> cena; mnozstvi.push_back(pocet); ceny.push_back(cena); vysledna.push_back(pocet*cena); indexy.push_back(i); } //cin >> cena; stable_sort(indexy.begin(), indexy.end(), comp); long int nejdelsi{}; long long int sum{}; for(int i{0}; i<polozek; i++) { stringstream mn; stringstream ce; stringstream vy; string vypis{}; mn << mnozstvi[indexy[i]]; vypis.append(mn.str()); vypis.append(" x "); ce << ceny[indexy[i]]; vypis.append(ce.str()); vypis.append(" = "); vy << vysledna[indexy[i]]; vypis.append(vy.str()); //string vypis = std::to_string(mnozstvi[indexy[i]]) + " x " + std::to_string(ceny[indexy[i]]) + " = " + std::to_string(vysledna[indexy[i]]); //string vypis = mnozstvi[indexy[i]] + " x " + ceny[indexy[i]] + " = " + vysledna[indexy[i]] + "\n"; if(vypis.size() > nejdelsi) { nejdelsi = vypis.size(); } sum += vysledna[indexy[i]]; cout << vypis << endl; //cout << mnozstvi[indexy[i]] << " x " << ceny[indexy[i]] << " = " << vysledna[indexy[i]] << endl; } for(int i{0}; i<nejdelsi; i++) { cout << "-"; } cout << endl; cout << "Celkem " << sum; return 0; }

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.

Číselný úděl

  1. Načíst si jednotlivá čísla.
  2. Načtená čísla chápat jako vrcholy grafu. Pokud jsou dvě čísla soudělná, spojit vrcholy příslušející těmto číslům hranou. Soudělnost testovat algoritmem pro určení největšího společného dělitele.
  3. Po vytvoření grafu už jen spočítat komponenty grafu (například pomocí DFS - prohledávání do hloubky) a vypsat jako výsledný počet skupin.

Příklad zdrojového kódu:

#include <iostream> #include <vector> using namespace std; struct node { long long num; bool visited = false; vector<int> neigh; }; int n; vector<node> nodes; void search(int i) { if (nodes[i].visited) { return; } nodes[i].visited = true; for (int x: nodes[i].neigh) { search(x); } } long long gcd(long long a, long long b) { if (a<b) { return gcd(b, a); } if (b==0) { return a; } return gcd(b, a%b); } int main() { long long a; for (int i=0;; i++) { cin >> a; if (a == 0) break; nodes.resize(i+1); nodes[i].num = a; } n=nodes.size(); for (int i=0; i<n; i++) { for (int j=i+1; j<n; j++) { if (i != j && gcd(nodes[i].num, nodes[j].num) > 1) { // cout << i << " " << j << endl; nodes[i].neigh.push_back(j); nodes[j].neigh.push_back(i); } } } int groups = 0; for (int i=0; i<n; i++) { if (!nodes[i].visited) { groups++; search(i); } } cout << groups << endl; }

Garance čerstvosti

  1. Načíst výšku a šířku a následně jednotlivá políčka mapy.
  2. Pro každou potravinu si vytvořit 2D mapu vzdáleností pomocí BFS (prohledávání do šířky) - do fronty si na počátku vložit všechny výdejní místa dané potraviny. Vzdálenostní mapa pro danou potravinu určuje pro každé políčko (i, j) minimální vzdálenost k této surovině.
  3. Vytvořené vzdálenostní mapy (pro každou potravinu) pak přeložit přes sebe a pro každé políčko určit maximum. Z těchto maxim pak určit globální minimum a vypsat ho jako výsledek.

Příklad zdrojového kódu:

#include <bits/stdc++.h> using namespace std; typedef pair<int, int> ii; typedef vector<int> vi; typedef vector<vi> vvi; typedef vector<ii> vii; #define F first #define S second int main(){ int s, v; cin >> s >> v; cin.ignore(); vector<string> m(v); vector<vii> f(3); for(int i = 0; i < v; i++){ string str; getline(cin, str); for(int j = 0; j < s; j++){ if(str[j] >= 'A' && str[j] <= 'C') f[str[j]-'A'].push_back({i,j}); } m[i] = str; } vector<vvi> md(3, vvi(v, vi(s, -1))); for(int i = 0; i < 3; i++){ queue<pair<ii, int>> q; vvi vis(v, vi(s, false)); for(const ii& pos: f[i]){ q.push({pos, 0}); } while(!q.empty()){ auto a = q.front(); q.pop(); ii pos = a.first; int d = a.second; if(vis[pos.F][pos.S]) continue; vis[pos.F][pos.S] = true; if(m[pos.F][pos.S] == '.') md[i][pos.F][pos.S] =d; int x = -1, y = 0; for(int p = 0; p < 4; p++){ ii pp = {pos.F+x, pos.S+y}; if(pp.F >= 0 && pp.F < v && pp.S >= 0 && pp.S < s && m[pp.F][pp.S] == '.') q.push({pp, d+1}); swap(x, y); y *= -1; } } } int res = -1; for(int i = 0; i < v; i++){ for(int j = 0; j < s; j++){ int tmp = max(max(md[0][i][j], md[1][i][j]), md[2][i][j]); if(md[0][i][j] != -1 && md[1][i][j] != -1 && md[2][i][j] != -1){ if(res == -1) res = tmp; res = min(res, tmp); } } } assert(res != -1); cout << res << "\n"; }

Ptačí hodinka

  1. Načíst si ze vstupu pravidelnou mřížku zachycující scénu (detekované ptáky/prázdné buňky) do dvourozměrného pole znaků.
  2. Projít načtená data a stanovit počet výskytů každého znaku (kromě mezer), přičemž počty výskytů jsou ukládány do vhodné datové struktury.
  3. Stanovit počet porozovaných druhů a vypsat jej.
  4. Pokud je to potřeba (závisí na zvolené datové struktuře), seřadit počet výskytů jednotlivých druhů podle ASCII hodnoty znaku označujícího druh a vypsat v předepsaném formátu.

Příklad zdrojového kódu:

import java.util.Arrays; import java.util.HashMap; import java.util.Scanner; public class PtaciHodinka { private static HashMap<Character,Integer> data = new HashMap<>(); public static void main(String[] args) { Scanner sc = new Scanner(System.in); int pocetRadku = sc.nextInt(); sc.nextInt(); char znak; String retezec; for(int i = pocetRadku; i >= 0; i--) { retezec = sc.nextLine(); for(int j = 0; j < retezec.length(); j++) { znak = retezec.charAt(j); if(data.containsKey(znak)) { data.replace(znak, data.get(znak) + 1); } else if(!(znak == ' ')){ data.put(znak,1); } } } System.out.println(vypis()); } public static String vypis() { int[] kliceASCII = new int[data.size()]; String vystup = kliceASCII.length + "\n"; for(int i = 0; i < kliceASCII.length; i++) { kliceASCII[i] = (int)((char) data.keySet().toArray()[i]); } Arrays.sort(kliceASCII); for(int klic : kliceASCII) { vystup += (char) klic + " = " + data.get((char) klic) + "\n"; } return vystup; } }

Roboúklid

  1. Načíst ze vstupu výšku a šířku a následně jednotlivá políčka mapy.
  2. Mapa popisuje jednoduchý graf, který má podobu pravidelného dvourozměrného rastru. Cílem je zjistit délku maximálního Eulerovského tahu či kružnice. Analogická úloha je zjistit maximální možný počet skoků jedním kamenem ve hře Dáma.
  3. Vstupní data jsou dostatečně malá, aby toto řešení doběhlo ve stanoveném časovém limitu.
  4. Problém řešit metodou backtracking. Pro danou pozici vysavače uvažovat 4 směry, kudy může vést chodba do jiné místnosti. Pro každý směr, pro který existuje chodba do jiné místnosti, předpokládat, že už je v této místnosti známo maximum. Kdyby se tímto směrem vysavač pohyboval, tak délka jeho cesty bude toto maximum + 1. Při výběru maxima přes všechny možné směry z dané pozice vysavače vyjde maximum pro pozici vysavače.
  5. Předpoklad znalosti maxima realizovat pomocí rekurze. Nechť funkce maxLength(i, j) vrací pro pozici i a j délku maximálního Eulerovského tahu. Pro pozici (i, j) toto maximum vyčíslit jako maximum přes všechny možné směry s použitím funkce maxLength(i + posun_i, j + posun_j). Před vyhodnocováním směru (posun_i, posun_j) pomocí funkce maxLength() je pouze nutno smazat chodbu v tomto směru a po návratu z rekurzivního volání maxLength() je nutno tuto chodbu zase vrátit.
  6. Nalezenou délku maximálního Eulerovského tahu vypsat.

Příklad zdrojového kódu:

#include <bits/stdc++.h> using namespace std; typedef vector<bool> vb; typedef pair<int, int> ii; #define F first #define S second vector<string> v; vector<vb> vis; int r, s; int mx = 0; void dfs(ii u, ii e, int d){ if(e.F != -1 && vis[e.F][e.S]) return; if(e.F != -1) vis[e.F][e.S] = true; mx = max(mx, d); int a = -1, b = 0; for(int p = 0; p < 4; p++){ ii pp = {u.first + a, u.second + b}; if(pp.F >= 0 && pp.F < r && pp.S >= 0 && pp.S < s){ if(v[pp.F][pp.S] == '|' || v[pp.F][pp.S] == '-'){ ii qq = {pp.F + a, pp.S + b}; dfs(qq, pp, d+1); } } swap(a, b); b *= -1; } if(e.F != -1) vis[e.F][e.S] = false; } int main(){ cin >> r >> s; cin.ignore(); v.resize(r); vis.assign(r, vb(s, 0)); ii start; for(int i = 0; i < r; i++){ string str; getline(cin, str); for(int j = 0; j < s; j++){ if(str[j] == 's') start = {i, j}; } v[i] = str; } dfs(start, {-1,-1}, 0); cout << mx << "\n"; }

Síla magie

  1. Načíst runy jednotlivých cípů pentagramu.
  2. Vyzkoušet všechny možnosti (všechna možná zaklínadla - slova délky 5) a spočítat ty, která projdou omezujícími podmínkami pentagramu.
  3. Každá z 5 řádek na vstupu udává seznam znaků, která lze v daném cípu pentagramu použít (malá písmena anglické abecedy). Pro rychlejší testování tento seznam uchovat jako bitovou masku (znaky „a“ - „z“ převést do rozsahu 0 - 26 a použít jako index bitu - bit nastavit na 1, pokud je znak použit, jinak 0).
  4. Poté vyzkoušet všech 265 - 1 možností „zaklínadel“. Každou možnost otestovat, zda vyhovuje zadání nebo ne, a spočítat vyhovující možnosti.
  5. Test, zda konkrétní „zaklínadlo“ vyhovuje zadání, je následující: pro každý z 5 cípů a každý ze 2 možných směrů udělat jeden průchod 5 cípy pentagramu, při každém kroku kontrolovat, zda je aktuální písmeno zaklínadla povoleno pro aktuální cíp pentagramu - otestovat bit na příslušné pozici v bitové masce náležící příslušnému cípu pentagramu.
  6. Počet vyhovujících zaklínadel vypsat na výstup jakožto sílu magie.

Příklad zdrojového kódu:

#include <iostream> #include <vector> #include <set> #include <algorithm> using namespace std; vector<vector<char>> runes(5); vector<vector<char>> new_runes(5); vector<char> unique(vector<char> n) { if (n.size() == 0) { return {}; } sort(n.begin(), n.end()); vector<char> res = {n[0]}; for (int i=1; i<n.size(); i++) { if (n[i] != n[i-1]) res.push_back(n[i]); } return res; } vector<char> intersect(vector<char> * a, vector<char> * b) { vector<char> same; int ai=0, bi=0; while (true) { if (ai >= a->size() || bi >= b->size()) break; if (a->at(ai) > b->at(bi)) { bi++; } else if (a->at(ai) < b->at(bi)) { ai++; } else { same.push_back(a->at(ai)); ai++; bi++; } } return same; } vector<char> multisect(vector<int> inter) { if (inter.size() == 1) { return new_runes[inter.at(0)]; } int x = inter.at(inter.size()-1); inter.pop_back(); vector<char> rest = multisect(inter); return intersect(&new_runes[x], &rest); } unsigned long long calc(vector<int> * inter) { unsigned long long sub = 1; int n = inter->size(); vector<int> points(n); for (int i=0; i<n; i++) { points[i] = inter->at(i) % 5; } vector<int> diffs(n); for (int i=0; i<n; i++) { diffs[i] = -2*(inter->at(i)>=5)+1; } for (int i=0; i<5; i++) { sub *= multisect(points).size(); for (int j=0; j<n; j++) { points[j] = (points[j] + diffs[j] + 5) % 5; } } return sub; } vector<vector<int>> gen(int depth) { vector<vector<int>> res = {}; if (depth == 1) { for (int i=0; i<10; i++) { res.push_back({i}); } return res; } vector<vector<int>> old = gen(depth-1); for (int i=0; i < old.size(); i++) { for (int j=old[i][old[i].size()-1]+1; j<10; j++) { res.push_back(old[i]); res[res.size()-1].push_back(j); } } return res; } int main() { cin >> noskipws; char c; for (int i=0; i<5; i++) { while (true) { cin >> c; if (!('a' <= c && c <= 'z')) { break; } runes[i].push_back(c); cin >> c; if (c != ' ') { break; } } sort(runes[i].begin(), runes[i].begin()); runes[i] = unique(runes[i]); } for (int i=0; i<5; i++) { new_runes[i] = runes[(2*i) % 5]; } vector<vector<int>> combs; unsigned long long res = 0; for (int i=1; i<=10; i++) { combs = gen(i); for (auto c: combs) { res += (2*(i%2)-1) * calc(&c); } // cout << res << endl; } cout << res << endl; }

Zamotaná matice

  1. Načíst si ze vstupu výšku a šířku a následně jednotlivé prvky matice.
  2. Pro každý ze čtyř rohů matice a každý ze dvou směrů projít matici po spirále a znaky z matice zapsat do řetězce.
  3. Každý z osmi výsledných řetězců otestuvat, zda je palindrom nebo ne.
  4. Pokud najdeme alespoň jeden palindrom, vypsat 1, jinak vypsat 0.

Příklad zdrojového kódu:

#include <bits/stdc++.h> using namespace std; string spiralOrder(vector<string>& matrix) { string ans = ""; if (matrix.empty()) return ans; int R = matrix.size(), C = matrix[0].size(); vector<vector<bool> > seen(R, vector<bool>(C, false)); int dr[] = { 0, 1, 0, -1 }; int dc[] = { 1, 0, -1, 0 }; int r = 0, c = 0, di = 0; // Iterate from 0 to R * C - 1 for (int i = 0; i < R * C; i++) { ans.push_back(matrix[r][c]); seen[r][c] = true; int cr = r + dr[di]; int cc = c + dc[di]; if (0 <= cr && cr < R && 0 <= cc && cc < C && !seen[cr][cc]) { r = cr; c = cc; } else { di = (di + 1) % 4; r += dr[di]; c += dc[di]; } } return ans; } bool isPalindrome(string S) { string P = S; reverse(P.begin(), P.end()); return S == P; } vector<string> rotate90matrix(vector<string> mat) { vector<string> a(mat[0].size(), ""); for (int i = 0; i < mat[0].size(); ++i) { for (int j = 0; j < mat.size(); ++j) { a[i] += mat[j][mat[0].size() - i - 1]; } } return a; } vector<string> rotate180matrix(vector<string> mat) { vector<string> a(mat.size(), ""); for (int i = 0; i < mat.size(); ++i) { for (int j = 0; j < mat[0].size(); ++j) { a[i] += mat[i][mat[0].size() - j - 1]; } } return a; } // Driver code int main() { int r, s; cin >> r >> s; vector<string> a; string asd; for (int i = 0; i < r; ++i) { cin >> asd; a.push_back(asd); } for (int i = 0; i < 4; ++i) { string hh = spiralOrder(a); bool x = isPalindrome(hh); if (x) { cout << "1" << endl; return 0; } a = rotate90matrix(a); } a = rotate180matrix(a); for (int i = 0; i < 4; ++i) { string hh = spiralOrder(a); bool x = isPalindrome(hh); if (x) { cout << "1" << endl; return 0; } a = rotate90matrix(a); } cout << "0" << endl; return 0; }

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.

Dračí jezdec

  1. Načíst si rozměr šachovnice, počet tahů jezdcem a počáteční pozici jezdce.
  2. Protože počet tahů je malý (maximálně 8), vyzkoušet všechny cesty o délce odpovídající počtu tahů. Lze použít hrubou sílu pro generování všech cest nebo např. backtracking.
  3. Vyřadit cesty, které vedou mimo šachovnici.
  4. Odstranit duplicitní výsledky a výsledky seřadit primárně podle x a sekundárně podle y. Obojí lze zařídit zanesením výsledků do 2D pole reprezentující šachovnici a následným vypsáním výsledků z tohoto pole po sloupcích.

Příklad zdrojového kódu:

#include <bits/stdc++.h> using namespace std; bool valid(int x, int y, int r){ return x > 0 && x <= r && y > 0 && y <= r; } int main(){ int r,t; cin >> r >> t; int x, y; cin >> x >> y; set<pair<int, int>> res; set<vector<int>> vis; queue<vector<int>> q; q.push({0, x, y}); while(!q.empty()){ auto curr = q.front(); q.pop(); if(vis.count(curr)) continue; vis.insert(curr); if(curr[0] == t){ res.insert({curr[1], curr[2]}); continue; } vector<vector<int>> off = { {1,2},{1,-2},{-1,2},{-1,-2}, {2,1},{2,-1},{-2,1},{-2,-1} }; for (int i = 0; i < 8; i++) { if (valid(curr[1] + off[i][0], curr[2] + off[i][1], r)) { q.push({curr[0]+1, curr[1] + off[i][0], curr[2] + off[i][1]}); } } } for(auto i: res){ cout << i.first << " " << i.second << "\n"; } }

Matemagik

  1. Načíst si maximální množství všech čtyř živlů.
  2. Určit si počet unikátních směsí jako počet variací všech možných hodnot živlů s výjimkou prázdné směsi pomocí vzorce s = (z1 + 1) * (z2 + 1) * (z3 + 1) * (z4 + 1) - 1
  3. Určit si počet různých způsobů, kterými lze ovlivnit kombinatorium jako počet všech n-tic (tj. dvojic, trojic, čtveřic atd.), jak lze unikátní směsi kombinovat.
  4. To lze určit např. z Pascalova trojúhelníku, po úpravě vyjde vztah N = 2n - (n + 1).
  5. Pro výpočet tohoto vztahu však nelze využít běžná celá čísla, protože velikost výsledku snadno přesáhne 64 bitů. Je proto potřeba využít počítání s velkými celými čísly, což lze zařídit ručně (např. pomocí pole bytů), nebo s využitím knihovních prostředků jazyka (např. v Javě třída BigInteger).

Příklad zdrojového kódu:

import java.math.BigInteger; import java.util.Scanner; public class Main { static Scanner sc = new Scanner(System.in); public static void main(String[] args){ int a = sc.nextInt(), b = sc.nextInt(), c = sc.nextInt(), d = sc.nextInt(); int cc = (a+1)*(b+1)*(c+1)*(d+1)-1; BigInteger bb = new BigInteger(Integer.toString(cc)); BigInteger one = new BigInteger("1"); BigInteger two = new BigInteger("2"); System.out.println((two.pow(cc).subtract(one).subtract(bb)).toString()); } }

Netradiční výzva

  1. Načíst si počet stanovišť a souřadnice jednotlivých stanovišť a seřadit si stanoviště podle souřadnice x od západu na východ.
  2. Rozdělit si okružní trasu na dvě části - západní cestu a východní cestu. Řešit pomocí dynamického programování.
  3. Stanoviště zpracovávat v pořadí jeden za druhým.
  4. Uvažovat tři parametry:
    1. i - hraniční bod východní cesty i .. n - 1,
    2. j - hraniční bod západní cesty n - 1 .. j,
    3. k - další bod v pořadí zpracování bodů.
  5. Parametr k lze určit z parametrů i a j jako max(i, j) + 1.
  6. Mezivýsledky pro i a j ukládat do tabulky DélkaTrasy[i, j] následovně:
    • pro k = n - 1: DélkaTrasy[i, j] = vzdálenostBodů(i, k) + vzdálenostBodů(k, j),
    • jinak: DélkaTrasy[i, j] = min(DélkaTrasy[k, j] + vzdálenostBodů(i, k), DélkaTrasy[i, k] + vzdálenostBodů(k, j)).
  7. Po vyplnění tabulky bude řešení úlohy v DélkaTrasy[0, 0].

Příklad zdrojového kódu:

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

Ohmova záchranná mise

  1. Načíst si počet testovacích případů (bomb) a pro každou bombu požadovaný výsledný odpor a hodnoty jednotlivých odporů. Protože počet jednotlivých odporů není zadán, je vhodné načíst celou řádku a z ní následně dělením podle mezery získat hodnoty jednotlivých odporů.
  2. Pro každou bombu lze použít řešení hrubou silou - vyzkoušet všechny trojice odporů R1, R2 a R3 s výjimkou nulových odporů, které mohou být na vstupu.
  3. Pro výpočet celkového odporu použít celá čísla, aby nedocházelo k zaokrouhlovacím chybám - rovnici lze přespat na R1 * R2 * R3 = R * (R2 * R3 + R1 * R3 + R1 * R2). Pozor, že pro tento výpočet nemusí stačit 32bitové celé číslo.
  4. U každé trojice vyhovující rovnici výše zjistit součet jejích odporů. Pokud je menší než dosud nalezené minimum, tuto trojici si uložit.
  5. Jako výsledek vypsat nalezenou trojici s minimálním součtem odporů. Při vhodném generování trojic bude trojice seřazená vzestupně, protože jednotlivé vstupní odpory jsou seřazené. Pokud žádná vyhovující trojice nebyla nalezena, vypsat výzvu k útěku.

Příklad zdrojového kódu:

#include <bits/stdc++.h> using namespace std; int main(){ int b; cin >> b; while(b--){ int r; cin >> r; cin.ignore(256, '\n'); string s; getline(cin, s); istringstream iss(s); set<int> xs; int x; while(iss >> x){ if(x > r) xs.insert(x); } int l = xs.size(); vector<int> res; int sum = 10000; for(auto it = xs.begin(); it != xs.end(); ++it){ for(auto itt = it; itt != xs.end(); ++itt){ int a = *it, b = *itt; int cc = a*b - r*(a+b); if(cc != 0 && (r*a*b) % cc == 0){ int c = (r*a*b)/cc; if(a+b+c < sum && xs.count(c)){ res = {a,b,c}; sum = a+b+c; } } } } if(!res.size()){ cout << "Vezmi nohy na ramena!\n"; } else{ sort(res.begin(), res.end()); cout << res[0] << " " << res[1] << " " << res[2] << "\n"; } } }

Sociální bublina

  1. Načíst si počet nových přátelství a načítat jednotlivá přátelství. Pro označená přátelství vypsat počet lidí v sociální bublině (komponentě).
  2. Pro řešení úlohy lze využít disjoint set (union - find) datovou strukturu:
    • operace union(a, b) - spojí množiny, do kterých patří a a b,
    • operace find(a) - vrátí prvek reprezentující množinu, do které patří prvek a, přičemž reprezentant množiny je stejný pro všechny prvky množiny.
  3. Dané operace je možné realizovat pomocí stromové struktury pro všechny prvky dané množiny, přičemž v kořeni stromu je třeba udržovat počet uzlů stromu (tj. velikost sociální bubliny):
    • operace union je připojení kořene jednoho stromu pod druhý,
    • operace find je průchod stromem od daného uzlu ke kořeni, přičemž při této operaci je vhodné provádět kompresi cest (přepojení uzlů navštívených na cestě přímo pod kořen).
  4. Pro každé označené přátelství vypsat hodnotu v kořeni stromu, ve kterém se oba lidé nacházejí.

Příklad zdrojového kódu:

#include <bits/stdc++.h> using namespace std; struct DFU{ map<string, string> p; map<string, int> sz; void create(string x){ if(p.find(x) == p.end()){ p[x] = x; sz[x] = 1; } } string getParent(string x){ if(p[x] == x) return x; return p[x] = getParent(p[x]); } int getSize(string x){ return sz[getParent(x)]; } void join(string a, string b){ string x = getParent(a), y = getParent(b); if(x == y) return; if(sz[x] > sz[y]){ p[y] = x; sz[x] += sz[y]; } else{ p[x] = y; sz[y] += sz[x]; } } }; int main(){ int p; cin >> p; cin.ignore(100, '\n'); DFU dfu; while(p--){ string s; getline(cin, s); istringstream iss(s); string a, b; iss >> a >> b; dfu.create(a); dfu.create(b); dfu.join(a, b); if(!iss.eof()){ string rest; iss >> rest; if(rest == "*"){ cout << dfu.getSize(a) << "\n"; } } } }