PilsProg 2017

Výsledky kvalifikace

#JménoPříjmeníSplněných úlohČasFinále
1FilipBialas65,965Postupuje do finále
2JakubJirkal6352,613Postupuje do finále
3JakubŠilhavý61 206,059Postupuje do finále
4PetrŠíma61 640,627Postupuje do finále
5MilanHotovec61 830,123Postupuje do finále
6FrantišekDeckert61 991,878Postupuje do finále
7RadekBělohlávek62 112,616Postupuje do finále
8VáclavVolhejn63 196,569Postupuje do finále
9RichardHladík51 223,607Postupuje do finále
10MartinHubata51 386,381Postupuje do finále
11RadekOlšák52 723,300Postupuje do finále
12JanKaifer52 734,705Postupuje do finále
13LenkaKopfová52 904,739Postupuje do finále
14JanBouček53 081,763Postupuje do finále
15JanHeller4706,745-
16MichaelBosák41 027,459-
17MartinJandík41 681,943-
18Nguyen DongMilan41 774,230-
19MartinProcházka373,442-
20PetrKotáb3661,506-
21Filip Čermák31 660,217-
22VeronikaHladíková32 069,903-
23JanŠimerda267,275-
24KarelPatlejch2134,597-
25VáclavČermák2797,257-
26DanilKoževnikov21 155,675-
27MichalPřevrátil16,758-
28MilanBorový17,591-
29DanielCiepluch121,741-
30DavidŠkarda150,515-
31OndřejLošťák1124,830-
32DanielHladký1382,348-
33KláraCihlářová1390,354-

Výsledky finále

#JménoPříjmeníSplněných úlohČas
1FilipBialas56,235
2VáclavVolhejn57,373
3RichardHladík57,590
4JanBouček36,478
5JakubJirkal23,077
6FrantišekDeckert26,525
7RadekOlšák10,574
8JakubŠilhavý11,148
9RadekBělohlávek11,251
10MartinHubata11,525
11LenkaKopfová11,585
12JanKaifer12,243
13PetrŠíma12,496
14MilanHotovec13,022

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ů
AxB170126
AplusB170222
Největší ze tří celých čísel170320
Pascalův trojúhelník170415

Kvalifikační úlohy

NázevČísloÚspěšných řešitelů
Hlasování171133
Podnikatel171216
Tvorba textu171325
Velehory171422
Vzpoura strojů171510
Zabezpečení171615

Finálové úlohy

NázevČísloÚspěšných řešitelů
Dokonalá zpráva17214
Drony17226
Robožába17233
Superpohár172414
Vosa17253

A jaké bylo finále?

Finále začíná ...

Harmonogram PilsProg 2017

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.

Hlasování

  1. Pro každou fakultu (testovací případ) načíst počet skupin a počty členů jednotlivých skupin.
  2. Počty členů jednotlivých skupin seřadit vzestupně (od nejmenšího k největšímu).
  3. Pro každou z prvních (s / 2) + 1 skupin spočteme nadpoloviční počet jejích členů jako (ai / 2) + 1.
  4. Sumu těchto počtů vypsat na samostatnou řádku jako výsledek pro danou fakultu.

Příklad zdrojového kódu:

/* * To change this license header, choose License Headers in Project Properties. * To change this template file, choose Tools | Templates * and open the template in the editor. */ package pp1; import java.util.Arrays; import java.util.Scanner; /** * * @author Martin */ public class PP1 { /** * @param args the command line arguments */ public static void main(String[] args) { Scanner sc = new Scanner(System.in); int rpt = sc.nextInt(); for(int i = 0; i < rpt; i++){ int skupin = sc.nextInt(); int[] skupiny = new int[skupin]; for(int k = 0; k < skupin; k++){ skupiny[k] = sc.nextInt(); } Arrays.sort(skupiny); int res = 0; for(int k = 0; k < (skupin-1)/2+1; k++){ res = res + (skupiny[k]-1)/2+1; } System.out.println(res); } } }

