PilsProg 2015

Výsledky kvalifikace

Splněných úlohPočet soutěžících
69
55
43
23
115

Pozn.: Jména a příjmení soutěžících byla odstraněna, protože pominul účel zpracování osobních údajů.

Výsledky finále

Splněných úlohPočet finalistů
51
41
33
21
11
06

Pozn.: Jména a příjmení finalistů byla odstraněna, protože pominul účel zpracování osobních údajů.

Ilustrační úlohy:

NázevOznačeníÚspěšných řešitelů
AxB070439
Pascalův trojúhelník070327
Největší ze tří celých čísel080634
AplusB080535

Kvalifikační úlohy:

NázevOznačeníÚspěšných řešitelů
Seznam slov151518
Strom151612
Domněnka151134
Palindromy151416
Kódování151220
Nejdelší společná sekvence151312

Finálové úlohy:

NázevOznačeníÚspěšných řešitelů
Dekódování pásky15217
Oslava zápočtu15226
Podíl15232
Topení15242
Trezor15256

A jaké bylo finále?

Finále začíná ...

Harmonogram PilsProg 2015

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.

Domněnka

  1. Načíst přirozené číslo ze vstupu. Pokud je číslo rovno 0, skončit.
  2. Pro každé načtené číslo si vytvořit dvě celočíselné proměnné. Do první přiřadit 1, do druhé načtené číslo zmenšené o 1.
  3. V cyklu první proměnnou inkrementovat, druhou proměnnou dekrementovat, dokud je první proměnná menší než druhá.
  4. V každé obrátce cyklu zkontrolovat, zda obě proměnné obsahují prvočísla (např. pomocí Eratosthenova síta). Pokud ano, cyklus předčasně ukončit.
  5. Vypsat výsledek v požadovaném formátu.
  6. Pokud je cyklus zastaven až v okamžiku, kdy první proměnná obsahuje větší nebo stejné číslo jako druhá proměnná, rozklad na prvočísla neexistuje.

Příklad zdrojového kódu:

#include <stdio.h> #include <stdlib.h> #include <math.h> int main() { int n, i, j, nalezeno; scanf("%d",&n); while(n!=0){ nalezeno = 0; i=3; j=n-i; while(i<=j){ if(jePrvocislo(i)==1&&jePrvocislo(j)==1){ printf("%d = %d + %d\n",n,i,j); nalezeno = 1; break; } else{ i+=2; j-=2; } } if(nalezeno==0){ printf("Neplati!"); } scanf("%d",&n); } return 0; } int jePrvocislo(int cislo) { int i; for(i=2;i<=sqrt(cislo);i++){ if(cislo%i==0) return 0; } return 1; }

Kódování

  1. Pro každý testovací případ si načíst jednu řádku.
  2. Zjistit, zda je první znak na řádce číslo. Pokud ano, zpráva je zakódovaná, provést dekódování. Pokud ne, zpráva je nezakódovaná, provést zakódování.
  3. Pro zakódování i dekódování si vytvořit tabulku platných znaků a odpovídajících kódů seřazenou podle kódů vzestupně (např. 2 pole, jedno se znaky, druhé s kódy).
  4. Při dekódování může mít kód jednoho znaku 2 nebo 3 číslice. Připravit si pole znaků pro výsledek. Načíst dvě číslice ze vstupní řádky (tj. ze zakódovaného řetězce), prohodit je, převést je na číslo (kód) a zkusit najít tento kód v poli kódů (např. pomocí binárního vyhledávání, pole je seřazené). Pokud kód není nalezen, přidat třetí číslici před první dvě načtené číslice, převést na kód a zkusit tento tříciferný kód najít v poli kódů. Odpovídající znak (na stejném indexu jako kód) uložit do pole pro výsledek. Projít celou řádku až do konce. Pole pro výsledek vypsat znak po znaku pozpátku.
  5. Při zakódování číst vstupní řádku (tj. řetězec, který se má zakódovat) pozpátku. Pro každý znak najít odpovídající kód (např. pomocí binárního vyhledávání, pole je seřazené). Kód vypsat pozpátku číslici po číslici.

Příklad zdrojového kódu:

