PilsProg 2018

Výsledky kvalifikace

Splněných úlohPočet soutěžících
64
35
28
15

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ů
34
23
02

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

Ilustrační úlohy

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

Kvalifikační úlohy

NázevČísloÚspěšných řešitelů
Cvičení z programování18114
Délka cesty18124
Hra181320
Kostky181419
Naplň si pohár18159
Rozsazení18164

Finálové úlohy

NázevČísloÚspěšných řešitelů
Plán zkoušek18212
Pomodoro18222
Slepičí úlet18237
Zahrada18240
Zobrazení času18257

A jaké bylo finále?

Finále začíná ...

Harmonogram PilsProg 2018

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.

Cvičení z programování

  1. Pro každé cvičení načíst počet studentů a čísla, která si studenti vylosovali.
  2. Na tato čísla se dívat jako na vrcholy grafu, ve kterém jsou dvě čísla spojená hranou právě tehdy, když je jejich největší společný dělitel větší než 1. Počet skupin pak odpovídá počtu komponent grafu.
  3. Pro efektivní uložení grafu použít datovou strukturu disjunktních množin.
  4. Protože vytvoření všech hran grafu prozkoumáním všech dvojic čísel by bylo pomalé, vytvářet hrany tak, že každé číslo je spojeno hranou s jeho děliteli, kterými jsou všichni společní dělitelé s ostatními čísly studentů.
  5. Nakonec je třeba nezapomenout, že číslo 1 se může vyskytovat v posloupnosti vícekrát, ale každý výskyt bude v samostatné skupině.

Příklad zdrojového kódu:

#include <iostream> #include <map> #include <vector> #include <set> const int primes[168] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997}; int main() { int T; std::cin >> T; while(T--) { int n; std::cin >> n; std::vector<int> v; while(n--) { int tmp; std::cin >> tmp; v.push_back(tmp); } std::map<int,std::vector<int> > m; int count = 0; for(int i:v) { std::vector<int> fact; int tmp=i; if(tmp == 1) { fact.push_back(tmp); if(m.count(tmp)) count++; } else for(int p:primes) { if(tmp % p == 0) { fact.push_back(p); while(tmp % p == 0) tmp /= p; } } if(tmp != 1) fact.push_back(tmp); m[fact[0]]; for(int i=1;i<fact.size();i++) { m[fact[i]].push_back(fact[i-1]); m[fact[i-1]].push_back(fact[i]); } } std::set<int> used; for(auto &i:m) { if(used.count(i.first)) continue; used.insert(i.first); count++; std::vector<int> z; z.push_back(i.first); while(z.size() > 0) { int c = z.back(); z.pop_back(); for(int j:m[c]) { if(!used.count(j)) { used.insert(j); z.push_back(j); } } } } std::cout << count << std::endl; } }

Délka cesty

  1. Pro každou hru načíst počet překážek, počet kroků a souřadnice jednotlivých překážek.
  2. Průchodem překážek si určit maximální a minimální souřadnice x a y a vytvořit si mapu (dvourozměrné pole) o nejmenší možné velikosti, aby se na ní všechny překážky vešly. Body pole inicializovat zápornými čísly (např. -1 = překážka, -2 = počátek).
  3. Prohledáváním do šířky určit a uložit do připraveného pole vzálenosti bodů od počátečního bodu [0, 0]. Mezi body existuje hrana, pokud jsou sousední (jen vodorovně a svisle, nikoliv diagonálně) a ani jeden z nich není překážka.
  4. Určit maximální souřadnici x, na kterou se lze dostat z počátku, procházením pole zprava a hledáním minimální kladné hodnoty vždy v celém sloupci.
  5. Hledá se minimální hodnota menší nebo rovna počtu kroků. Pokud je tato hodnota nalezena v posledním sloupci, je výsledkem aktuální souřadnice sloupce zvětšená o počet kroků zmenšený o nalazenou minimální hodnotu. Pokud se nejedná o poslední sloupec, je výsledkem aktuální souřadnice sloupce.

Příklad zdrojového kódu:

#include <iostream> #include <vector> #include <queue> using namespace std; struct bod{ int x,y; }; int main(){ int xs[4] = {1,0,0,-1}; int ys[4] = {0,1,-1,0}; int h; cin >> h; while(h--){ int p, k; cin >> p >> k; vector<vector<int> > sou(2001,vector<int>(2001,0)); int dx = 1000, dy = 1000; for(int i = 0; i < p; i++){ int x, y; cin >> x >> y; sou[x+dx][y+dy] = -1; } sou[dx][dy]=-1; int bx = dx; queue<bod> fr; bod b; b.x = dx; b.y = dy; fr.push(b); for(int krok = 1; krok <= k; krok++){ queue<bod> fr2; while(!fr.empty()){ bod now = fr.front(); fr.pop(); for(int j = 0; j < 4; j++){ int newx = now.x + xs[j]; int newy = now.y + ys[j]; if(newx>=2001 || newx < 0 || newy>=2001||newy<0||sou[newx][newy]!=0) continue; sou[newx][newy] = krok; b.x = newx; b.y = newy; fr2.push(b); if(newx>bx) bx = newx; } } fr = fr2; } cout << bx-1000<<endl; } return 0; }