Podnikatel

  1. Pro každý testovací případ načíst souřadnice jednotlivých časových pásem (důležité jsou souřadnice x, protože pásmo vždy zabírá celou výšku (y) mapy), počet hodin dne a jména a souřadnice jednotlivých měst.
  2. Seřadit časová pásma podle souřadnic x jejich levých horních rohů.
  3. Pro každý dotaz načíst čas ve formátu HH:MM, název výchozího a cílového města.
  4. Sekvenčním vyhledáváním v poli měst najít podle názvů souřadnice obou měst.
  5. Podle souřadnic x měst zjistit indexy časových pásem, ve kterých se města nacházejí.
  6. Čas ve výchozím městě převést na minuty. Spočítat časový rozdíl mezi pásmy v minutách jako rozdíl indexů časových pásem cílového a výchozího města násobených 30 (časové pásmo má „šířku“ 30 minut).
  7. Pokud je rozdíl záporný a součet rozdílu v minutách a času ve výchozím městě v minutách je rovněž záporný, přičíst počet minut za den.
  8. Výsledný čas v minutách převést do formátu HH:MM (použít zbytek po dělení počtem hodin jednoho dne) a vypsat na samostatnou řádku

Příklad zdrojového kódu:

program podnikatel; uses sysutils; var pasma, mesta_pozice:array of integer; mesta_jmeno:array of string; s,v,h,m,x1,y1,x2,y2,x,y,index1,index2,vysl,t,k,l,d:integer; n,n1,n2:string[22]; cas:string[5]; mezera,znak:char; procedure QuickSort(var A: array of integer; l, r: integer); var i, j, k, x: integer; begin i:=l; j:=r; k:=A[(i+j) div 2]; { volba pivota } repeat while A[i]<k do i:=i+1; while A[j]>k do j:=j-1; if i<=j then begin x:=A[i]; A[i]:=A[j]; A[j]:=x; i:=i+1; j:=j-1; end; until i >= j; if j>l then QuickSort(A, l, j); if i<r then QuickSort(A, i, r); end; function najdi(mesto:string):integer; var o:integer; begin o:=0; while mesto<>mesta_jmeno[o] do o:=o+1; najdi:=o; end; function vzdalenost(pozice1,pozice2:integer):integer; var o,p:integer; begin o:=0; p:=0; while pozice1>pasma[o] do o:=o+1; while pozice2>pasma[p] do p:=p+1; //writeln(pozice1,pozice2,o,p,p-o); vzdalenost:=p-o; end; begin readln(t); for k:=1 to t do begin read(s,v,h,m); setlength(pasma,2*h); for l:=0 to (2*h)-1 do begin read(x1,y1,x2,y2); pasma[l]:=x2; end; QuickSort(pasma,0,(2*h)-1); setlength(mesta_pozice,m); setlength(mesta_jmeno,m); for l:=0 to m-1 do begin readln(x,y,mezera,n); mesta_pozice[l]:=x; mesta_jmeno[l]:=n; end; readln(d); for l:=1 to d do begin read(cas); n1:=''; read(znak); read(znak); while znak<>' ' do begin n1:=n1+znak; read(znak); end; readln(n2); index1:=najdi(n1); index2:=najdi(n2); vysl:=strtoint(cas[1..2])*60+strtoint(cas[4..5]); vysl:=vysl+vzdalenost(mesta_pozice[index1],mesta_pozice[index2])*30; while vysl div 60 >= h do vysl:=vysl-h*60; while vysl < 0 do vysl:=vysl+h*60; writeln(Format('%.2d',[vysl div 60]),':',Format('%.2d',[vysl mod 60])); end; end; end.

