PilsProg 2014

Výsledky kvalifikace

Splněných úlohPočet soutěžících
63
52
32
26
12

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ů
52
42
31
21
16
01

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ů
AxB070447
Největší ze tří celých čísel080635
AplusB080536
Pascalův trojúhelník070336

Kvalifikační úlohy:

NázevOznačeníÚspěšných řešitelů
Cesta14126
Pokuty14146
Hesla141315
Příklady141513
Barevná věž14113
Symetrie14165

Finálové úlohy:

NázevOznačeníÚspěšných řešitelů
Oplocení14255
MHD14242
Mayové14235
Čísla142212
Besídka14215

A jaké bylo finále?

Finále začíná ...

Harmonogram PilsProg 2014

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.

Barevná věž

  1. Pro každý testovací případ si vytvořit pomocné pole celých čísel (tabulku barev) o velikosti 100 (počet všech možný barev). Tabulka bude obsahovat maximální výšku pro danou barvu (na začátku 0).
  2. Postupně načítat mnohoúhelníky (barvy jednotlivých hran). Pro každý mnohoúhelník:
  3. Postupně otáčet o jednu hranu, dokud se neotočí dokola. Pro každé pootočení zjistit barvu horní hrany a její hodnotu v tabulce barev. Tuto hodnotu přičíst do hodnoty v tabulce barev pro barvu dolní hrany.
  4. Liché mnohoúhelníky mohou přispět pouze 1 u barev, u kterých je 0, protože na ně nelze nic postavit.
  5. Během otáčení mnohoúhleníku se barvy musí ukládat do pomocné tabulky barev, aby nedocházelo k ovlivnění výpočtu (mnohoúhelník může mít více hran stejné barvy). Po skončení otáčení mnohoúhleníku se hodnoty z pomocné tabulky barev překopírují do hlavní tabulky barev (pokud jsou větší).

Příklad zdrojového kódu:

#include <cstdio> #include <cstring> #include <vector> using namespace std; int main() { int m; while (scanf("%d", &m) == 1 && m) { vector<vector<int> > barvy(m); for (int i = 0; i < m; i++) { int n; scanf("%d", &n); for (int j = 0; j < n; j++) { int c; scanf("%d", &c); barvy[i].push_back(c); } } int dp[2][101]; // vyska - sudy, lichy for (int i = 0; i < 2; i++) { for (int j = 1; j <= 100; j++) { dp[i][j] = 0; } } int vysledek = 0; for (int i = m-1; i >= 0; i--) { int cur = i % 2, prev = (i+1) % 2, pocet_barev = barvy[i].size(); for (int j = 1; j <= 100; j++) { dp[cur][j] = dp[prev][j]; } for (int j = 0; j < pocet_barev; j++) { int barva = barvy[i][j]; if (pocet_barev % 2 == 0) { int naproti = barvy[i][(j + pocet_barev / 2) % pocet_barev]; dp[cur][naproti] = max(dp[cur][naproti], dp[prev][barva] + 1); vysledek = max(vysledek, dp[cur][naproti]); } else { vysledek = max(vysledek, dp[prev][barva] + 1); } } } printf("%d\n", vysledek); } return 0; }

Cesta

Tato úloha se dá řešit pomocí modifikovaného Dijkstrova algoritmu (algoritmus pro nalezení nejkratší cesty mezi dvěma vrcholy grafu). Hledáme druhou nejkratší cestu. U každého vrcholu je nutné si pamatovat počet navštívení. Každý vrchol může být navštíven maximálně dvakrát. Algoritmus končí v okamžiku, kdy je podruhé navštíven cílový vrchol.

Příklad zdrojového kódu:

