PilsProg 2020

Výsledky Lite

#JménoPříjmeníSplněných úlohČas
1MichalKodad9666,148
2Vojtěch Šebek5264,098
3JakubKloub3170,371
4FilipDigrín3289,128
5VojtěchHořánek126,316
6OndřejHlavinka1102,150
7TomášZouval1127,011

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

Výsledky kvalifikace

#JménoPříjmeníSplněných úlohČasFinále
1JiříKalvoda68,761Postupuje do finále
2MichalKodad637,546Postupuje do finále
3KristýnaPetrlíková650,765Postupuje do finále
4OndřejSladký6126,892Postupuje do finále
5AdamBlažek6262,783Postupuje do finále
6JakubMarek62 550,836Postupuje do finále
7JanKaifer65 340,241Postupuje do finále
8VáclavJanáček52 338,986Postupuje do finále
9TomášMüller54 296,038Postupuje do finále
10JakubJankovec55 905,713Postupuje do finále
11DominikFarhan425,965Postupuje do finále
12JosefMiegl4766,881Postupuje do finále
13JakubKloub4870,469Postupuje do finále
14OndřejBaštař41 683,485Postupuje do finále
15OndřejKovář358,668-
16RichardBleier3126,347-
17JiříRichter3155,892-
18VojtěchHořánek3223,377-
19MartinKopecký3655,320-
20DominikHrdý3676,081-
21MichalBřečka3728,099-
22Vojtěch Šebek3769,682-
23Štěpán Pressl33 075,716-
24VojtěchHolý33 141,139-
25MarikaKosohorská33 249,811-
26RobertOnder33 338,675-
27JosefHřebec33 485,733-
28ViktorieValdmanová33 907,519-
29Jan Kadlec2213,937-
30VítVohralík2584,074-
31OndřejNováček21 488,255-
32PavelBařtipán1654,047-
33JakubKislinger11 009,656-
34JakubHolý11 009,818-
35RadekIdlbek11 009,829-
36VojtěchAdamec11 129,254-
37NicolasKohout11 145,885-
38NejsemStudent67 409,781-

Výsledky finále

#JménoPříjmeníSplněných úlohČas
1JiříKalvoda33,784
2AdamBlažek22,213
3OndřejSladký22,245
4MichalKodad23,401
5JakubJankovec13,630
6VáclavJanáček15,457
7JosefMiegl00,000
8JakubMarek00,000
9OndřejBaštař00,000
10JanKaifer00,000
11TomášMüller00,000
12JakubKloub00,000
13DominikFarhan00,167
14KristýnaPetrlíková01,000

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

Ilustrační úlohy

NázevČísloÚspěšných řešitelů
AxB170119
AplusB17028
Největší ze tří celých čísel17037
Pascalův trojúhelník17045

Lite1 úlohy

NázevČísloÚspěšných řešitelů
Hvězdičky20116
Nad diagonálou20122
Vyhledávání čísel20132

Lite2 úlohy

NázevČísloÚspěšných řešitelů
Pravoúhlý trojúhelník20143
Prvočíslo20153
Součet matic20162

Lite3 úlohy

NázevČísloÚspěšných řešitelů
Největší společný dělitel20172
Sestupné řazení20182
Statistika písmen20191

Kvalifikační úlohy

NázevČísloÚspěšných řešitelů
Caesarova šifra202137
Kódované výsledky202233
Kruh ochrany202310
Mazaní studenti20249
Mocniny dvojky202528
Movo202616

Finálové úlohy

NázevČísloÚspěšných řešitelů
Pivní tácky20311
Poslední svého druhu20320
Projetí kolony20335
Utrpení mladého Jürlechena20340
Výlov rybníka20355

A jaké bylo finále?

Finále začíná ...

Harmonogram PilsProg 2020

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.

Hvězdičky

  1. Pro každé hodnocení si načíst procenta.
  2. Určit počet hvězdiček, např. vzorcem počet = 1 + procenta / 20 (dělení je celočíselné).
  3. V cyklu (ideálně for) vypsat spočtený počet hvězdiček (každou hvězdičku bez odřádkování).
  4. Po vyspání příslušného počtu hvězdiček odřádkovat.

Příklad zdrojového kódu:

#include <stdio.h> #include <stdlib.h> void printStars(const char n) { for (int i = 0; i <= n; i += 20) { putchar('*'); } putchar('\n'); } void getline(char **lineptr, size_t *n, FILE *stream) { if (!(*lineptr)) { return; } char c; unsigned int pos = 0; while ((c = getc(stream)) != '\n') { (*lineptr)[pos++] = c; } (*lineptr)[pos] = '\0'; } int main(int argc, char **argv) { size_t bufferSize = sizeof(char) * 4; char *buffer = malloc(bufferSize); if (!buffer) { return 1; } unsigned char lines; getline(&buffer, &bufferSize, stdin); lines = atoi(buffer); for (int i = 0; i < lines; i++) { getline(&buffer, &bufferSize, stdin); printStars(atoi(buffer)); } free(buffer); return 0; }