Hra

  1. Pro každou písničku načíst řetezec s instrukcemi.
  2. Určit si prostředek řetězce vydělením jeho délky dvěmi.
  3. Projít jednotlivé znaky řetězce. V první půlce je porovnávat se znakem '>', ve druhé půlce se znakem '<' a počítat počet rozdílů.
  4. Vrátit nalezený počet rozdílů.

Příklad zdrojového kódu:

program U1813; var p,I:Integer; N,Y:byte; V:array of string; O:array of Integer; begin readln(p); SetLength(V,p); SetLength(O,p); dec(p); for I:=0 to p do readLn(V[I]); for I:=0 to p do begin N:=Length(V[I]); for Y:= 1 to N div 2 do if V[I][Y] = '<' then inc(O[I]); for Y:= (N div 2)+1 to N do if V[I][Y] = '>' then inc(O[I]); end; for I:=0 to p do writeln(O[I]); end.

Kostky

  1. Vytvořit si pole celých čísel o délce odpovídající maximálnímu počtu kostek a naplnit ho počtem dělitelelů čísel odpovídajících indexům pole.
  2. Počet dělitelů určit testováním každého čísla menšího než druhá odmocnina čísla, pro které hledáme počet dělitelů, zda je zbytek po dělení roven nule.
  3. Pro každý testovací případ načíst počet kostek.
  4. Načtený počet kostek použít jako index do dříve vytvořeného pole a vrátit hodnotu na tomto indexu.

Příklad zdrojového kódu:

package cv1814; import java.util.Scanner; public class Cv1814 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int i = sc.nextInt(); for(; i > 0; i--) { int result = 0; int input = sc.nextInt(); int iterace = (int) Math.floor(Math.sqrt(input)); for(int j = 1; j < iterace+1; j++) { result += Math.floor(input/j)-(j-1); } System.out.println(result); } } }

Naplň si pohár

  1. Pro každou soutěž načíst počet pohárů a objemy jednotlivýh pohárů.
  2. Je nutno prověřit pouze čísla odpovídající objemům pohárů. Všechna ostatní se dají dosáhnout.
  3. Vytvořit si pole, kde je každý objem poháru uveden jen jednou (je jedinečný).
  4. Vytvořit pole, kde je každá možná výhra uvedena pouze jednou. Výhru určit průchodem všech objemů pohárů pro každý jedinečný objem poháru. Výhru přidat do pole výher, pokud tam ještě není.
  5. Vrátit počet objemů, které jsou v poli různých pohárů, ale nejsou v poli možných výher.

Příklad zdrojového kódu:

#include <iostream> #include<bits/stdc++.h> #include <math.h> using namespace std; long long cisla[208]; int main() { int n; cin>>n; long long maxi,p; long long aktual; int vrat; for(int i=0;i<n;i++){ map<long long,int> mapka; vrat=0; cin>>p; maxi=0; for(int j=0;j<p;j++){ cin>>cisla[j]; mapka[cisla[j]]=0; if(cisla[j]>maxi){maxi=cisla[j];} } for(int j=0;j<p;j++){ aktual=cisla[j]; for(int k=0;k<p;k++){ if(aktual==cisla[k]){aktual=aktual*2;} if(aktual>maxi){break;} } for(int k=0;k<p;k++){ if(cisla[k]==aktual){ if(mapka[cisla[k]]==0){mapka[cisla[k]]=1;} } } } for( map<long long,int>::iterator ii=mapka.begin(); ii!=mapka.end(); ++ii){ if((*ii).second==0){vrat++;} //cout << (*ii).first << ": " << (*ii).second << endl; } cout<<vrat<<endl; } return 0; }

Rozsazení

  1. Pro každou lavici načíst počet míst, počet studentů a vzdálenosti jednotlivých míst od začátku lavice.
  2. Pole vzdáleností seřadit vzestupně.
  3. Vybrat minimální vzdálenost mezi studenty a ověřit, že se studenti do lavice při této minimální vzdálenosti vejdou.
  4. Minimální vzdálenost vybrat pomocí binárního vyhledávání - spodní hranice je 0, horní hranice je největší vzdálenost místa dělená počtem mezer mezi studenty.