Tvorba textu

  1. Pro každého studenta (testovací případ) načíst počáteční text a jednotlivá pravidla (pro každé pravidlo pozici v textu pi a délku podřetězce di).
  2. Pro každé pravidlo zjistit podřetězec začínající na pozici pi výchozího textu (pro první pravidlo počátečního textu, pro další pravidla počátečního textu ovlivněného předchozími pravidly) a končící před pozicí pi + di.
  3. V tomto podřetězci převrátit pozice znaků (tj. nultý znak se stane posledním, první znak předposledním atd.).
  4. Výsledný převrácený podřetězec vložit na pozici pi + di výchozího textu (tj. výchozí řetězec na této pozici rozdělit na začátek a konec a následně provést zřetězení začátek + převrácený podřetězec + konec.

Příklad zdrojového kódu:

#include <iostream> #include <string> #include <algorithm> using namespace std; int main() { int pripady; cin >> pripady; while (pripady-->0) { string s; cin >> s; int pocet; cin >> pocet; int** pravidla = new int*[2]; for (int i = 0; i<2; i++) { pravidla[i] = new int[pocet]; } for (int i = 0; i<2; i++) { for (int j = 0; j<pocet; j++) { cin >> pravidla[i][j]; } } for (int i = 0; i < pocet; i++) { string pom = ""; for (int j = 0; j < pravidla[1][i]; j++) { pom += s[pravidla[0][i]+pravidla[1][i]-1-j]; } s.insert(pravidla[0][i]+pravidla[1][i], pom); } cout << s<<endl; } return 0; }

Velehory

  1. Pro každý testovací případ načíst body (souřadnice x a y), které představují vrcholy a údolí pohoří.
  2. Protože body nemusejí být zadány uspořádané, seřadit body podle jejich souřadnice x vzestupně.
  3. Po seřazení se vždy střídá vrchol a údolí, pole bodů se tedy bude procházet po dvojicích od konce (slunce svítí zprava) až do začátku. Poslední bod (kterým procházení začíná) je údolí a předposlední bod je vrchol.
  4. Pro každé údolí a vrchol spočítat průsečík úsečky údolí - vrchol s aktuální hladinou stínu (souřadnice y zatím nejvyššího vrcholu, na začátku je rovna nule). Spočítat délku úseku jako vzdálenost vrcholu a průsečíku.
  5. Sumu všech úseků po průchodu celého pole vypsat na samostatnou řádku na dvě desetinná místa.

Příklad zdrojového kódu:

#include <stdio.h> #include <string.h> #include <math.h> long bodx[100]; long body[100]; void sort(int n) { int done=0, i; long h1, h2; while (done == 0) { done = 1; for (i = 0; i < n-1; i++) { if (bodx[i]<bodx[i+1]) { h1 = bodx[i]; h2 = body[i]; bodx[i] = bodx[i+1]; body[i] = body[i+1]; bodx[i+1] = h1; body[i+1] = h2; done = 0; } } } return; } int main() { int t, b, i, j, y, silencer; double count; silencer = scanf("%d\n", &t); for (;t-->0;) { silencer = scanf("%d\n", &b); for (i = 0 ; i < b; i++) { silencer = scanf("%ld %ld\n", &bodx[i], &body[i]); } sort(b); count = 0; y = 0; for (i = 0; i < b; i++) { if (body[i] > y) { count += ((body[i] - y) * sqrt(pow(body[i]-body[i-1], 2) + pow(bodx[i-1]-bodx[i], 2))) / (body[i]-body[i-1]); y = body[i]; } } printf("%.2f\n", count); } return 0; }

Vzpoura strojů

  1. Načíst souřadnice a poloměry síní a uložit si je do dvourozměrného pole (souřadnice jsou celočíselné, pole bude mít maximálně 500 x 500 buněk).
  2. Pro každý dotaz načíst souřadnice počátečního a koncového bodu cesty (tj. úsečky)
  3. Podle souřadnic bodů úsečky určit buňky pole síní, které jsou poblíž úsečky. Lze rozdělit na několik případů - vodorovná a svislá úsečka (pouze buňky přímo pod úsečkou) a šikmá úsečka (buňky pod úsečkou a buňky těsně sousedící s úsečkou - body do vzdálenosti 1.0 od úsečky).
  4. Pouze u takto nalezených buněk zjistit, zda v dané buňce je síň. Pouze, pokud v buňce síň je, zjistit, zda se síň (kružnice) dotýká cesty (úsešky) nebo protíná cestu (úsečku). Pokud ano, inkrementovat čítač počtu síní.
  5. Vypsat čítač počtu síní na samostatnou řádku.

Příklad zdrojového kódu:

/* * To change this license header, choose License Headers in Project Properties. * To change this template file, choose Tools | Templates * and open the template in the editor. */ import java.util.Scanner; /** * * @author rada */ public class Krtek { /** * @param args the command line arguments */ public static void main(String[] args) { Scanner sc = new Scanner(System.in); int circleCount = sc.nextInt(); Circle[] circles = new Circle[circleCount]; for (int i = 0; i < circleCount; i++) { int x = sc.nextInt(); int y = sc.nextInt(); int r = sc.next().charAt(2) - 48; circles[i] = new Circle(x, y, r); } int lineCount = sc.nextInt(); Line[] lines = new Line[lineCount]; for (int i = 0; i < lineCount; i++) { int x1 = sc.nextInt(); int y1 = sc.nextInt(); int x2 = sc.nextInt(); int y2 = sc.nextInt(); lines[i] = new Line(x1, x2, y1, y2); } for (Line line : lines ) { int a = line.Y2 - line.Y1; int b = line.X1 - line.X2; double c = (-a * line.X1) + (-b * line.Y1); double denominator = Math.sqrt(a * a + b * b); int x1, x2, y1, y2; if (line.X1 < line.X2) { x1 = line.X1; x2 = line.X2; } else { x1 = line.X2; x2 = line.X1; } if (line.Y1 < line.Y2) { y1 = line.Y1; y2 = line.Y2; } else { y1 = line.Y2; y2 = line.Y1; } int hitCount = 0; for (Circle circle : circles) { if ((circle.X >= x1) && (circle.X <= x2) && (circle.Y >= y1) && (circle.Y <= y2)) { double distance = Math.abs(a * circle.X + b * circle.Y + c) / denominator; if (distance <= circle.R) { hitCount++; } } } System.out.println(hitCount); } } static class Circle { public int X; public int Y; public double R; public Circle(int x, int y, int r) { this.X = x; this.Y = y; this.R = r / 10.0; } } static class Line { public int X1; public int X2; public int Y1; public int Y2; public Line(int x1, int x2, int y1, int y2) { this.X1 = x1; this.X2 = x2; this.Y1 = y1; this.Y2 = y2; } } }

Zabezpečení

  1. Vytvořit si pole o velikosti 10 000 indikující, zda daný index je či není prvočíslo s využitím Eratosthenova síta. Toto pole se využije ve všech testovacích případech.
  2. Pro každý testovací případ načíst počáteční a koncovou kombinaci zámku.
  3. Najít nejkratší cestu mezi počáteční a koncovou kombinací, přičemž přípusné jsou pouze prvočíselné kombinace zámku a změny pouze v jedné cifře (lze např. využitím grafu, ve kterém jednotlivá prvočísla jsou vrcholy a přechody mezi nimi, změnou jedné číslice, jsou hrany).
  4. Vypsat délku cesty (počet hran grafu) na samostatnou řádku.

Příklad zdrojového kódu:

#include <iostream> #include <algorithm> #include <cmath> #include <vector> bool prime[10000]; void setPrimes() { prime[0] = prime[1] = false; for(int i=2;i<10000;i++) if(prime[i]) for(int k=2;k*i<10000;k++) prime[k*i]=false; } int findRes(int start, int goal) { int reached[10000]; for(int i=0;i<10000;i++) reached[i]=false; reached[start] = true; if(start==goal) return 0; std::vector<int> f; std::vector<int> o; f.push_back(start); for(int x=0;;x++) { for(int n=0;n<f.size();n++) { for(int i=1;i<10000;i*=10) { int tmp = f[n]; tmp-=((tmp/i)%10)*i; for(int d=0;d<10;d++) { if(tmp+(d*i)==goal) return x+1; if(prime[tmp+(d*i)] && reached[tmp+(d*i)] == false) { reached[tmp+(d*i)]= true; o.push_back(tmp+(d*i)); } } } } std::swap(f,o); o.clear(); } } int main(){ for(int i=0;i<10000;i++) prime[i]=true; setPrimes(); int T; std::cin >> T; while(T--) { int a, b; std::cin >> a >> b; std::cout << findRes(a, b) << std::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ů.

Dokonalá zpráva

  1. Pro každou zprávu (testovací případ) načíst maximální počet řádků výsledné dokonalé zprávy a počet slov.
  2. Načítat jednotlivá slova a do pole si zaznamenat jejich délky.
  3. Pokud je počet řádků větší nebo roven počtu slov, vrátit délku nejdelšího slova jako výsledek.
  4. Pokud je počet řádků menší než počet slov, vytvořit funkci, která pro zadanou maximální délku řádky vrátí počet řádek.
  5. Pomocí binárního vyhledávání (půlením intervalu) a této metody najít takovou maximální délku řádky, při které se zpráva vejde na maximální počet řádek a zároveň je maximální délka řádky co nejmenší.
  6. Tuto hodnotu vypsat na samostatnou řádku.

Příklad zdrojového kódu:

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Objects; /** * Created by pilsprog on 01.04.2017. */ public class ProblemA { static int[] text; static int maxLines; public static void main(String[] args) { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); try { int t = Integer.parseInt(br.readLine()); for (int i = 0; i < t; i++) { String[] split = br.readLine().split(" "); maxLines = Integer.parseInt(split[0]); int s = Integer.parseInt(split[1]); String message = br.readLine(); String[] wwords = message.split(" "); int ind = 0; text = new int[s]; for (int j = 0; j < wwords.length; j++) { if (!Objects.equals(wwords[j].trim(), "")) { text[ind] = wwords[j].length(); ind++; } } int maxLen = 0; for (int j = 0; j < text.length; j++) { if (text[j] > maxLen) maxLen = text[j]; } int l = maxLen; int r = message.length(); int mid = 0; while (true) { mid = (l + r) / 2; int tr = tryCut(mid); //System.out.println(l + " " + r); // System.out.println("mid: " + mid + " res: " + tr); if (tr == -1) { l = mid + 1; } else { r = mid; } if (l == r) break; } //System.out.println("fin " +l + " " + r); System.out.println(tryCut(l)); /*System.out.println("trying"); for (int j = l; j < 20; j++) { System.out.println(tryCut(j)); }*/ } } catch (IOException e) { e.printStackTrace(); } } public static int tryCut(int maxlen) { int max = 0; int lines = 0; int curl = text[0]; //System.out.println("maxlen " + maxlen); for (int i = 1; i < text.length; i++) { //System.out.println("word" + text[i]); if (curl + 1 + text[i] <= maxlen) { curl += 1 + text[i]; } else { // System.out.println("curl " + curl); if (curl > max) max = curl; lines++; curl = text[i]; } } if (curl > max) max = curl; lines++; //System.out.println("res: lines: " + lines + " max: " + max); if (lines > maxLines) { return -1; } return max; } }

Drony

  1. Pro každou hru (testovací případ) načíst ceny jednotlivých dronů do pole.
  2. Pole nijak neřadit - pořadí dronů nelze měnit, volbou množství je však možné určit, které drony si prodávající ponechá. Rozhodnutí na začátku však mají vliv na to, co připadne prodávajícímu na konci, je tedy potřeba postupovat od konce.
  3. Je vhodné využít dynamické programování. Vytvořit si pole o (počet dronů + 6) prvcích a jeho prvky nastavit na 0. Od konce postupně procházet jednotlivé ceny dronů a do připraveného pole ukládat nejvyšší možné celkové ceny při výběru 1, 2 nebo 3 dronů. V každém kroku prověřit všechny možnosti s přičtením odpovídající předchozí hodnoty z pole (tj. o 2, 4, nebo 6 hodnot dále).
  4. Výsledek vyjde v prvním prvku pole (tj. na indexu 0). Tento výsledek vypsat na samostatnou řádku.

Příklad zdrojového kódu:

#include <stdio.h> #include <vector> #include <set> #include <queue> #include <algorithm> #include <string> #include <iostream> #include <cmath> using namespace std; /* run this program using the console pauser or add your own getch, system("pause") or input loop */ long int pole[100000]; long long int cache[100000]; int d; long long int hra(int count); int main(void) { int h; scanf("%i",&h); for (int i=0;i<h;i++) { for (int j=0;j<100000;j++) { cache[j]=-1; } scanf("%i",&d); int x; for (int j=0;j<d;j++) { scanf("%i",&x); pole[j]=x; } long long int vysl = hra(0); printf("%lli\n",vysl); } return 0; } long long int hra(int count) { if (count>=d) return 0; else if (cache[count]!=-1) return cache[count]; else if (count+3 <= d) return cache[count]=max(max(pole[count]+hra(count+2),pole[count]+pole[count+1]+hra(count+4)),pole[count]+pole[count+1]+pole[count+2]+hra(count+6)); else if (count+2 <= d) return cache[count]=max(pole[count]+hra(count+2),pole[count]+pole[count+1]+hra(count+4)); else if (count+1 <= d) return cache[count]=pole[count]+hra(count+2); }

Robožába

  1. Pro každý testovací případ načíst počet leknínů, doskok žáby, x a y souřadnice startovní pozice žáby a x a y souřadnice cílové pozice žáby. Načíst x a y souřadnice a poloměr všech leknínů.
  2. Podle doskoku žáby a vzdálenosti a poloměrů jednotlivých leknínů zkonstruovat graf, kde vrcholy jsou jednotlivé lekníny a hrany (ohodnocené vzdáleností leknínů mínus jejich poloměry zaokrouhlenou na nejbližší vyšší celé číslo) spojují lekníny, mezi kterými žába doskočí. Pro urychlení této náročné operace lze umístit lekníny do mřížky a zjišťovat existenci hran pouze u sousedních leknínů.
  3. Pro určení celkového množsví energie je potřeba najít nejkratší cestu mezi počátečním a koncovým leknínem. Na to lze využít Dijkstrův algoritmus.
  4. Pokud startovní a/nebo cílová pozice žáby leží mimo leknín, je potřeba připočítat vzdálenost pozic od nejbližších leknínů a mezi těmito lekníny hledat nejkratší cestu.
  5. Pokud cesta neexistuje, nebo je nejbližší leknín ke startovní/cílové pozici žáby dále, než je doskok žáby, vypsat na samostatnou řádku -1. Jinak vypsat délku celkové množství spotřebované energie.

Příklad zdrojového kódu:

#include <iostream> #include <vector> #include <cmath> #include <algorithm> #include <string> #include <set> #include <map> #include <queue> #include <stack> #include <cstring> #include <cassert> using namespace std; #define rep(i,a,n) for (int i=a;i<(n);i++) #define per(i,a,n) for (int i=(n)-1;i>=(a);i--) template<typename T> ostream& operator<<(ostream& s, vector<T> t) {rep(i, 0, t.size()) s << (i ? " " : "") << t[i]; return s;} template<typename T> istream& operator>>(istream& s, vector<T> &t) {rep(i, 0, t.size()) s >> t[i]; return s;} template<typename T, typename U> ostream& operator<<(ostream& s, pair<T,U> t) {s << t.first << "/" << t.second; return s;} template<typename T, typename U> istream& operator>>(istream& s, pair<T,U> &t) {s >> t.first >> t.second; return s;} typedef long long ll; typedef pair<int,int> pt; #define x first #define y second double distance(pt & a, pt & b) { return hypot(a.x - b.x, a.y - b.y); } const int N = 100010; const int DIV = 100; const ll INF = 1e17; vector<pair<int,ll>> g[N]; pt getTile(pt& a) { return {a.x/DIV,a.y/DIV}; } int dijkstra(int n) { set<pair<int,ll>> q; q.insert({n, 0}); vector<ll> dist(n+2,INF); dist[n] = 0; while(!q.empty()){ int a; ll cd; tie(a, cd) = *q.begin(); q.erase(q.begin()); //cout << a << " at distance " << cd << endl; if(a == n+1){ return cd; } for(auto e : g[a]) { int b; ll jd; tie(b, jd) = e; if(cd+jd<dist[b]) { if(dist[b] != INF) { q.erase({b, dist[b]}); } dist[b] = cd+jd; q.insert({b, dist[b]}); } } } return -1; } int main() { ios_base::sync_with_stdio(false); int n; while(cin>>n) { rep(i,0,N) g[i].clear(); int d, x0, y0, x1, y1; cin>>d>>x0>>y0>>x1>>y1; vector<pt> a(n); vector<ll> r(n); rep(i,0,n) { cin>>a[i]>>r[i]; } auto cost = [&](int i, int j){ return max(0ll, (ll)ceil(distance(a[i], a[j]) - r[i] - r[j])); }; map<pt,vector<int>> m; rep(i,0,n) { m[getTile(a[i])].push_back(i); } rep(i,0,n) { pt tile = getTile(a[i]); rep(dx, -1, 2) rep(dy, -1, 2) { pt curTile = {tile.x+dx,tile.y+dy}; if(m.count(curTile)){ for(auto j : m[curTile]) { if(i==j) continue; if(cost(i, j) <= d) { g[i].push_back({j,cost(i, j)}); } } } } } a.push_back({x0,y0}); r.push_back(0); a.push_back({x1,y1}); r.push_back(0); rep(i,0,n) { if(cost(i, n) <= d) { g[n].push_back({i, cost(i,n)}); } if(cost(i, n+1) <= d) { g[i].push_back({n+1, cost(i,n+1)}); } } if(cost(n, n+1) <= d) g[n].push_back({n+1, cost(n, n+1)}); //rep(i,0,n+2) cout << i <<": "<< g[i] <<endl; cout << dijkstra(n) << endl; } }

Superpohár

  1. Pro každou situaci (testovací případ) načíst počet útočících a bránících hráčů. Načíst vzdálenosti útočících a bránících hráčů od brankové čáry do dvou polí.
  2. Projít pole vzdáleností útočících hráčů a najít nejmenší vzdálenost od brankové čáry.
  3. Projít pole vzdáleností bránících hráčů a spočítat počet bránících hráčů, kteří jsou blíže než nejližší útočící hráč
  4. Pokud je tento počet menší než dva, vypsat „ano“, jinak vypsat „ne“ na samostatnou řádku.

Příklad zdrojového kódu:

#include <iostream> #include <vector> #include <algorithm> int main() { int T; std::cin >> T; while(T--) { std::vector<int> u,o; int a,b; std::cin >> a >> b; for(int i=0;i<a;i++) { int tmp; std::cin >> tmp; u.push_back(tmp); } for(int i=0;i<b;i++) { int tmp; std::cin >> tmp; o.push_back(tmp); } std::sort(u.begin(),u.end()); std::sort(o.begin(),o.end()); if(o[0] <= u[0] && o[1] <= u[0]) std::cout << "ne" << std::endl; else std::cout << "ano" << std::endl; o.clear(); u.clear(); } }

Vosa

  1. Načíst x a y souřadnice jednotlivých rohů podstavy krabice (tj. čtverce o hraně 5).
  2. Vosa se může nacházet v libolném místě objemu krabice s výjimkou objemu kostky. Očekávaný počet puntíků viditelných z její pozice lze určit jako pravděpodobnost p = 1p1 + 2p2 + 3p3 + 4p4 + 5p5 + 6p6, kde pi jsou pravděpodobnosti viditelnosti jednotlivých stěn kostky (a jedním až šesti puntíků).
  3. Jednotlivé pravděpodonosti lze určit jako objem krabice, ze kterého je daná stěna viditelná dělený celkovým objemem krabice mínus objem kostky. Výjimkou je pravděpodobnost p2, která je rovna 0 (kostka leží na stěně se dvěma puntíky).
  4. Vypsat výslednou pravděpodovnost p na samostatnou řádku.

Příklad zdrojového kódu:

#include <bits/stdc++.h> using namespace std; #define ll long long #define ld double #define FOR(i, n) for (int i=0; i<n; i++) const ld konst = .5; pair <ld, ld> v[4]; void rotuj(void) { FOR(i, 4) v[i] = {v[i].second, -v[i].first}; } bool spravne(pair <ld, ld> bod) { return bod.first >= konst; } pair <ld, ld> prusecik(pair <ld, ld> a, pair <ld, ld> b) { pair <ld, ld> u = {b.first - a.first, b.second - a.second}; // a + t * u; pro t = 1 mame bod b // a.first + t * u.first = konst; ld t = (konst - a.first) / u.first; return {a.first + t * u.first, a.second + t * u.second}; } ld spocti(pair <ld, ld> a, pair <ld, ld> b, pair <ld, ld> c) { pair <ld, ld> u = {b.second - a.second, b.first - a.first}, w = {c.first - a.first, c.second - a.second}; return abs(u.first * w.first - u.second * w.second) / 2; } ld vyres(void) { vector <pair <ld, ld> > body; FOR(i, 4){ if (spravne(v[i])) body.push_back(v[i]); int j = i + 1; j %= 4; if (spravne(v[i]) != spravne(v[j])) body.push_back(prusecik(v[i], v[j])); } /* for (pair <ld, ld> p: body) printf("%lf %lf\n", p.first, p.second); printf("\n"); */ assert(body.size() > 2); ld res = 0; FOR(i, body.size()) res += spocti(body[0], body[i], body[(i + 1) % body.size()]); // printf("%lf\n", res); return res; } int main(void) { ld celkem = 5 * 5 * 5 - 1; const int p[] = {3, 6, 4, 1}; FOR(i, 4) scanf("%lf %lf", &v[i].first, &v[i].second); ld sum = 4 * 5 * 5 * 5; FOR(i, 4) sum += p[i] * vyres() * 5, rotuj(); printf("%lf\n", sum / celkem); }