#include <stdio.h> #include <vector> #include <queue> #include <utility> #define MAX 10001 #define mp make_pair #define pb push_back using namespace std; vector< pair<int, int> > graph[MAX]; int doDijkstra(int start, int end) { int vis[MAX] = {0}, v = 0; priority_queue< pair<int, int> > q; q.push(mp(0, start)); pair<int, int> curr; while(!q.empty()) { curr = q.top(); q.pop(); curr.first = -curr.first; v = curr.second; ++vis[v]; if(v == end && vis[v] == 2) { return curr.first; } for(int i = 0, n = graph[v].size(); i < n; i++) { if(vis[graph[v][i].first] < 2) { q.push(mp(-(curr.first + graph[v][i].second), graph[v][i].first)); } } } return -MAX; } int main() { int t, n, m, a, b, c, s, e; scanf("%d", &t); while(t--) { scanf("%d %d", &n, &m); for(int i = 0; i < n; i++) { graph[i].clear(); } for(int i = 0; i < m; i++) { scanf("%d %d %d", &a, &b, &c); graph[a - 1].pb(mp(b - 1, c)); graph[b - 1].pb(mp(a - 1, c)); } scanf("%d %d", &s, &e); printf("%d\n", doDijkstra(s - 1, e - 1)); } }

Hesla

  1. Pro každé osobní číslo získat jeho číselnou část o délce 4 číslice (podřetězec z načteného řetězce od znaku 4 do znaku 7, pokud jsou znaky číslované od 0, převést na číslo).
  2. Převést takto získané číslo na římské (uložit si do pole jednotlivé římské číslice a převáděné číslo zkoumat od nejvyšší řádu, již zpracované hodnoty od čísla odečítat, římské číslo ukládat do řetězce či pole znaků).
  3. Výsledné pole znaků či řetězec projít a spočítat počet jednotlivých římských číslic.

Příklad zdrojového kódu:

import java.util.*; /** * * @author hynek */ public class Hesla { private static final String literals = "IVXLCDM"; private static final int[] nums = { 1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1 }; private static final String[] rNums = { "M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I" }; private static String toRoman(int n){ StringBuilder roman = new StringBuilder(); for (int i = 0; i < nums.length && n != 0; i++) { while (n >= nums[i]) { n -= nums[i]; roman.append(rNums[i]); } } return roman.toString(); } public static void main(String[] args){ Scanner sc = new Scanner(System.in); int t = sc.nextInt(); while(t-- > 0){ int n = Integer.parseInt(sc.next().trim().substring(4, 8)); String roman = toRoman(n); Map<Character, Integer> occ = new HashMap<Character, Integer>(); occ.put('I', 0);occ.put('V', 0);occ.put('X', 0);occ.put('L', 0); occ.put('C', 0);occ.put('D', 0);occ.put('M', 0); for(int i = 0; i < roman.length(); i++){ int x = occ.get(roman.charAt(i)); occ.put(roman.charAt(i), x + 1); } for(int i = 0; i < 7; i++){ System.out.print(occ.get(literals.charAt(i))); } System.out.println(); } } }

Pokuty

Tento problém je vyhledáváním určitých vrcholů (míst) v grafu silnic a to takových, že po jejich odstranění přestane graf být souvislý (tj. nebude možné dostat se ze všech míst do všech dalších míst). Situaci komplikuje fakt, že graf může být nesouvislý už na začátku (už v zadaném grafu nebude možné dostat se z každého místa do každého jiného). V tom případě je třeba zjistit, jestli je graf po odstranění místa (vrcholu) nesouvislý více než předtím (tj. nebude možné se dostat do více vrcholů).

  1. Pro každou mapu města:
  2. Načíst si jednotlivá místa a silnice a jejich strukturu si uložit (např. do matice (dvourozměrného pole) o velikosti (počet míst x počet míst), kde jednička na pozici (i, j) bude udávat, že existuje cesta z i do j).
  3. Pomocí prohledávání do šířky z prvního vrcholu spočítat, do kolika vrcholů je možné se dostat. Pokud takto zjištěný počet odpovídá celkovému počtu vrcholů, je graf souvislý. Pokud ne, je graf nesouvislý.
  4. Bez ohledu na to, zda je souvislý nebo ne, odstranit první vrchol, provést prohledávání do šířky z druhého vrcholu a spočítat, kolik je nyní dosažitelných vrcholů. Pokud je jich o 2 a více méně než před odstraněním prvního vrcholu, je odstraněný vrchol místem, kde bude kamera. Toto místo si uložíme do pole.
  5. Celý postup zopakujeme pro odstranění druhého vrcholu a tak dále, dokud nezkusíme odstranit všechny vrcholy.
  6. Získaná místa s kamerami uložená v poli seřadíme podle abecedy a spočítáme, kolik jich je. Počet míst s kamerami a jejich seřazený seznam vypíšeme.