#include <iostream> #include <string> using namespace std; void enc(char f) { char in[1255]; int i=-1; cin>>noskipws; while(f!='\n') { in[++i]=f; cin>>f; } string a; for(int j=i;j>=0;j--) { int t=in[j]; a=to_string(t); cout<<a[a.size()-1]; if(a.size()==3) cout<<a[1]; cout<<a[0]; } } void dec(char f){ char in[1855]; int i=-1; cin>>noskipws; while(f!='\n') { in[++i]=f; cin>>f; } for(int j=i;j>=0;j-=2) { int res=0; if(in[j]!='1') { res+=in[j-1]-'0'; res+=(in[j]-'0')*10; }else{ res+=in[j-2]-'0'; res+=(in[j-1]-'0')*10; res+=(in[j]-'0')*100; j--; } cout<<(char)res; } } int main() { int n; std::cin>>n; cin>>noskipws; char t; cin>>t; for(int i=0;i<n;i++) { cin>>t; if('0'<=t && t<='9') dec(t); else enc(t); cout<<endl; } }

Nejdelší společná sekvence

  1. Pro každý testovací případ načíst dvě řádky jako řetězce a řešit pomocí dynamického programování.
  2. Vytvořit si dvourozměrné celočíselné pole o délce odpovídající délce prvního slova zvětšené o 1 a o šířce odpovídající délce druhého slově zvětšené o 1. První řádek a první sloupec vyplnit nulami. Index řádku ukazuje na znak v prvním slově, index sloupec na znak v druhém slově.
  3. Vyplnit celé pole. Buňky se vyplňují po řádkách. Pokud jsou si znaky v obou slovech rovny, vloží se do odpovídající buňky pole hodnota nacházející se o jeden řádek a jeden sloupec zpět zvětšená o 1. Pokud si znaky v obou slovech nejsou rovny, vloží se do odpovídající buňky pole větší z hodnot nacházejících se buď jeden řádek nebo jeden sloupec zpět.
  4. Výsledná délka nejdelší společné sekvence vyjde v poslední buňce vyplněného pole.

Příklad zdrojového kódu:

package nejdelsi_sekvence; import java.util.ArrayList; import java.util.Scanner; /** * * @author Ondra */ public class Nejdelsi_sekvence { public static int spolecnaSekvence(String s1, String s2) { int delkaSekvence = 0; int delka1 = s1.length(); int delka2 = s2.length(); int[][] p = new int[delka1+1][delka2+1]; for(int i=0; i <= delka1; i++) { for(int j=0; j <= delka2; j++) { p[i][j] = 0; } } for(int i=0; i < delka1; i++) { for(int j=0; j < delka2; j++) { if(s1.charAt(i) == s2.charAt(j)) p[i+1][j+1] = p[i][j] + 1; else p[i+1][j+1] = Math.max(p[i][j+1], p[i+1][j]); } } delkaSekvence = p[delka1][delka2]; return delkaSekvence; } /** * @param args the command line arguments */ public static void main(String[] args) { // TODO code application logic here Scanner sc = new Scanner(System.in, "UTF-8"); ArrayList<String> radek1 = new ArrayList<>(); ArrayList<String> radek2 = new ArrayList<>(); int pocetPripadu = Integer.parseInt(sc.nextLine()); for(int a=0; a < pocetPripadu; a++) { radek1.add(sc.nextLine().trim()); radek2.add(sc.nextLine().trim()); } for(int a=0; a < pocetPripadu; a++) { int delkaSekvence = 0; String t1 = radek1.get(a); String t2 = radek2.get(a); if(t1.length() > 0 && t2.length() > 0) { delkaSekvence = spolecnaSekvence(t1, t2); } System.out.println(delkaSekvence); } } }

Palindromy

  1. Pro každý testovací případ načíst jednu řádku (vstupní řetězec). Pro určení zrcadlovosti řetězce si vytvořit tabulku znaků opačných (např. dvourozměrné pole znaků o dvou řádkách obsahující pouze znaky, pro které existují znaky opačné).
  2. Připravit si dvě proměnné indikující, že řetězec není zrcadlový a že není palindrom. Obě proměnné na začátku nastavit na false (předpokládáme, že se jedná o zrcadlový palindrom).
  3. Postupně procházet řetězec od začátku a od konce zároveň a porovnávat znaky ze začátku a z konce (nejprve 1. znak s posledním, pak 2. znak s předposledním atd.).
  4. Pokud znaky nejsou stejné, nemůže se jednat o palindrom. Nastavit proměnnou indikující, že řetězec není palindrom na true.
  5. Pokud znaky nejsou opačné (zjistíme neúspěšným vyhledáním znaku v tabulce znaků opačných), nemůže se jednat o zrcadlový řetězec. Nastavit proměnnou indikující, že řetězec není zrcadlový na true. Pokud jsou obě indikující proměnné nastaveny na true, procházení řetězce předčasně ukončit.
  6. Podle stavu indikujících proměnných vypsat řetězec a příslušné hodnocení.

Příklad zdrojového kódu:

program uloha4; {$APPTYPE CONSOLE} uses StrUtils; var pal,ret:boolean; i,j,n:longint; a,s:string; function otoc(a:string):string; var i:integer; b:string; begin b:=''; for i:=length(a) downto 1 do b:=b+a[i]; otoc:=b; end; begin readln(n); for i:=1 to n do begin pal:=false; ret:=false; readln(s); if s=otoc(s) then pal:=true; a:=''; for j:=length(s) downto 1 do case s[j] of 'A': a:=a+'A'; 'E': a:=a+'3'; 'H': a:=a+'H'; 'I': a:=a+'I'; 'J': a:=a+'L'; 'L': a:=a+'J'; 'M': a:=a+'M'; 'O': a:=a+'O'; 'S': a:=a+'2'; 'T': a:=a+'T'; 'U': a:=a+'U'; 'V': a:=a+'V'; 'W': a:=a+'W'; 'X': a:=a+'X'; 'Y': a:=a+'Y'; 'Z': a:=a+'5'; '1': a:=a+'1'; '2': a:=a+'S'; '3': a:=a+'E'; '5': a:=a+'Z'; '8': a:=a+'8'; end; if a=s then ret:=true; if pal and ret then writeln(s,': zrcadlovy palindrom') else if pal then writeln(s,': palindrom') else if ret then writeln(s,': zrcadlovy retezec') else writeln(s,': retezec'); writeln; end; readln; end.

Seznam slov

  1. Postupně po řádcích načítat vstupní text. Skončit v okamžiku, kdy je v načtené řádce na začátku samostatná tečka. Vytvořit si pole slov o maximální délce 5000 (vyplývá ze zadání), na začátku bude prázdné.
  2. Každou řádku rozdělit na slova podle všech znaků, které nejsou písmeno (tj. mezery, pomlčky, podtržítka, dvojtečky, atd.). Každé slovo zkusit najít v poli slov. Pokud není nalezeno, přidat ho do tohoto pole.
  3. Po načtení všech řádek pole slov seřadit vzestupně.
  4. Vypsat pole slov.

Příklad zdrojového kódu:

import java.util.*; public class Slova { public static void main(String[] args) { Scanner sc = new Scanner(System.in); String s = ""; Set<String> words = new TreeSet<String>(); while(sc.hasNextLine()){ s = sc.nextLine(); if(s.equals(".")) break; else if(s.equals("")) continue; String[] splitted = s.split("[\\p{Punct}\\s0-9]+"); for(String word : splitted) words.add(word.toLowerCase()); } for(String word : words) System.out.println(word); } }

Strom

  1. Pro každý testovací případ načíst dva řetězce oddělené mezerou reprezentující přímý a vnitřní průchod binárním stromem. Vytvořit si strukturu/třídu/záznam pro uložení uzlu binárního stromu (tj. obsahující hodnotu uzlu a dva odkazy na potomky).
  2. Rekurzivně vytvořit strom z přímého a vnitřního průchodu:
  3. Načíst znak (hodnota uzlu) z přímého průchodu. Inkrementovat index přímého průchodu. Vytvořit uzel s tímto znakem.
  4. Najít tento znak ve vnitřním průchodu. Vnitřní průchod rozdělit na levou a pravou část v místě nalezeného znaku.
  5. Rekurzivně provést pro levou a pravou část vnitřního průchodu. Výsledek přiřadit jako levého a pravého potomka uzlu.
  6. Rekurzivně vypsat zpětný průchod stromem. Zavolat nad kořenem stromu, provést rekurzivně pro levý a pravý podstrom a vypsat hodnotu uzlu.

Příklad zdrojového kódu:

#include <stdio.h> #include <string.h> int search(char *arr, char c, int n) { int i; for(i = 0; i < n; i++) { if(arr[i] == c) return i; } } void postorder(char *pre, char *in, int n) { int koren = search(in, pre[0], n); if(koren != 0) postorder(pre+1, in, koren); if(koren != n-1) postorder(pre+koren+1, in+koren+1, n-koren-1); printf("%c", pre[0]); } int main() { int i, n; char preorder[31], inorder[31]; scanf("%d", &n); for(i = 0; i < n; i++) { scanf("%s %s", preorder, inorder); postorder(preorder, inorder, strlen(preorder)); printf("\n"); } 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ů.

Dekódování pásky

  1. Určit, jak jsou data na pásce uložena - každá řádka obsahuje 7 bitů a odpovídá jednomu znaku, znak "o" odpovídá hodnotě 1, znak mezera " " odpovídá hodnotě 0.
  2. Pro každou řádku obsahující "o" a " ":
  3. Postupně zleva projít významové znaky řádky, pokud je znak roven "o", udělat logický součet 1 s proměnnou a provést posun o 1 vlevo.
  4. Proměnnou vypsat jako znak.

Příklad zdrojového kódu:

var i:integer; s,x:string; begin readln(s); readln(s); x:=''; while s[1]='|' do begin i:=0; if s[3]='o'then i:=i+64; if s[4]='o'then i:=i+32; if s[5]='o'then i:=i+16; if s[6]='o'then i:=i+8; if s[8]='o'then i:=i+4; if s[9]='o'then i:=i+2; if s[10]='o'then i:=i+1; x:=x+chr(i); readln(s); end; writeln(x); readln; end.

Oslava zápočtu

  1. Pro každý testovací případ načíst kapacitu studentky a všechny drinky.
  2. Z celkového množství alkoholu M a množství vypitého 1. studentkou M1 lze odvodit M2 (M = M1 + M2).
  3. Označme D[i] sílu i-tého drinku. Studentky dohromady vypily drinky 1 až (i – 1) a na řadě je drink i. Potom M = D[1] + D[2] + ... + D[i – 1] a K je kapacita jedné studentky.
  4. Drink i může vypít buď 1. nebo 2. studentka, ale nesmí překročit kapacitu K:
    • M1’ = M1 + D[i], pokud M1 + D[i] <= K
    • M2’ = M – M1 + D[i], pokud M – M1 + D[i] <= K
  5. Takových M1 může být více. Budeme udržovat množinu P[i – 1] všech M1 dosažitelných na 1, 2, …, (i – 1) drincích.
  6. P[i] zkonstruujeme z P[i – 1] s využitím M1’ a M2’
  7. Pokud je nově vytvořená P[i] prázdná, pak nelze vypít žádný drink ani jednou studentkou, konec, vrátíme (i – 1)

Příklad zdrojového kódu:

#include <iostream> #include <cstdio> #include <cmath> #include <vector> #include <map> using namespace std; typedef long long ll; typedef pair<int, int> ii; map<ii, int> dp; int getMax(int a, int b, int at, vector<int> &v){ if(dp.count(ii(a, b)) != 0){return dp[ii(a, b)];} int ans; int w = v[at]; if(w > a & w > b){ ans = at; }else if(w > a){ ans = getMax(a, b-w, at+1, v); }else if(w > b){ ans = getMax(a-w, b, at+1, v); }else{ ans = max(getMax(a-w, b, at+1, v), getMax(a, b-w, at+1, v)); } return dp[ii(a, b)] = ans; } int main(){ vector<int> v; while(true){ int kap; scanf("%d", &kap); if(kap == 0) break; dp.clear(); vector<int> v; while(true){ int n; scanf("%d", &n); if(n == 0) break; v.push_back(n); } // sort(v.begin(), v.end()); int ans = getMax(kap, kap, 0, v); printf("%d\n", ans); } return 0; }

Podíl

  1. Pro každý testovací případ načíst dělenec a dělitel a uložit je do pole čísel.
  2. Použít algoritmus dělení, který nevyžaduje zpracovat najednou celé číslo (např. s využitím odčítání dělitele od dělence, inkrementace výsledku a posunu výsledku).
  3. Provádět dělení, dokud z dělence nezbude 0 nebo dokud není detekována perioda.
  4. Pro detekci periody:
    • Pamatovat si jednotlivé zbytky po každém dělení.
    • Při vypočtení dalšího zbytku zkontrolovat, zda se již nevyskytl.
    • Pokud se zbytek již vyskytl, sekvence čísel ve výsledku se začne opakovat (tj. detekována perioda).

Příklad zdrojového kódu:

import java.util.*; import java.math.*; public class Main{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); int x = sc.nextInt(); for(int i=0;i<x;i++){ String s1 = sc.next(); String s2 = sc.next(); String s3 = sc.next(); BigDecimal b1 = new BigDecimal(s1); BigDecimal b2 = new BigDecimal(s3); //BigDecimal full = b1.divide(b2, BigDecimal.ROUND_DOWN); int prec = 2005; BigDecimal a = new BigDecimal("10"); a = a.pow(prec); b1 = b1.multiply(a); BigDecimal b3 = b1.divide(b2, BigDecimal.ROUND_DOWN); b3 = b3.divide(a); String ans = b3.toPlainString(); int k = ans.length(); if(k >= (prec*9)/10){ //String novy = ans.substring(ans.indexOf(".")+1); int h = k-1; int f = k-2; while(f > (prec/10)){ if(ans.charAt(f) == ans.charAt(h)){ f--; h--; }else{ while(ans.charAt(f) != ans.charAt(h) && f > (prec/10)){ f--; } } } while(ans.charAt(f) == ans.charAt(h)){ f--; h--; } String per = ans.substring(f+1, h+1); //System.out.println(ans + " " + f + " "+ h + " "+per); ans = ans.substring(0,f+1) + "(" + per + ")" ; } //System.out.println(s1+"-"+s2+"-"+s3); System.out.println(ans); } } }

Topení

  1. Načíst T techniků a kohouty, za které jsou zodpovědní.
  2. Vyřešit T rovnic o T neznámých. Každá rovnice reprezentuje jeden kohout, každý technik jednu neznámou.
  3. Pro řešení použít Gauss-Jordanovu eliminaci.
    • Uložit rovnice do matice T x (T + 1)
    • Každá rovnice odpovídá jedné řádce. Pokud technik spravuje kohout odpovídající rovnici, je v příslušném sloupci 1, jinak 0.
    • Sčítat a přesouvat řádky matice, aby na hlavní diagonále byly hodnoty 1, jinde 0.
    • Úpravy matice se provádí v aritmetice modulo 2. V matici jsou tedy pouze hodnoty 0 a 1.
    • Poslední sloupec indikuje použité techniky (1 znamená, že technik má dostat pokyn, 0 znamená, že nikoliv).
  4. Vypsat čísla techniků, kteří mají dostat pokyn, vzestupně.

Příklad zdrojového kódu:

#include<stdio.h> int main(void){ int T; scanf("%i", &T); int Pole[T][T+1]; int i; int j; int k; int cislo; for(i=0;i<T;i++){ for(j=0;j<T;j++){ Pole[i][j]=0; } } for(j=0;j<T;j++){ Pole[j][T]=1; } for(i=0;i<T;i++){ while(1){ scanf("%i", &cislo); if(cislo==-1) break; Pole[cislo-1][i]=1; } } int uzmam[T]; for(i=0;i<T;i++){ uzmam[i]=-1; } int dalsi[T]; for(i=0;i<T;i++){ dalsi[i]=-1; } for(i=0;i<T;i++){ if(Pole[i][0]==1) dalsi[0]=i; } int aa; int bb; for(i=0;i<T;i++){ if(dalsi[i]==-1){ printf("-1\n"); return 0; } uzmam[dalsi[i]]=i; /*for(aa=0;aa<T;aa++){ for(bb=0;bb<=T;bb++){ printf("%i ", Pole[aa][bb]); } printf("\n"); } printf("%i\n", dalsi[i]); printf("%\n");*/ for(j=0;j<T;j++){ if(Pole[j][i]==1&&uzmam[j]==-1){ for(k=0;k<=T;k++){ Pole[j][k]+=Pole[dalsi[i]][k]; if(Pole[j][k]==2) Pole[j][k]-=2; } } if(i<T-1){ if(Pole[j][i+1]==1&&uzmam[j]==-1) dalsi[i+1]=j; } } } int pouziji[T]; for(i=0;i<T;i++){ pouziji[i]=0; } int zrovna; for(i=T-1;i>=0;i--){ zrovna=0; for(j=T-1;j>i;j--){ zrovna+=pouziji[j]*Pole[dalsi[i]][j]; } zrovna=zrovna%2; if(zrovna!=Pole[dalsi[i]][T]) pouziji[j]=1; } int stav=0; for(i=0;i<T;i++){ if(pouziji[i]==1&&stav==1){ printf(" %i", i+1); } if(pouziji[i]==1&&stav==0){ printf("%i", i+1); stav=1; } } printf("\n"); return 0; }

Trezor

  1. Pro každý testovací případ načíst všechny klíče trezoru.
  2. Vytvořit si graf, kde vyrcholy představují klíče a hrany jsou ohodnoceny celkovým minimálním počtem otočení potřebným k přechodu z jednoho klíče (vrcholu) na druhý.
  3. Vytvořit všechny možné hrany grafu a spočítat jejich ohodnocení.
  4. Všechny hrany uložit do pole a seřadit podle ohodnocení vzestupně.
  5. Odstranit všechny hrany z grafu.
  6. Postupně přidávat hrany do grafu:
    • Hranu přidat pouze v případě, že mezi vrcholy, které spojuje zatím neexistuje cesta (ověřit pomocí prohledávání do hloubky (DFS)).
    • Ohodnocení přidané hrany přičíst do celkového počtu otočení.
    • Pokud je při prohledávání grafu do hloubky dosaženo všech vrcholů, skončit.
  7. Nalézt nejnižší počet otočení při přechodu mezi 0000 a jedním z klíčů a tuto nalezenou nejnižší hodnotu přičíst do výsledku.

Příklad zdrojového kódu:

#include <cstdio> #include <iostream> #include <algorithm> #include <cmath> #include <string> using namespace std; struct e { int a,b,v; }; int min(int a, int b) { if(a<b) return a; return b; } int max(int a, int b) { if(a>b) return a; return b; } bool cmp(e a, e b) { if(a.v<b.v) return true; return false; } int hod(int i, int j) { int a=0; for(int q=0;q<4;q++) { int c=int(i/pow(10,q))%10; int d=int(j/pow(10,q))%10; a+=min(abs(c-d), 10+min(c,d)-max(c,d)); } return a; } int main() { int t; int i,j,k,l; scanf("%d", &t); for(i=0;i<t;i++) { scanf("%d", &k); e hr[k*k+k*4]; int klice[k+10]; int min=100000; for(j=0;j<k;j++) { scanf("%d", &klice[j]); } int poc=0; for(j=0;j<k;j++) { for(l=j+1;l<k;l++) { hr[poc].a=j; hr[poc].b=l; hr[poc].v=hod(klice[j],klice[l]); poc++; } if(hod(klice[j],0)<min) min=hod(klice[j],0); } sort(hr, &hr[poc], cmp); int skupiny[k+10][k+10]; for(j=0;j<k;j++) { for(l=0;l<k+2;l++) { skupiny[j][l]=-1; } skupiny[j][0]=j; klice[j]=j; } int zbyva=k-1; poc=0; int res=min; while(zbyva>0) { while(klice[hr[poc].a]==klice[hr[poc].b]) poc++; int q=0; int last=0; int ak=klice[hr[poc].a]; int bk=klice[hr[poc].b]; while(skupiny[ak][last]!=-1) last++; while(skupiny[bk][q]!=-1) { skupiny[ak][last++]=skupiny[bk][q]; klice[skupiny[bk][q]]=ak; q++; } res+=hr[poc].v; zbyva--; } printf("%d\n", res); } return 0; }