Nad diagonálou

  1. Pro zadaný řád matice (n) načíst jednotlivé řádky matice po jednotlivých číslech a uložit je do dvourozměrného pole.
  2. Připravit si proměnnou pro součet prvků a použít dva vnořené cykly for pro procházení matice. Vnější cyklus určuje aktuální řádku matice. Vnitřní cyklus for určuje aktuální prvek na řádce (tj. sloupec).
  3. Vnější cyklus se opakuje v intervalu <0; n).
  4. Vnitřní cyklus se opakuje podle aktuální řádky - pro řádku 0 n-krát, pro řádku 1 (n - 1)-krát, atd.
  5. V každé obrátce vnitřního cyklu se aktuální prvek přičte do celkového součtu.
  6. Vypsat součet.

Příklad zdrojového kódu:

#include <iostream> using namespace std; int main() { unsigned int inputCount; cin >> inputCount; int sum = 0; bool b = false; for (int row = 0; row < inputCount; row++) { for (int i = 0; i < inputCount; i++) { int input; cin >> input; if (i == row) { b = true; } if (b) { sum += input; } } b = false; } cout << sum << endl; return 0; }

Vyhledávání čísel

  1. Pro každý testovací případ načíst hledané číslo a počet prvků posloupnosti. Následně v cyklu (ideálně for) načíst jednotlivé prvky posloupnosti a uložit je do pole.
  2. Projít pole v cyklu (ideálně for) od začátku a porovnávat aktuální prvek s hledaným číslem.
  3. Pokud je aktuální prvek roven hledanému číslu, vypsat aktuální prvek a cyklus předčasně ukončit.
  4. Pokud se prošlo celé pole, ale žádný prvek neodpovídal hledanému číslu, vypsat „Nenalezeno.“.

Příklad zdrojového kódu:

#include <bits/stdc++.h> using namespace std; void solve(){ int find, n; cin >> find >> n; int indexNumber = -1; for(int i = 0; i < n; i++){ int el; cin >> el; if(find == el && indexNumber == -1) indexNumber = i; } if(indexNumber != -1) cout << indexNumber << "\n"; else cout << "Nenalezeno.\n"; } int main(){ int t; cin >> t; for(int i = 0; i < t; i++){ solve(); } }

Pravoúhlý trojúhelník

  1. Zadanou délku odvěsny použít jako hranici pro dva vnořené cykly for jdoucí od 0.
  2. Vnější cyklus udává řádku trojúhelníku, vnitřní cyklus udává sloupec trojúhelníku.
  3. Ve vnitřním cyklu zjišťovat, zda je index aktuálního sloupce menší než rozdíl (délka odvěsny - index aktuální řádky). Pokud ano, vypsat bez odřádkování „.“, jinak „*“.
  4. Po skončení vnitřního cyklu vždy odřádkovat.

Příklad zdrojového kódu:

/** * Simple java template */ import java.util.Scanner; public class trojuhelnikfinal { static Scanner sc = new Scanner(System.in); static int nactiCislo() { int i = sc.nextInt(); return i; } public static void main(String[] args) { int n = nactiCislo(); int x = n; int reset = n; int pocethvezd = 1; String vysledek = ""; while (x > 0) { n = reset; while (n > pocethvezd) { vysledek = vysledek + "."; n--; } while (n > 1) { vysledek = vysledek + "*"; n--; } vysledek = vysledek + "*\n"; pocethvezd++; x--; } System.out.println(vysledek); } }

Prvočíslo

  1. Pro každý testovací případ načíst číslo.
  2. Připravit si proměnnou sloužící jako čítač nalezených dělitelů inicializovanou na 0.
  3. V cyklu for opakujícím se v intervalu <1; číslo> zkoušet pomocí operátoru pro zbytek po celočíselném dělení, zda je číslo dělitelné aktuálním indexem.
  4. Pokud ano, inkremetovat čítač.
  5. Po skončení cyklu rozhodnout, zda je číslo prvočíslo podle počtu nalezených dělitelů. Pokud je počet dělitelů roven 2, je číslo prvočíslo, jinak ne.
  6. Pokud je číslo prvočíslo, vypsat „Je prvocislo.“, jinak vypsat „Neni prvocislo.“.

Příklad zdrojového kódu:

#include <stdio.h> #include <stdlib.h> _Bool Je_prvocislo(int cislo) { if (cislo == 1) return 0; else if (cislo == 2) return 1; _Bool a = 0; if (cislo & 1) { for (int i = 2; i < cislo; i++) if (cislo % i == 0) return 0; return 1; } else return 0; } int main(void) { int pocet_cisel; scanf("%i", &pocet_cisel); if (pocet_cisel < 1 || pocet_cisel > 100) return -1; int *cisla = (int *)malloc(pocet_cisel * sizeof(int)); for (int i = 0; i < pocet_cisel; i++) { scanf("%i", &cisla[i]); if (cisla[i] > 1000) { free(cisla); return -1; } } for (int i = 0; i < pocet_cisel; i++) { if (Je_prvocislo(cisla[i])) printf("Je prvocislo.\n"); else printf("Neni prvocislo.\n"); } free(cisla); return 0; }

Součet matic

  1. Pro zadaný počet řádek a sloupců matic vytvořit tři dvourozměrná pole o odpovídajích rozměrech.
  2. Načíst prvky první matice do prvního pole a následně prvky druhé matice do druhého pole. Načtení každé matice realizovat pomocí dvou vnořených cyklů for, kdy vnější cyklus udává řádku matice a vnitřní sloupec matice.
  3. Pomocí dvou vnořených cyklů se stejnou hlavičkou jako pro načítání jednotlivých vstupních matic procházet jednotlivé prvky obou vstupních polí najednou, sčítat odpovídající prvky a ukládat je do třetího pole.
  4. Pomocí dvou vnořených cyklů se stejnou hlavičkou jako pro načítání jednotlivých vstupních matic vypsat třetí pole obsahující součet matic. Jednotlivé prvky pole vypisovat bez odřádkování. Za každým prvkem kromě posledního navíc vypsat mezeru. Za každou řádkou (tj. po skončení vnitřního cyklu) odřádkovat.