Příklad zdrojového kódu:

#include <algorithm> #include <cstdio> #include <map> #include <string> #include <vector> using namespace std; int n, m; char jmeno[33]; char jmeno1[33], jmeno2[33]; map<string,int> cisla; map<int,string> nazvy; vector<vector<int> > sousedi; vector<int> hladina, spojeno; vector<string> kamery; void dfs(int v, int f, int l); int main() { for(int q=1; ; q++) { scanf("%d\n", &n); if(n==0) break; cisla.clear(); nazvy.clear(); for(int i=0; i<n; i++) { scanf("%s\n", jmeno); cisla[string(jmeno)]=i; nazvy[i]=string(jmeno); } sousedi.clear(); sousedi.resize(n); scanf("%d\n", &m); for(int i=0; i<m; i++) { scanf("%s %s\n", jmeno1, jmeno2); int u, v; u=cisla[string(jmeno1)]; v=cisla[string(jmeno2)]; sousedi[u].push_back(v); sousedi[v].push_back(u); } hladina.clear(); hladina.resize(n, -1); spojeno.clear(); spojeno.resize(n, -1); kamery.clear(); dfs(0, -1, 0); sort(kamery.begin(), kamery.end()); printf("Mapa #%d: pocet kamer: %d\n", q, kamery.size()); for(int i=0; i<kamery.size(); i++) { printf("%s\n", kamery[i].c_str()); } printf("\n"); } return 0; } void dfs(int v, int f, int l) { hladina[v]=l; spojeno[v]=l; int nejnizsi=l; int synu=0; for(int i=0; i<sousedi[v].size(); i++) { int s=sousedi[v][i]; if(s==f) continue; if(hladina[s]==-1) { dfs(s, v, l+1); synu++; spojeno[v]=min(spojeno[s], spojeno[v]); } else { nejnizsi=min(hladina[s], nejnizsi); } } if(l==0) { if(synu>1) kamery.push_back(nazvy[v]); } else { if(synu>0 && spojeno[v]>=hladina[v]) kamery.push_back(nazvy[v]); } spojeno[v]=min(nejnizsi, spojeno[v]); }

Příklady

  1. Pro každý příklad:
  2. Načíst první operand, operátor a druhý operand. Oba operandy nejlépe načíst jako řetězce.
  3. Oba operandy převést na čísla (procházet vždy po dvou číslicích, první číslice udává počet, druhá číslice je přímo číslice). Výsledné číslo může být dost velké, je třeba použít dostatečný datový typ (64bitů) pro jeho uložení.
  4. Vypočítat výsledek podle toho, jaký byl zadaný operátor.
  5. Vypsat zadání a rovná se.
  6. Výsledek zakódovat a vypsat (projít ho číslici po číslici a počítat, kolik je stejných číslic, jakmile se číslice změní, vypsat počet a číslici, pokud bude počet větší než 9, vypsat 9 a číslici a pokračovat od 0)

Příklad zdrojového kódu:

import java.util.*; import java.math.*; public final class Priklady { public static BigInteger expand(String num) { BigInteger res = BigInteger.ZERO; for(int i = 0; i < num.length()/2; i++) { for(int j = 0; j < num.charAt(2*i)-'0'; j++) res = res.multiply(BigInteger.valueOf(10)).add(BigInteger.valueOf(num.charAt(2*i+1)-'0')); } return res; } public static void printres(String num) { for(int x = 0; x < num.length(); ) { int j = x+1; while(j < num.length() && num.charAt(j) == num.charAt(x)) { j++; } int cnt = j-x; while(cnt > 0) { System.out.print(Math.min(9, cnt)); System.out.print(num.charAt(x)); cnt -= 9; } x = j; } } public static void main(String[] args) { Scanner s = new Scanner(System.in); int n = s.nextInt(); for(int i = 0; i < n; i++) { String a = s.next(); String op = s.next(); String b = s.next(); System.out.print(a + " " + op + " " + b + " = "); BigInteger n1 = expand(a), n2 = expand(b); BigInteger res = BigInteger.ZERO; if(op.equals("-")) res = n1.subtract(n2); else if(op.equals("*")) res = n1.multiply(n2); else if(op.equals("+")) res = n1.add(n2); else res = n1.divide(n2); printres(res.toString()); System.out.println(); } } }

Symetrie

Tento problém je zjištěním, kolik je minimálně potřeba znaků na doplnění slova na palindrom (slovo, které se stejně čte zepředu i zezadu). Aktuální počet přidaných písmen nastavím na 0. Po načtení slova je třeba ho postupně procházet zleva i zprava. Pokud jsou na obou koncích znaky stejné, pouze přejdu na další znak vlevo i vpravo. Jinak si načtu aktuální počet přidaných písmen z pomocného pole. Pokud odeberu písmeno zprava a toto neodpovídá písmenu zleva, zvýším aktuální počet přidaných písmen o jedna a zaznamenám si ho do pomocného pole. Stejně postupuji, pokud odeberu písmeno zleva a toto neodpovídá písmenu zprava. Jakmile se indexy zleva a zprava setkají, procházení končí a vypíšu aktuální počet doplněných písmen.

Příklad zdrojového kódu:

import java.util.*; /** * * @author hynek */ public class Symetrie { private static int getSymmetry(String s){ int[][] dp = new int[s.length()][s.length()]; for(int i = 1; i < s.length(); i++){ for(int r = 0, c = i; c < s.length(); r++, c++){ dp[r][c] = s.charAt(r) == s.charAt(c) ? dp[r + 1][c - 1] : (Math.min(dp[r][c - 1], dp[r + 1][c]) + 1); } } return dp[0][s.length() - 1]; } public static void main(String[] args){ Scanner sc = new Scanner(System.in); int t = sc.nextInt(); while(t-- > 0){ String s = sc.next(); System.out.println(getSymmetry(s)); } } }

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ů.

Besídka

Je zadáno několik částek v KIV$. Úkolem je pro každou částku určit, kolika různými kombinacemi je možné danou částku poskládat s využitím bankovek a mincí ve stanovených hodnotách. Počet možných kombinací lze vyjádřit vztahem f(n, k) = f(n, k – 1) + f(n – Hk, k), kde n je částka, která se má sestavit s využitím prvních k bankovek/mincí a Hk je hodnota k-té bankovky/mince. Tento vzorec by šlo přímo rekurzivně využít, ale rekurze je příliš pomalá. Místo toho se použije tabulka o rozměrech počet bankovek/mincí x maximální částka, do které se budou ukládat mezivýsledky a místo rekurze se použije cyklus.

Postup je tedy následující:

Příklad zdrojového kódu:

#include <iostream> #include <vector> #include <algorithm> #include <cmath> #define ll long long #define ii pair< int , int > #define REP(i,a,b) for(int i=a;i<=b;i++) using namespace std; //VSE*20 ll pocty[1001][9]; int main(){//poresit 50 int i, j,n, k,p,o, l, a, b, u, w; int pom; for(i=0;i<=1000;i++){ for(j=0;j<9;j++){ pocty[i][j]=0; if(j==0) pocty[i][j]=1; } } int hmen[9]={1,2,4,10,20,40,100,200,400}; for(i=1;i<9;i++){ pocty[0][i]=1; } for(i=1;i<9;i++){ for(j=1;j<1001;j++){ pom=j; do{ pocty[j][i]+=pocty[pom][i-1]; pom-=hmen[i];// cout<<pom<<endl; }while(pom>=0); } } pocty[1000][8]++; cin >> n; float m; int bzn; while(n--){ cin >> m; bzn=m*20; cout << "Pocet ruznych variant sestaveni: " << pocty[bzn][8]<<endl; } return 0; }

Čísla

Je zadáno několik dvojic čísel. Úkolem je pro každou dvojici určit, zda jsou čísla spřátelená (tj. součet dělitelů prvního čísla včetně 1 ale bez něj samotného je roven druhému číslu a naopak):

Příklad zdrojového kódu:

var n,i,sdx,sdy,j:longint; x,y:integer; begin readln(n); for i:=1 to n do begin sdx := 0; sdy := 0; readln(x,y); if x<>1 then BEGIN for j:=1 to x-1 do begin if (x mod j = 0) then sdx := sdx + j; end; END ELSE sdx:=1; if y<>1 then BEGIN for j:=1 to y-1 do begin if (y mod j = 0) then sdy := sdy + j; end; END ELSE sdy:=1; if (x=sdy) and (y=sdx) then writeln('Ano!') else writeln('Ne.'); end; readln; end.

Mayové

Je zadáno několik slunečních soustav, u každé planety je zadána vzdálenost od středu oběhu a rychlost oběhu. Úkolem je určit dobu (ve dnech), za kterou se planety dostanou do stejné pozice, ve které se právě nacházejí. Planety obíhají svou hvězdu po kruhových drahách a den na všech planetách je stejný.

Pro každou soustavu:

Příklad zdrojového kódu:

#include <cstdio> #include <cmath> using namespace std; typedef long long ll; ll gcd(ll a, ll b){ if(b == 0) return a; return gcd(b, a%b); } int main(){ int n; scanf("%d", &n); for(int i=0;i<n;i++){ int p; scanf("%d", &p); ll *planet = new ll[p]; for(int j=0;j<p;j++){ double r, v; scanf("%lf %lf", &r, &v); planet[j] = round(acos(-1)*(r/(12.0*v))); //dny } ll vys = planet[0]; for(int j=1;j<p;j++){ ll g = gcd(vys, planet[j]); vys = (vys/g); vys *= planet[j]; } printf("%lld\n", vys); } return 0; }

MHD

Je zadáno několik sítí linek MHD a startovní a cílová zastávka. Úkolem je najít takovou cestu mezi startovní a cílovou zastávku, kdy počet přestupů je minimální a ujetá vzdálenost (v počtu přejezdů mezi zastávkami) je co největší.

Pro každou síť:

Příklad zdrojového kódu:

#include <algorithm> #include <cstdio> #include <queue> #include <set> #include <vector> using namespace std; typedef long long ll; #define pt pair<ll,ll> #define mp(x, y) make_pair((x), (y)) const ll INFTY=(1LL<<60); int q; int z, l, a, b; vector<int> linky[200005]; vector<int> ktere[300005]; int used[200005]; pt dist[300005]; char radek[3000000]; char cislo[100]; set<ll> found; queue<int> fr; void test(); int main() { scanf("%d\n", &q); for(int i=0; i<q; i++) test(); return 0; } void zlepsi(pt &a, pt b) { if((a.first>b.first) || (a.first==b.first && a.second<b.second)) a=b; } void test() { scanf("%*s %d\n", &z); scanf("%*s %d\n", &l); l*=2; scanf("%*s %d\n", &a); scanf("%*s %d\n", &b); for(int i=0; i<l; i++) used[i]=0; for(int i=0; i<z; i++) ktere[i].clear(); for(int i=0; i<l; i++) linky[i].clear(); for(int i=0; i<l/2; i++) { gets(radek); int kon=0; for(int j=0; radek[j]; j++) { if(!(radek[j]>='0' && radek[j]<='9')) { cislo[kon++]=0; int v=atoi(cislo); linky[2*i].push_back(v); ktere[v].push_back(2*i); ktere[v].push_back(2*i+1); kon=0; } else { cislo[kon++]=radek[j]; } } if(kon) { cislo[kon++]=0; int v=atoi(cislo); linky[2*i].push_back(v); ktere[v].push_back(2*i); ktere[v].push_back(2*i+1); kon=0; } linky[2*i+1]=linky[2*i]; reverse(linky[2*i+1].begin(), linky[2*i+1].end()); } scanf("\n"); for(int i=0; i<z; i++) dist[i]=mp(INFTY, INFTY); dist[a]=mp(0, 0); for(int i=0; i<ktere[a].size(); i++) { int num=ktere[a][i]; used[num]=1; fr.push(num); } while(!fr.empty()) { int akt=fr.front(); fr.pop(); found.clear(); ll prestup=INFTY; for(int i=0; i<linky[akt].size(); i++) { int v=linky[akt][i]; if(!found.empty()) { if(dist[v].first==INFTY) { dist[v]=mp(prestup+1, *(--found.end())+i); for(int k=0; k<ktere[v].size(); k++) { int num=ktere[v][k]; if(!used[num]) { used[num]=1; fr.push(num); } } } else { if(dist[v].first<prestup) { prestup=dist[v].first; found.clear(); found.insert(dist[v].second-i); } else if(dist[v].first==prestup) { found.insert(dist[v].second-i); } else { zlepsi(dist[v], mp(prestup+1, *(--found.end())+i)); } } } else if(dist[v].first!=INFTY) { prestup=dist[v].first; found.clear(); found.insert(dist[v].second-i); } } } printf("Adam %lld, Eva %lld\n", dist[b].first, dist[b].second); }

Oplocení

Je zadáno několik čtvercových růžových sadů s pozicemi růží (jedna růže na řádku). Úkolem je určit minimální délku pletiva (v metrech) potřebnou pro oplocení všech růží. Úkolem je tedy najít konvexní obálku bodů v rovině (růží).

Pro každý sad:

Příklad zdrojového kódu:

#include <cstdio> #include <cmath> #include <algorithm> using namespace std; struct bod_t { int x, y; }; bool operator<(const bod_t &a, const bod_t &b) { return a.x < b.x || (a.x == b.x && a.y < b.y); } bod_t body[10000]; bod_t konvexni_obal[10000]; long long vektorovy_soucin(bod_t a, bod_t b, bod_t c) { long long a1 = b.x - a.x, a2 = b.y - a.y, b1 = c.x - a.x, b2 = c.y - a.y; return a1 * b2 - a2 * b1; } int main(int argc, char** argv) { int t; scanf("%d", &t); while (t--) { int n; scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%d", &body[i].x); body[i].y = i; } sort(body, body + n); int k = 0; for (int i = 0; i < n; i++) { while (k >= 2 && vektorovy_soucin(konvexni_obal[k-2], konvexni_obal[k-1], body[i]) <= 0) k--; konvexni_obal[k++] = body[i]; } int konec_horniho_obalu = k; for (int i = n-1; i >= 0; i--) { while (k >= konec_horniho_obalu + 1 && vektorovy_soucin(konvexni_obal[k-2], konvexni_obal[k-1], body[i]) <= 0) k--; konvexni_obal[k++] = body[i]; } double obvod = 0; for (int i = 0; i < k - 1; i++) { bod_t a = konvexni_obal[i], b = konvexni_obal[i+1]; double dx = b.x - a.x, dy = b.y - a.y; obvod += sqrt(dx * dx + dy * dy); //printf("# %d %d, %d %d\n", a.x, a.y, b.x, b.y); } //printf("# %lf\n", obvod); printf("%lld\n", (long long) round(obvod)); } }