Příklad zdrojového kódu:

#include <iostream> #include <vector> #include <algorithm> bool isPossible(const std::vector<int> &v, int d, int p) { int last = -1; for(int i=0;i<v.size();i++) { if(last == -1 || v[i]-last >= d) { p--; last = v[i]; } } if(p>0) return false; else return true; } int main() { int T; std::cin >> T; while(T--) { int w,s; std::cin >> w >> s; std::vector<int> v; while(w--) { int tmp; std::cin >> tmp; v.push_back(tmp); } std::sort(v.begin(),v.end()); int b=0; int e=1000000001; while(e-b>1) { int m = (b+e)/2; if(isPossible(v,m,s)) b=m; else e=m; } std::cout << b << std::endl; } }

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.

Plán zkoušek

  1. Pro každou místnost načíst vymezenou dobu a počet všech zkoušek. Načíst si jednotlivé zkoušky do pole (pro každou uložit dobu trvání a kapacitu).
  2. Řešit pomocí dynamického programování.
  3. Vytvořit si dvourozměrné celočíselné pole o počtu řádek odpovídající vymezené době místnosti (zvětšené o 1) a počtu sloupců odpovídající počtu všech zkoušek (zvětšené o 1).
  4. Vyplnit celé pole. Na prvek [i, j] uložit celkovou kapacitu určenou jako maximum z předchozí hodnoty a hodnoty po přidání kapacity další zkoušky.
  5. Projít poslední sloupec dvourozměrného pole odspodu a najít nejmenší index řádky, pro který je hodnota v tomto sloupci rovna poslední hodnotě v tomto sloupci (tj. nalezené maximální celkové kapacitě).
  6. Hodnotu nalezeného minimálního indexu a nalezenou maximální celkovou kapacitu (hodnota v posledním sloupci a poslední řádce dvourozměrného pole) oddělené mezerou na samostatnou řádku.

Příklad zdrojového kódu:

#include <iostream> #include<bits/stdc++.h> using namespace std; int vzdalenost(int a,int b,int c,int d){ return abs(c-a)+abs(d-b); } int main() { ios_base::sync_with_stdio(false); //ifstream fin; //fin.open("vstup.txt"); int m; cin>>m; int t,k; for(int i=0;i<m;i++){ int d,z; cin>>d>>z; //cout<<"d "<<d<<endl; int pole[d+1]; for(int j=0;j<d+1;j++){ pole[j]=0; } for(int j=0;j<z;j++){ cin>>t>>k; //cout<<"t,k "<<t<<", "<<k<<endl; for(int l=d;l>=t;l--){ if(pole[l]<pole[l-t]+k){ pole[l]=pole[l-t]+k; } } } //for(int j=0;j<d+1;j++){ // cout<<pole[j]<<" "; //} //cout<<endl; int maxi=0; for(int j=0;j<d+1;j++){ if(pole[j]>maxi){ maxi=pole[j]; } } int kde; for(int j=d;j>=0;j--){ if(pole[j]==maxi){ kde=j; } } cout<<kde<<" "<<maxi<<endl; } //fin.close(); return 0; }

Pomodoro

  1. Pro každý pracovní cyklus robota (testovací případ) načíst počáteční pozici Pomodora, počet kěříků (k) a pozice jednotlivých keříků.
  2. Je potřeba vyřešit symetrický problém obchodního cestujícího - najít pořadí, v jakém je třeba keříky navštívit, aby celková cena byla co nejmenší a Pomodoro začínal i končil v počáteční pozici.
  3. Řešit pomocí dynamického programování.
  4. Vytvořit si dvourozměrné celočíselné pole o počtu řádek odpovídající 2k a o počtu sloupců odpovídající k. Prvky pole nastavit na -1 kromě prvků [2i , i], které se nastaví na vzdálenost i-tého keříku od počáteční pozice Pomodora.
  5. S využitím rekurze hledat cesty z počáteční pozice mezi všemi keříky s minimální cenou a mezivýsledky zaznamenávat do dvourozměrného pole. Nalézt všechny takové cesty končící různým keříkem.
  6. K ceně každé nalezené cesty přičíst cenu od posledního keříku do počáteční pozice a získat tak celkovou cenu.
  7. Vypsat celkovou cenu, která je minimální, na samostatnou řádku.

Příklad zdrojového kódu:

package pils.prog; import java.util.Scanner; import java.util.ArrayList; public class Pomodoro { static Scanner scan = new Scanner(System.in); static int minLength = -1; static Position startingPosition; static int scanInt() { return scan.nextInt(); } static void nextPosition(Position currentPosition, ArrayList<Position> positions, int currentLength) { for (int i = 0; i < positions.size(); i++) { int newLength = currentLength + positions.get(i).distance(currentPosition); if (newLength > minLength && minLength != -1) { return; } ArrayList<Position> newList = new ArrayList<>(positions); newList.remove(i); nextPosition(positions.get(i), newList, newLength); } if (positions.isEmpty()) { currentLength += currentPosition.distance(startingPosition); if (minLength == -1 || currentLength < minLength) { minLength = currentLength; } } } public static void main(String[] args) { int[] results = new int[scanInt()]; for (int i = 0; i < results.length; i++) { minLength = -1; ArrayList<Position> positions = new ArrayList<>(); startingPosition = new Position(scanInt(), scanInt()); int positionCount = scanInt(); for (int j = 0; j < positionCount; j++) { positions.add(new Position(scanInt(), scanInt())); } nextPosition(startingPosition, positions, 0); results[i] = minLength; } for (int result : results) { System.out.println(result); } } } class Position { int x; int y; public Position(int x, int y) { this.x = x; this.y = y; } public int distance(Position position) { return Math.abs(x - position.x) + Math.abs(y - position.y); } }

Slepičí úlet

  1. Načít počet portálů a slepic. Načíst všechny portály (souřadnice středu a „poloměr“ portálu) do pole. U každého portálu si uložit i jeho číslo (index v poli zvětšený o 1).
  2. Seřadit portály vzestupně podle souřadnice x.
  3. Postupně načítat souřadnice slepic.
  4. Pro každou slepici procházet seřazené pole portálů a zjišťovat, zda má slepice menší nebo stejnou souřadnici x jako portál a má souřadnici y uvnitř souřadnic y úsečky portálu. Pokud ano, byl nalezen první portál, do kterého slepice vběhne.
  5. Vypsat číslo tohoto portálu na samostatnou řádku, nebo vypsat 0, pokud takový portál nebyl nalezen.

Příklad zdrojového kódu:

#include <iostream> #include <vector> #include <algorithm> using namespace std; struct portal{ int x, y, r; }; struct slepice{ int x, y; }; int main(){ int p, s; cin >> p >> s; vector<portal> ps(p); for(int i = 0; i < p; i++) cin >> ps[i].x>> ps[i].y >> ps[i].r; for(int i = 0; i < s; i++){ int x, y; cin >> x >> y; int bl = -1; int where = -1; for(int j = 0; j < p; j++){ if(ps[j].y+ps[j].r >= y && ps[j].y-ps[j].r <= y && ps[j].x >= x){ int leng = abs(x-ps[j].x); if(bl == -1 || leng < bl){ bl = leng; where = j; } } } if(bl==-1) cout << 0 << endl; else cout << where+1 << endl; } return 0; }

Zahrada

  1. Pro každou zahradu načíst její velikost a mapu jako pole znaků bez bílých znaků (mezer). Určit si vzájmené vzdálenosti (tj. počty políček) mezi jednotlivými políčky pro všechny políčka zahrady pomocí prohledávání grafu do šířky.
  2. Cesty mezi oblastmi (zahrádkami AD) mohou být maximálně 3 ale mohou se křížit. Maximálně mohou být tedy 2 křižovatky.
  3. Vytvořit si graf o šesti vrcholech (4 oblasti + maximálně 2 křižovatky). Jako křižovatky postupně zkoušet všechna možná políčka, která nejsou oblastmi (tj. na kterých se může vybudovat cesta). Pro každý pokus najít délku kostry grafu (pomocí Jarníkova/Primova algoritmu).
  4. Vrátit nejmenší délku kostry grafu.

Příklad zdrojového kódu:

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

Zobrazení času

  1. Pro každý čas načíst všechny číslice jako celá čísla do pole o šesti prvcích.
  2. Pro všechny mocniny dvojky počínaje od nejvyšší (tj. 23):
  3. Vypsat exponent dvojky. Projít pole od začátku do konce. Pro každé číslo v poli vyzkoušet pomocí logického součinu s aktuální mocninou dvojky, zda binární zápis čísla obsahuje jedničku na pozici odpovídající mocnině dvojky. Pokud ano, vypsat o, jinak vypsat -.

Příklad zdrojového kódu:

#include <iostream> #include <stdlib.h> #include <stdio.h> int main(void) { int c; std::cin >> c; for(int i = 0; i < c; i++) { char in[10]; std::cin >> in; for(int e = 3; e >= 0; e--) { std::cout << e; for(int n = 0; n < 8; n++) { if(n == 2 || n == 5) continue; int nr = (int)in[n] - (int)'0'; char out = nr & (1 << e) ? 'o' : '-'; std::cout << out; } std::cout << std::endl; } } return 0; }