Příklad zdrojového kódu:

#include <stdio.h> #include <string.h> #include <stdlib.h> int main(void) { int y, x; scanf("%i%i", &y, &x); getc(stdin); if (y < 1 || y > 20 || x < 1 || x > 20) return -1; int **matice1 = (int **)malloc(y * sizeof(int *)); for (int i = 0; i < y; i++) matice1[i] = (int *)malloc(x * sizeof(int)); for (int i = 0; i < y; i++) for (int j = 0; j < x; j++) matice1[i][j] = 0; for (int m = 0; m < 2; m++) { for (int i = 0; i < y; i++) { char *str; scanf("%m[^\n]", &str); getc(stdin); char *p = strtok(str, " "); for (int j = 0; p; j++) { int number = atoi(p); if (number <= -100 || number >= 100) matice1[i][j] = 0; else matice1[i][j] += number; p = strtok(NULL, " "); } free(str); } } for (int i = 0; i < y; i++) { for (int j = 0; j < x; j++) printf("%i ", matice1[i][j]); printf("\n"); } for (int i = 0; i < y; i++) free(matice1[i]); free(matice1); return 0; }

Největší společný dělitel

  1. Pro každý testovací případ načíst dvě čísla.
  2. Určit minimum z těchto načtených čísel.
  3. Připravit si proměnnou pro největšího společného dělitele a inicializovat ji na 1.
  4. V cyklu for opakujícím se v intervalu <minimum; 2> zjišťovat, zda jsou obě čísla dělitelná aktuálním indexem. Pokud ano, přiřadit aktuální index do proměnné pro největšího společného dělitele a cyklus předčasně ukončit.
  5. Po skončení cyklu vypsat hodnotu proměnné pro největšího společného dělitele.

Příklad zdrojového kódu:

#include <bits/stdc++.h> using namespace std; int main() { int t; cin >> t; for(int i = 0; i < t; i++){ int a, b; cin >> a >> b; if(a < b) swap(a, b); while(b != 0){ a = a%b; swap(a, b); } cout << abs(a) << endl; } return 0; }

Sestupné řazení

  1. Pro zadaný počet prvků řady vytvořit pole o odpovídajícím rozměru a načíst jednotlivé prvky řady v cyklu for.
  2. Pro řazení lze použíj jeden mnoha existujících algoritmů, přičemž je potřeba dát pozor na směr řazení (sestupně, tedy od největšího k nejmenšímu).
  3. Jeden z nejjednodušších algoritmů řazení na implementaci je řazení výběrem, který postupně hledá a zařazuje na správné místo největší prvek, pak druhý největší atd.:
    • Použít dva vnořené cykly for.
    • Vnejší se opakuje v intervalu <0; počet prvků - 1) a udává, který prvek se hledá.
    • Vnitřní se opakuje v intervalu <aktuální index vnějšího + 1; počet prvků) a vyhledává v tomto intervalu index největšího prvku. Nalezený index největšího prvku se uloží do proměnné
    • Po skončení vnitřního cyklu se prohodí prvek na indexu vnějšího cyklu s prvkem na právě nalezeném indexu největšího prvku.
  4. Vypsat seřazené pole pomocí cyklu for. Jednotlivé prvky vypisovat bez odřádkování, ale navíc s čárkou a mezerou, kromě posledního prvku.
  5. Po vypsání prvků řady odřádkovat.

Příklad zdrojového kódu:

/** * Simple java template */ import java.util.Scanner; import java.util.Arrays; import java.util.Collections; public class sestupne { static Scanner sc = new Scanner (System.in); static int nactiCislo() { int i = sc.nextInt(); return i; } public static void main(String[] args) { int pocet = nactiCislo(); int i = 0; Integer[] cisla = new Integer [pocet]; while (i < pocet) { cisla[i] = nactiCislo(); i++; } Arrays.sort(cisla, Collections.reverseOrder()); System.out.println(Arrays.toString(cisla).replace("[", "").replace("]", "")); } }

Statistika písmen

  1. Vytvořit si pole celých čísel udávající četnosti jednotlivých znaků o velikosti 27 („z“ - „a“ + 2, tj. pro 26 písmen anglické abecedy a ostatní) a prvky pole inicializovat na 0.
  2. Pro zadaný počet řádek textu načítat postupně jednotlivé řádky do řetězce.
  3. Každou načtenou řádku procházet od začátku do konce znak po znaku.
  4. Pro každý znak určit, zda se jeho hodnota nachází mezi znaky „a“ až „z“ nebo „A“ až „Z“.
  5. Pokud ano, inkrementovat četnost odpovídající zkoumanému znaku v poli četností jednotlivých znaků. Pokud ne, inkrementovat četnost ostatních v poli četností jednotlivých znaků.
  6. Po zpracování všech řádek projít pole četností jednotlivých znaků v cyklu for.
  7. Pokud je aktuální četnost větší než 0, vypsat odpovídající malé písmeno, mezeru, četnost a odřádkovat.

Příklad zdrojového kódu:

#include <bits/stdc++.h> using namespace std; int main() { int n; cin >> n; vector<int> vyskyty(27, 0); string text; getline(cin, text); for(int i = 0; i < n; i++){ getline(cin, text); for(char z : text){ if(z >= 97) vyskyty[z - 'a']++; else if(z >= 65) vyskyty[z - 'A']++; else{ vyskyty[26]++; //cout << z << endl; } } } for(int i = 0; i < 27; i++){ string text; if(i != 26) text = ('a' + i); else text = "ostatni"; if(vyskyty[i] != 0) cout << text << " " << vyskyty[i] << endl; } 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.

Caesarova šifra

  1. Načíst a uložit zprávu (např. jako řetězec), směr posunu a počet míst posunu šifry.
  2. Procházet zprávu znak po znaku.
  3. Pokud se jedná o velké písmeno nebo o malé písmeno anglické abecedy, přičíst nebo odečíst ke kódu znaku počet míst posunu podle směru posunu.
  4. Pokud vyjde záporné číslo, přičíst počet znaků anglické abecedy (tedy 26). Na výsledku provést operaci zbytek po dělení (tj. modulo) počtem znaků anglické abecedy.
  5. Výsledné číslo po operaci modulo převést na znak a vypsat ho.
  6. Pokud se nejedná o velké či malé písmeno anglické abecedy, znak pouze vypsat.

Příklad zdrojového kódu:

program caesarovacifra; {$mode objfpc}{$H+} uses {$IFDEF UNIX}{$IFDEF UseCThreads} cthreads, {$ENDIF}{$ENDIF} Classes { you can add units after this }; var s, st: string; p, i: integer; begin readln(s); readln(st); readln(p); for i:= 1 to length(s) do begin if (ord(s[i])>=65) and (ord(s[i])<=90) then begin if st = 'vlevo' then begin ord(s[i]):= ord(s[i]) - p; if (ord(s[i])<65) then ord(s[i]):= ord(s[i]) + 26 end else begin ord(s[i]):= ord(s[i]) + p; if (ord(s[i])>90) then ord(s[i]):= ord(s[i]) - 26 end; end; if(ord(s[i])>=97) and (ord(s[i])<=122) then begin if st = 'vlevo' then begin ord(s[i]):= ord(s[i]) - p; if (ord(s[i])<97) then ord(s[i]):= ord(s[i]) + 26 end else begin ord(s[i]):= ord(s[i]) + p; if (ord(s[i])>122) then ord(s[i]):= ord(s[i]) - 26 end; end; write(s[i]); end; readln end.

Kódované výsledky

  1. Pro každý kódovaný výsledek načíst 8 znaků, každý na samostatné řádce. Znaky si ukládat do pole čísel, pro „|“ uložit 1, pro „-“ uložit 0.
  2. Proměnnou pro výsledek inicializovat na 0.
  3. Procházet pole od zadu a do výsledku si nasčítávat aktuální řád vynásobený aktuálním prvkem pole.
  4. Vypsat pole znak po znaku bez mezer, znaménko „ = “ a vypočítaný dekadický výsledek.

Příklad zdrojového kódu:

#include <iostream> using namespace std; int main() { char c; int n; cin >> n; while(n--) { int d = 0; string s = "00000000"; for (int i = 0; i < 8; ++i) { cin >> c; if (c == '|') { d |= 1 << (7 - i); s[i] = '1'; } } cout << s << " = " << d << endl; } }

Kruh ochrany

  1. Načíst a uložit si délky jednotlivých magických holí.
  2. Pro určení maximálního možného stupně ochrany je potřeba určit maximální počet vrcholů pravidelného n-úhelníku, který lze z holí poskládat tam, aby žádná hůl nezbyla. To znamená rozdělit magické hole do skupin, přičemž v každé skupině budou mít hole v součtu stejnou délku.
  3. Protože není dopředu určeno, kolik je maximální n, je potřeba postupně vyzkoušet rozdělení holí do skupin od největšího počtu (odpovídá počtu magickcýh holí) po nejmenší počet (odpovídá trojúhelníku). Pokud při tomto zkoušení vyjde, že daný pravidelný n-úleník lze poskládat, skončit a vypsat aktuální n. Pokud nelze vytvořit ani trojúhelník, vypsat 0.
  4. Pro určení, zda lze pro zadané n a zadané hole poskládat pravidelný n-úhelník, použít dynamické programování. Pro indikaci, zda je magická hůl v dané skupině, je vhodné použít 32bitový celočíselný typ a bitové operace (holí je maximálně 20).

Příklad zdrojového kódu:

package comp1; import java.util.ArrayList; import java.util.Collections; import java.util.Scanner; public class Circle { public static void main(String arg[]) { new Circle(); } static Scanner scan = new Scanner(System.in); ArrayList<Integer> lengths; public Circle() { int n = Integer.parseInt(scan.nextLine()); lengths = new ArrayList<>(); for( int i= 0; i< n; i++ ) lengths.add(scan.nextInt()); // sort the list from biggest to smallest sort(); // sum divided by biggest length = max level -> try to divide it by numbers between biggest length and sum until it arrives at a whole number -> if this number is bigger than 3 => win... :) int sum = 0; int max = lengths.get(0); for( int length : lengths ) sum += length; //System.out.println( sum+" "+max); int level = 0; for( int i= max; i < sum; i++ ) { if( sum % i == 0 ) if(tryToMakeAChainPrettyPlease( i, i ) == i) { level = sum/i; break; } } if(level >= 3) System.out.println(level); else System.out.println(0); } public void sort() { Collections.sort(lengths, Collections.reverseOrder()); } boolean running = true; public int tryToMakeAChainPrettyPlease( int base, int now ) { //System.out.println("Looking for: "+base+" "+now); if( lengths.size() == 0 ) return base; if( now == base ) { int biggest = lengths.get(0); int find = base-biggest; //System.out.println("big: "+biggest); if( find == 0 ) { lengths.remove( new Integer(now) ); if( tryToMakeAChainPrettyPlease(base, base) < 0 ) { lengths.add(now); sort(); } } else { lengths.remove( new Integer(biggest) ); if( tryToMakeAChainPrettyPlease(base, find) < 0 ) { lengths.add(biggest); sort(); } } } else { for( int i= now; i> 0; i-- ) { //System.out.println( base +" <- "+now+": "+i); if( lengths.contains(i) ) { lengths.remove( new Integer(i) ); if( i == now ) { if( tryToMakeAChainPrettyPlease(base, base) < 0 ) { lengths.add(i); sort(); } } else if( tryToMakeAChainPrettyPlease(base, now-i) < 0) { lengths.add(i); sort(); } } } } if( lengths.size() == 0 ) return base; else return -1; } }

Mazaní studenti

  1. Načíst a uložit si celou mapu jako dvourozměrné pole znaků a maximální počet kol. Zvlášť si zaznamenat počáteční a cílovou polohu studenta a počáteční pozice a směry učitelů, aby nebylo nutné je pokaždé vyhledávat v mapě.
  2. Určit počet kol, které student potřebuje k dosažení cílové pozice pomocí simulace.
  3. Počáteční pozici studenta označit jako dosažitelné políčko.
  4. V každém kole pohnout se všemi učiteli a pro všechna políčka na mapě určit, zda jsou volná (tj. nejsou na nich učitelé, nemíří na ně učitelé ze sousedních políček a nejedná se o stěny) a zároveň dosažitelná (tj. lze se na ně dostat z dosažitelných políček z předchozího kola).
  5. V každém kole následně ověřit, zda je cílová pozice studenta dosažitelné políčko. Pokud ano, ukončit simulaci a vypsat číslo aktuálního kola.
  6. Pokud aktuální počet kol simulace přesáhne maximální počet kol, simulaci ukončit a vypsat -1.

Příklad zdrojového kódu:

#include <bits/stdc++.h> using namespace std; int pohyby[4][2] = {{1, 0}, {0, -1}, {-1, 0}, {0, 1}}; int pohybyHrac[5][2] = {{1, 0}, {0, -1}, {-1, 0}, {0, 1}, {0, 0}}; char zpet[4] = {'>', '^', '<', 'v'}; int pokusy[4] = {0, 1, 3, 2}; int getPohyb(char smer){ if(smer == '>') return 0; else if(smer == '^') return 1; else if(smer == '<') return 2; else return 3; } struct ucitel{ int x, y, pohyb; }; void provedPohyb(vector<vector<char>>& mapa, vector<vector<char>> & mapaNext, ucitel& uc){ int x = uc.x; int y = uc.y; for(int i = 0; i < 4; i++){ int pohyb = (uc.pohyb + pokusy[i])%4; int xx = x + pohyby[pohyb][0]; int yy = y + pohyby[pohyb][1]; if(xx < 0 || xx >= mapa[0].size() || yy < 0 || yy >= mapa.size()) continue; if(mapa[yy][xx] != '#'){ mapaNext[yy][xx] = 'U'; uc.x = xx; uc.y = yy; uc.pohyb = pohyb; return; } } assert(true); } int main(){ int r, s, c; cin >> s >> r >> c; vector<vector<char>> mapa(s, vector<char>(r)); vector<ucitel> ucitele; pair<int, int> cil; for(int y = 0; y < s; y++){ for(int x = 0; x < r; x++){ char el; cin >> el; if(el == '^' || el == 'v' || el == '<' || el == '>'){ ucitele.push_back({x, y, getPohyb(el)}); mapa[y][x] = 'U'; } else if(el == 'c'){ cil = {x, y}; mapa[y][x] = ' '; }else mapa[y][x] = el; } } /*for(int y = 0; y < s; y++){ for(int x = 0; x < r; x++){ cout << mapa[y][x]; } cout << endl; } cout << "----------------" << endl;*/ for(int i = 0; i < c; i++){ vector<vector<vector<bool>>> smerUc(s, vector<vector<bool>>(r, vector<bool>(4, false))); vector<vector<char>> mapaNext(s, vector<char>(r, ' ')); for(int i = 0; i < ucitele.size(); i++){ ucitel& uc = ucitele[i]; int minX = uc.x; int minY = uc.y; provedPohyb(mapa, mapaNext, uc); smerUc[minY][minX][uc.pohyb] = true; } for(int y = 0; y < s; y++){ for(int x = 0; x < r; x++){ if(mapa[y][x] == '#'){ mapaNext[y][x] = '#'; continue; }else if(mapaNext[y][x] == 'U') continue; for(int j = 0; j < 5; j++){ int xx = x + pohybyHrac[j][0]; int yy = y + pohybyHrac[j][1]; if(xx < 0 || xx >= mapa[0].size() || yy < 0 || yy >= mapa.size()) continue; if(mapa[yy][xx] == 's'){ if(j != 4 && smerUc[y][x][j]) continue; else mapaNext[y][x] = 's'; } } } } /*for(int y = 0; y < s; y++){ for(int x = 0; x < r; x++){ cout << mapaNext[y][x]; } cout << endl; } cout << "------" << endl;*/ if(mapaNext[cil.second][cil.first] == 's'){ cout << i+1 << "\n"; return 0; } mapa = mapaNext; } cout << "-1\n"; }

Mocniny dvojky

  1. Pro každý testovací případ načíst vstupní celé číslo. Uložit si jeho absolutní hodnotu a znaménko.
  2. V cyklu si vypočítat nejnižší mocninu čísla 2 vyšší než absolutní hodnota vstupního čísla.
  3. Podle rozdílu této mocniny čísla 2 a absolutní hodnoty vstupního čísla a rozdílu o 1 nižší mocniny čísla 2 a absolutní hodnoty vstupního čísla určit bližší mocninu čísla 2.
  4. Pokud je vzdálenost obou mocnin čísla 2 od absolutní hodnoty vstupního čísla stejná, vybrat větší mocninu v závislosti na znaménku vstupního čísla.
  5. Vybranou mocninu čísla 2 vynásobit znaménkem a vypsat.

Příklad zdrojového kódu:

#include <iostream> #include <cmath> using namespace std; int main(){ int N; cin >> N; while(N){ int pos = N < 0 ? -1 : 1; int p = log2(abs(N)); int left = pos * (1 << p), right = pos * (1 << (p + 1)); if(abs(N) - abs(left) < abs(right) - abs(N)){ cout << left << "\n"; } else if(abs(N) - abs(left) > abs(right) - abs(N)){ cout << right << "\n"; } else { cout << (left > right ? left : right) << "\n"; } cin >> N; } }

Movo

  1. Načíst a uložit si souřadnice a směry všech značek. Každou značku si uložit jako jeden objekt/záznam.
  2. Rozdělit značky do skupin podle shodnosti jedné ze souřadnic.
  3. V každé skupině značky seřadit podle neshodné souřadnice a pospojovat je mezi sebou podle jejich směrů, čímž vznikne orientovaný graf.
  4. Projít graf z první značky až do poslední dosažitelné značky.
  5. Při novém navštívení již navštívené značky vypsat „Cyklus“ a skončit. Pokud tato situace nenastane, vypsat souřadnice poslední navštívené značky.

Příklad zdrojového kódu:

#include <stdio.h> #include <stdlib.h> enum directions {up, down, left, right}; struct znacka { int y, x; enum directions d; _Bool ch; }; int pocet, my = 0, mx = 0; struct znacka *z; struct znacka *find_last(void) { int t_x = mx; int t_y = my; struct znacka *next = z, *cur; next->ch = 1; for (int i = 0; i < pocet; i++) { cur = NULL; switch (next->d) { case up: t_y = my; for (int j = 0; j < pocet; j++) { if (z[j].x == next->x && z[j].y <= t_y && z[j].y > next->y) { cur = z + j; t_y = z[j].y; } } break; case down: t_y = 0; for (int j = 0; j < pocet; j++) { if (z[j].x == next->x && z[j].y < next->y && z[j].y >= t_y) { cur = z + j; t_y = z[j].y; } } break; case left: t_x = 0; for (int j = 0; j < pocet; j++) { if (z[j].y == next->y && z[j].x < next->x && z[j].x >= t_x) { cur = z + j; t_x = z[j].x; } } break; case right: t_x = mx; for (int j = 0; j < pocet; j++) { if (z[j].y == next->y && z[j].x > next->x && z[j].x <= t_x) { cur = z + j; t_x = z[j].x; } } break; } if (cur == NULL) break; next = cur; if (next->ch == 0) next->ch = 1; else return NULL; } return next; } void main(void) { scanf("%i", &pocet); z = malloc(pocet * sizeof(struct znacka)); for (int i = 0, a, b; i < pocet; i++) { scanf(" %i %i %i %i", &z[i].x, &z[i].y, &a, &b); if (a == -1) z[i].d = left; else if (a == 1) z[i].d = right; else if (b == -1) z[i].d = down; else if (b == 1) z[i].d = up; z[i].ch = 0; if (z[i].y > my) my = z[i].y; if (z[i].x > mx) mx = z[i].x; } struct znacka *last = find_last(); if (last != NULL) printf("%i %i\n", last->x, last->y); else printf("Cyklus\n"); free(z); }

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.

Pivní tácky

  1. Načíst obrázek po řádkách a uložit si ho do dvourozměrného pole znaků (jeden bod představuje jeden pixel) - načítání ukončit, jakmile je načtena prázdná řádka.
  2. Vytvořit si dvourozměrné pole celých čísel pro uložení příslušnosti pixelu do tácku.
  3. Projít obrázek pixel po pixelu a, pokud se jedná o pixel tácku a zatím do žádného tácku nepatří, provést proledávání do šířky a najít všechny body tohoto tácku.
  4. Při prohledávání si počítat průměrnou souřadnici x a průměrnou souřadnici y, čímž se získá střed tácku. Dále si uložit všechny krajní body tácku (ty, které sousedí s pozadím nebo s hranicí obrázku.
  5. Po nalezení všech bodů tácku spočítat vzdálenosti všech krajních bodů a středu a najít maximum a minimum.
  6. Podle podílu maxima a minima určit, zda je to kruh (hodnota blízká 1) či čtverec (hodnota blízká odmocnině ze 2). Inkrementovat počet čtverců nebo kruhů.
  7. Vypsat počet nalezených čtverců a kruhů v předepsaném formátu.

Příklad zdrojového kódu:

#include<bits/stdc++.h> using namespace std; #ifdef DEB #define D if(0) #else #define D if(0) #endif using ll = long long; using ld = long double; const int MAX = 1123; char in [MAX][MAX]; pair<int,int> z[MAX*MAX*8]; int zlen; int main() { int kruh=0,ctverec=0; for(int i=1;;i++) { if(1!=scanf("%s",in[i]+1)) break; } for(int i=0;i<MAX;i++) for(int j=0;j<MAX;j++) { z[0]=make_pair(i,j); zlen=1; int size = 0; int xmin=1000000; int ymin=1000000; int xmax=-1000000; int ymax=-1000000; while(zlen) { auto act = z[--zlen]; int x = act.first; int y = act.second; if(in[x][y]=='#') { size++; xmin=min(xmin,x); ymin=min(ymin,y); xmax=max(xmax,x); ymax=max(ymax,y); in[x][y]='1'; z[zlen++]=make_pair(x+1,y+1); z[zlen++]=make_pair(x+1,y); z[zlen++]=make_pair(x+1,y-1); z[zlen++]=make_pair(x,y+1); z[zlen++]=make_pair(x,y-1); z[zlen++]=make_pair(x-1,y+1); z[zlen++]=make_pair(x-1,y); z[zlen++]=make_pair(x-1,y-1); } } if(size) { ll r=0; z[0]=make_pair(i,j); zlen=1; int sx = (xmin+xmax)/2; int sy = (ymin+ymax)/2; D printf("%d %d\n",sx,sy); while(zlen) { auto act = z[--zlen]; int x = act.first; int y = act.second; if(in[x][y]=='1') { r=max(r,ll(x-sx)*ll(x-sx)+ll(y-sy)*ll(y-sy)); in[x][y]='2'; z[zlen++]=make_pair(x+1,y+1); z[zlen++]=make_pair(x+1,y); z[zlen++]=make_pair(x+1,y-1); z[zlen++]=make_pair(x,y+1); z[zlen++]=make_pair(x,y-1); z[zlen++]=make_pair(x-1,y+1); z[zlen++]=make_pair(x-1,y); z[zlen++]=make_pair(x-1,y-1); } } ld pomer = size/ld(r); if(pomer > 2.9) kruh++; else ctverec++; D printf("R^2 %lld, size %d| %Lf\n",r,size,pomer); } } printf("Ctverce: %d Kruhy: %d\n",ctverec,kruh); return 0; }

Poslední svého druhu

  1. Načíst si souřadnice všech senzorů a uložit si je.
  2. Situaci na každém senzoru si lze představit tak, že opíšeme kružnici se středem v senzoru a poloměrem odpovídajícím času zachycení signálu. Místo průsečíku kružnic je zdroj signálu.
  3. Připravit si soustavu rovnic reprezentující jednotlivé kružnice pro všechny možné trojice senzorů, dosadit za souřadnice senzorů a upravit tak, aby bylo možné dosadit jednotlivé časy (odpovídající poloměrům).
  4. Načítat jednotlivé události (tj. časy ze všech senzorů).
  5. Pro každou událost pomocí upravených soustav rovnic najít všechna řešení - každá trojice dá až 2 řešení.
  6. Ze všech řešení vybrat řešení s nejmenší chybou - pro každý senzor určit přesahy kružnic vzhledem k jejich průsečíku, nejlepší je řešení s nejmenším maximálním přesahem.
  7. Obě složky x a y zaokoruhlit podle standardních pravidel a vypsat je oddělené mezerou.

Příklad zdrojového kódu:

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

Projetí kolony

  1. Načíst si šířku a délku silnice a také mapu silnice po řádkách. Mapu si uložit jako dvourozměrné pole znaků.
  2. Mapu procházet po řádkách. V každé řádce určit počet cest, nejdelší a nejkratší cestu na základě hodnot na předchozí řádce a pouze volných políček.
  3. Počet cest určit jako N[i][j] = N[i - 1][j - 1] + N[i - 1][j] + N[i - 1][j + 1]
  4. Délku nejkratší cesty určit jako K[i][j] = min(K[i - 1][j - 1] + sqrt(2), K[i - 1][j] + 1, K[i - 1][j + 1] + sqrt(2))
  5. Délku nejdelší cesty určit jako D[i][j] = max(D[i - 1][j - 1] + sqrt(2), D[i - 1][j] + 1, D[i - 1][j + 1] + sqrt(2))
  6. Délky cest si uchovávat pomocí koeficientů a a b.
  7. Vypsat počet cest a délky minimální a maximální cesty v požadovaném formátu.

Příklad zdrojového kódu:

#include <bits/stdc++.h> using namespace std; long long a, b; struct sil { long long v; long long kr; long long dl; long long poc; }pole[105][105]; int main() { cin >> b >> a; char t; b++; for(long long i=0; i<a; i++) { for(long long j=1; j<b; j++) { cin >> t; if(t=='O') pole[i][j].v=1; } } for(long long i=1; i<b; i++) {if(pole[0][i].v) pole[0][i].poc=1;} for(long long i=1; i<a; i++) { for(long long j=1; j<b; j++) { if(pole[i][j].v) { pole[i][j].kr=200; pole[i][j].dl=-200; for(int k=-1; k<2; k++) { if(pole[i-1][j+k].poc) { pole[i][j].poc+=pole[i-1][j+k].poc; pole[i][j].kr=min(pole[i][j].kr, pole[i-1][j+k].kr+(k*k)); pole[i][j].dl=max(pole[i][j].dl, pole[i-1][j+k].dl+(k*k)); } } } } } long long mi=200; long long ma=0; long long po=0; for(long long i=1; i<b; i++) { if(pole[a-1][i].poc) { po+=pole[a-1][i].poc; mi=min(mi, pole[a-1][i].kr); ma=max(ma, pole[a-1][i].dl); } } if(po) { cout << "Pocet cest: " << po << " Minimalni: "; if(a-1-mi) cout << a-1-mi; if(mi && a-1-mi) cout << " + "; if(mi) cout << mi << " sqrt(2)"; cout << " Maximalni: "; if(a-1-ma) cout << a-1-ma; if(ma && a-1-ma) cout << " + "; if(ma) cout << ma << " sqrt(2)"; cout << endl; return 0; } cout << "Silnice je neprujezdna" << endl; return 0; }

Utrpení mladého Jürlechena

  1. Pro každá testovací případ si načíst jednotlivá čísla.
  2. Pořadí čísel ve výrazu může být libovolné, musí být ale použita všechna.
  3. Pro určení takového pořadí, aby výsledek byl maximální či minimální, použít dynamické programování.
  4. Nalezené maximum a minimum vypsat v tomto pořadí oddělené mezerou.

Příklad zdrojového kódu:

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

Výlov rybníka

  1. Pro každou rybu načíst její číslo a počet rovnic a následně všechny rovnice (pro každou rovnici levou a pravou hranici intervalu a koeficienty b, a0 a a1).
  2. Pro každou rybu určit její plochu jako součet horních částí mínus součet dolních částí (lze použít určité integrály, ale také je možné počítat obsah pravoúhlého lichoběžníku pod každou úsečkou).
  3. Ryby seřadit vzestupně pomocí efektivního algoritmu řazení (např. Merge sort).
  4. Vypsat jednotlivá čísla seřazených ryb oddělená mezerou.

Příklad zdrojového kódu:

#include <bits/stdc++.h> using namespace std; typedef long double ld; struct rovnice{ int from, to; ld a, b; }; pair<ld, ld> vypBod(rovnice r, int x){ return {x, x*r.a + r.b}; } ld ob(pair<ld, ld> prvni, pair<ld, ld> druhy){ return prvni.first * druhy.second - prvni.second * druhy.first; } bool compare(const rovnice& x, const rovnice& y) { if (x.from < y.from) return true; return false; } int main(){ int n; cin >> n; vector<pair<ld, int>> ryby; for(int i = 0; i < n; i++){ int cislo, r; string s; cin >> s >> s >> cislo >> s >> s >> r; //scanf("Ryba cislo %d pocet rovnic %d", &cislo, &r); ld obsah = 0; vector<rovnice> horni; vector<rovnice> dolni; for(int j = 0; j < r; j++){ char znak; int from, to, a, b, c; char trash; cin >> znak >> trash >> from >> to >> trash >> a >> b >> c; //scanf("%c [%d %d] %d %d %d", &znak, &from, &to, &a, &b, &c); if(znak == 'D') dolni.push_back({from, to, ld(c) / ld(a), ld(b) / ld(a)}); else horni.push_back({from, to, ld(c) / ld(a), ld(b) / ld(a)}); } sort(horni.begin(), horni.end(), compare); sort(dolni.begin(), dolni.end(), compare); obsah += ob(vypBod(horni[0], horni[0].from), vypBod(dolni[0], dolni[0].from)); obsah += ob(vypBod(dolni[dolni.size() - 1], dolni[dolni.size() - 1].to), vypBod(horni[horni.size() - 1], horni[horni.size() - 1].to)); for(int j = 0; j < dolni.size(); j++){ if(j != 0) obsah += ob(vypBod(dolni[j-1], dolni[j-1].to), vypBod(dolni[j], dolni[j].from)); obsah += ob(vypBod(dolni[j], dolni[j].from), vypBod(dolni[j], dolni[j].to)); } for(int j = 0; j < horni.size(); j++){ if(j != 0) obsah += ob(vypBod(horni[j], horni[j].from), vypBod(horni[j-1], horni[j-1].to)); obsah += ob(vypBod(horni[j], horni[j].to), vypBod(horni[j], horni[j].from)); } obsah /= 2; ryby.push_back({obsah, cislo}); } /*for(int i = 0; i < n; i++){ cout << ryby[i].first << " " << ryby[i].second << "\n"; }*/ sort(ryby.begin(), ryby.end()); for(int i = 0; i < n; i++){ if(i != 0) cout << " "; cout << ryby[i].second; } cout << "\n"; }