PilsProg 2016

Výsledky kvalifikace

PříjmeníJménoSplněných úlohČasFinále
VolhejnVáclav610,351postupuje do finále
BoučekJan683,120postupuje do finále
HladíkRichard688,231postupuje do finále
JirkalJakub6124,245postupuje do finále
LukešVojtěch6700,920postupuje do finále
BialasFilip516,104postupuje do finále
PřevrátilMichal563,979postupuje do finále
ProcházkaMartin5160,336postupuje do finále
PatlejchKarel5206,823postupuje do finále
RozlivekJakub5409,147postupuje do finále
SchutzPetr51 553,307postupuje do finále
ScheubreinMartin52 113,088postupuje do finále
HubataMartin52 185,506postupuje do finále
RybaMartin52 432,502postupuje do finále
HotovecMilan52 580,685postupuje do finále
ŠilhavýJakub52 605,548postupuje do finále
RousRadek42 140,285
PavlátkaZdeněk311,381
BrunaMartin3138,216
KladívkoMilan3140,824
ŠimerdaJan232,413
BělohlávekRadek21 120,776
StrnadDavid11,474
KasalickáKateřina16,049
BoušeMartin177,230

Výsledky finále

PříjmeníJménoSplněných úlohČas
VolhejnVáclav53,859
BialasFilip57,219
HladíkRichard59,039
LukešVojtěch47,436
BoučekJan36,109
RozlivekJakub36,170
ScheubreinMartin36,374
JirkalJakub36,604
PřevrátilMichal21,913
ŠilhavýJakub23,371
PatlejchKarel11,190
HotovecMilan11,260
HubataMartin11,318
ProcházkaMartin11,346
SchutzPetr11,567
RybaMartin14,324

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

Ilustrační úlohy:

NázevOznačeníÚspěšných řešitelů
AxB070430
AplusB080525
Největší ze tří celých čísel080621
Pascalův trojúhelník070316

Kvalifikační úlohy:

NázevOznačeníÚspěšných řešitelů
Zrzečka161622
Vyšetřování161516
Řezání kmenů16147
Fibonacciho šifra161322
Bludiště161218
ASCII art161120

Finálové úlohy:

NázevOznačeníÚspěšných řešitelů
Bobr162110
Drakiáda16223
Jídelna162315
Lupiči a četníci16245
Mraveniště16258

A jaké bylo finále?

Finále začíná ...

Harmonogram PilsProg 2016

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.

ASCII art

  1. Načíst 7 řádek ze vstupu do pole řetězců.
  2. Pro každé číslo zapsané ASCII artem si stanovit pozice, podle kterých se dá jednozněčně určit, o jaké číslo (či znaménko +) se jedná. Projít celý vstup po skocích odpovídajícíh šířce znaku v ASCII artu (6 pozic včetně mezery mezi znaky) a rozpoznat tak všechny číslice a znaménko +.
  3. Z rozpozanných číslic postupně konstruovat první sčítanec, dokud nepřijde zanémko +. Po něm začít konstruovat druhý sčítanec.
  4. Provést sečtení sčítanců.
  5. Výsledek vypsat pomocí ASCII artu za použití předpřipravených ASCII art obrazů jednotlivých číslic (např. v dvourozměrném poli znaků či poli řetězců).

Příklad zdrojového kódu:

import java.util.*; public class ASCII { static Scanner sc = new Scanner(System.in); static final String[][] CHARS = {{ "xxxxx", "x...x", "x...x", "x...x", "x...x", "x...x", "xxxxx"},{ "....x", "....x", "....x", "....x", "....x", "....x", "....x"},{ "xxxxx", "....x", "....x", "xxxxx", "x....", "x....", "xxxxx"},{ "xxxxx", "....x", "....x", "xxxxx", "....x", "....x", "xxxxx"},{ "x...x", "x...x", "x...x", "xxxxx", "....x", "....x", "....x"},{ "xxxxx", "x....", "x....", "xxxxx", "....x", "....x", "xxxxx"},{ "xxxxx", "x....", "x....", "xxxxx", "x...x", "x...x", "xxxxx"},{ "xxxxx", "....x", "....x", "....x", "....x", "....x", "....x"},{ "xxxxx", "x...x", "x...x", "xxxxx", "x...x", "x...x", "xxxxx"},{ "xxxxx", "x...x", "x...x", "xxxxx", "....x", "....x", "xxxxx"},{ ".....", "..x..", "..x..", "xxxxx", "..x..", "..x..", "......"}}; private static int calculateFromASCII() { int nOfCharacters = 0; String[] lines = new String[7]; for (int i = 0; i < lines.length; i++) { lines[i] = sc.nextLine(); } nOfCharacters = (int) Math.ceil(lines[0].length() / 6.0); //System.out.println(nOfCharacters + "("+ lines[0].length() +")"); int plusPos = 0; String[][] chars = new String[nOfCharacters][7]; for (int i = 0; i < chars.length; i++) { //System.out.println("nCharacter "+ i +": "); for (int j = 0; j < chars[i].length; j++) { chars[i][j] = lines[j].substring(i*6, (i+1)*6 -1); //System.out.println("ln:"+j +" "+ chars[i][j]); //System.out.print("--CHECK-- "+ chars[i][j] +" == "+ CHARS[10][1]); //System.out.println(" : "+ chars[i][j].equals(CHARS[10][1])); if (chars[i][j].equals(CHARS[10][1])) { plusPos = i; //System.out.println("PLUUUS"); } } } /** * nOfChars = 11 * plusPos = 8 * nOfChars - plusPos = 3 * */ int[] n = {0, 0}; byte ind = 0; int factor = plusPos-1; for (int i = 0; i < chars.length; i++) { //System.out.println("FACTOR: "+ factor); if (Arrays.equals(chars[i], CHARS[0])) { // zeroes are basically useless } else if (Arrays.equals(chars[i], CHARS[1])) { n[ind] += 1 * Math.pow(10, factor); } else if (Arrays.equals(chars[i], CHARS[2])) { n[ind] += 2 * Math.pow(10, factor); } else if (Arrays.equals(chars[i], CHARS[3])) { n[ind] += 3 * Math.pow(10, factor); } else if (Arrays.equals(chars[i], CHARS[4])) { n[ind] += 4 * Math.pow(10, factor); } else if (Arrays.equals(chars[i], CHARS[5])) { n[ind] += 5 * Math.pow(10, factor); } else if (Arrays.equals(chars[i], CHARS[6])) { n[ind] += 6 * Math.pow(10, factor); } else if (Arrays.equals(chars[i], CHARS[7])) { n[ind] += 7 * Math.pow(10, factor); } else if (Arrays.equals(chars[i], CHARS[8])) { n[ind] += 8 * Math.pow(10, factor); } else if (Arrays.equals(chars[i], CHARS[9])) { n[ind] += 9 * Math.pow(10, factor); } if (factor <= 0) { factor = nOfCharacters - plusPos; ind++; } factor--; } //System.out.println("A: "+ n[0]); //System.out.println("B: "+ n[1]); return n[0] + n[1]; } private static void printIntAsASCII(int n) { String nStr = String.valueOf(n); for (int i = 0; i < 7; i++) { for (int j = 0; j < nStr.length(); j++) { int num = Integer.parseInt(nStr.charAt(j)+""); System.out.print(CHARS[num][i]); if (j < nStr.length()-1) { System.out.print("."); } } System.out.println(""); } } public static void main(String[] args) { printIntAsASCII(calculateFromASCII()); } }

Bludiště

  1. Pro každý testovací případ načíst rozměry poschodí.
  2. Poschodí načítat po řádkách a konstruovat z něj graf. Vrcholy grafu odpovídají jednotlivým čtverečkům. Každé dva sousední čtverečky (vrcholy) propojit hranou grafu, pokud mají společnou tmavou hranu (lze poznat podle jejich písmen). Platí pro horizontální i vertikální směr.
  3. Hledat počet komponent grafu (tj. počet místností). Lze například pomocí kompletního prohledávání do šířky:
  4. Nastavit počítadlo na 1. Všechny vrcholy obarvit na bílo. Vzít první vrchol, obarvit ho na šedo a vložit ho do fronty.
  5. Pokud fronta není prázdná, vybrat první vrchol z fronty. Najít všechny jeho bezprostřední sousedy, označit je šedě a dát je do fronty. Vrchol označit černě.
  6. Opakovat od bodu 5, dokud není fronta prázdná.
  7. Pokud ještě existuje bílý vrchol, inkrementovat počítadlo, obarvit tento vrchol na šedo a vložit ho do fronty.
  8. Opakovat od bodu 5, dokud nejsou všechny vrcholy černé.
  9. Hodnota počítadla je počtem komponent grafu, tedy i počtem místností v poschodí (tj. výsledkem pro daný testovací případ).

Příklad zdrojového kódu:

#include<stdio.h> int main(void){ int T; scanf("%i", &T); int i; for(i=0;i<T;i++){ int N; int M; scanf("%i %i", &N, &M); int parent[N*M]; char Pole[N*M]; int j; for(j=0;j<N*M;j++){ parent[j]=j; } int k; int x; int y; char c; scanf("%c", &c); for(j=0;j<N;j++){ for(k=0;k<M;k++){ scanf("%c", &Pole[j*M+k]); if(Pole[j*M+k]=='A') parent[j*M+k]=-1; } scanf("%c", &c); } for(j=0;j<N;j++){ for(k=0;k<M-1;k++){ x=j*M+k; y=x+1; if((Pole[x]=='D'||Pole[x]=='E'||Pole[x]=='F')&&(Pole[x+1]=='B'||Pole[x+1]=='C'||Pole[x+1]=='F')){ while(parent[x]!=x) x=parent[x]; while(parent[y]!=y) y=parent[y]; if(x<y) parent[y]=x; else parent[x]=y; } } } for(j=0;j<N-1;j++){ for(k=0;k<M;k++){ x=j*M+k; y=x+M; if((Pole[x]=='B'||Pole[x]=='E'||Pole[x]=='F')&&(Pole[y]=='C'||Pole[y]=='D'||Pole[y]=='F')){ while(parent[x]!=x) x=parent[x]; while(parent[y]!=y) y=parent[y]; if(x<y) parent[y]=x; else parent[x]=y; } } } int res=0; for(j=0;j<N*M;j++){ if(parent[j]==j) res++; } printf("%in", res); } return 0; }

Fibonacciho šifra

  1. Pro každý testovací případ načíst, zda se jedná o kódování (K) či dekódování (D). Načíst zprávu do řetězce.
  2. Vytvořit si pole celých čísel délkou odpovídající maximální délce zprávy (256 znaků) a vypočítat si do každé jeho buňky poslední cifru odpovídajícího členu Fibonacciho posloupnosti.
  3. Projít načtenou zprávu znak po znaku a zjistit ASCII hodnotu aktuálního znaku.
  4. Pokud se má zpráva kódovat: Pokud se jedná o mezeru, do výsledné zprávy se přidá mezera. Pokud se nejedná o mezeru, k ASCII hodnotě znaku se přičte (pro lichou pozici) nebo odečte (pro sudou pozici) poslední cifra odpovídajícího členu Fibonacciho posloupnosti. Takto získaná hodnota se převede na znak a přidá do výsledné zprávy.
  5. Pokud se má zpráva dekódovat: Pokud se jedná o mezeru, do výsledné zprávy se přidá mezera. Pokud se nejedná o mezeru, k ASCII hodnotě znaku se přičte (pro sudou pozici) nebo odečte (pro lichou pozici) poslední cifra odpovídajícího členu Fibonacciho posloupnosti. Takto získaná hodnota se převede na znak a přidá do výsledné zprávy.
  6. Výsledná zpráva je výsledkem daného testovacího případu.

Příklad zdrojového kódu:

package fibonaci; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { private static int[] tempFib = {0, 1}; public static void main(final String[] args) throws IOException { final BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); for (int cases = Integer.parseInt(br.readLine()); cases > 0; --cases) { tempFib = new int[] {0, 1}; int oddity = (br.readLine().equals("K")) ? -1 : 1; final String msgToProcess = br.readLine(); String result = ""; for (int i = 0; i < msgToProcess.length(); ++i) { oddity *= -1; if (msgToProcess.charAt(i) != ' ') { result += (char)(msgToProcess.charAt(i) + (fib(i) % 10) * oddity); continue; } fib(i); result += msgToProcess.charAt(i); } System.out.println(result); } } private static int fib(final int i) { final int out = (i < 2) ? i : tempFib[0] % 10 + tempFib[1] % 10; tempFib[0] = tempFib[1]; tempFib[1] = out; return out; } }

Řezání kmenů

  1. Pro každý testovací případ načíst délku kmene, počet řezů a pozice jednotlivých řezů. Pozice jednotlivých řezů uložit do pole a řešit pomocí dynamického programování.
  2. Vytvořit si dvourozměrné celočíselné pole o délce i šířce odpovídající délce kmene zvětšené o 1.
  3. Vyplnit celé pole. Na prvek i, j uložit minimální energii na řezání kmene od pozice i do pozice j (vypočtenou jako minimum ze všech požadovaných řezů mezi pozicemi i a j).
  4. Výsledná minimální energie vyjde v poslední buňce nultého řádku vyplněného pole.

Příklad zdrojového kódu:

#include <stdio.h> #include <stdlib.h> #include <math.h> int main() { FILE *fr = stdin;//fopen("D:/vstup.txt","r"); int i, j, d, n, k, x, y; int pole[60][60], rezy[60]; fscanf(fr,"%d",&k); for(i=0;i<k;i++) { fscanf(fr,"%d %d",&d,&n); for(j=1;j<=n;j++) { fscanf(fr,"%d",&rezy[j]); } rezy[0]=0; rezy[n+1]=d; n+=2; for(j=0;j<n;j++) { pole[j][0]=pole[j][1]=0; for(x=2;x<n;x++) { pole[j][x]=INFINITY; } } for(j=2;j<n;j++) // delka { for(x=0;x<n;x++) // pozice { if(x+j>=n) break; int minimum = INFINITY; for(y=1;y<j;y++) // delka prvniho useku { int aktualni = pole[x][y] + pole[x+y][j-y] + rezy[x+j] - rezy[x]; if(minimum>aktualni) minimum=aktualni; } pole[x][j]=minimum; } } /*for(j=0;j<n;j++) { for(x=0;x<n;x++) { printf("%d ",pole[j][x]); } printf("n"); }*/ //break; printf("%dn",pole[0][n-1]); } return 0; }

Vyšetřování

  1. Pro každý testovací případ načíst počet skupin a počet známostí. Pokud je počet skupin roven 0, výsledkem je 0.
  2. Vytvořit graf o počtu vrcholů odpovídající počtu skupin. Načítat jednotlivé známosti po řádkách a přidávat odpovídající hrany (spojení dvou vrcholů, tedy skupin) do grafu.
  3. Hledat jednotlivé komponenty grafu (tj. jednotlivé odnože) a pro každou odnož vypsat nejmenší číslo skupiny. Lze například pomocí upraveného kompletního prohledávání do šířky:
  4. Všechny vrcholy obarvit na bílo.
  5. Aktuální mimimum nastavit na hodnotu větší než počet skupin. Vzít první bílý vrchol z pole vrcholů (pamatovat si poslední černý vrchol kvůli efektivitě), obarvit ho na šedo a vložit ho do fronty.
  6. Pokud fronta není prázdná, vybrat první vrchol z fronty. Pokud je jeho číslo menší než aktuální minimum, zapsat ho jako aktuální minimum. Najít všechny jeho bezprostřední sousedy, označit je šedě a dát je do fronty. Vrchol označit černě.
  7. Opakovat od bodu 6, dokud není fronta prázdná.
  8. Vypsat aktuální minimum.
  9. Opakovat od bodu 5, dokud nejsou všechny vrcholy černé.

Příklad zdrojového kódu:

package vysetrovani_2; import java.util.ArrayList; import java.util.Collections; import java.util.List; import java.util.Scanner; public class Vysetrovani_2 { public static ArrayList<String> znamosti = new ArrayList<String>(); public static ArrayList<Integer> odnoze = new ArrayList<Integer>(); /** * @param args the command line arguments */ public static void main(String[] args) { // TODO code application logic here Scanner sc = new Scanner(System.in, "Windows-1250"); int opakovani = Integer.parseInt(sc.nextLine()); String odnozeaznamosti = ""; for (int i = 0; i < opakovani;i++) { odnozeaznamosti = sc.nextLine(); if (Integer.parseInt(odnozeaznamosti.split(" ")[0]) != 0) { for (int j = 0; j < Integer.parseInt(odnozeaznamosti.split(" ")[1]); j++) { znamosti.add(sc.nextLine()); } for (int k = 1; k <= Integer.parseInt(odnozeaznamosti.split(" ")[0]); k++) { odnoze.add(k); } ArrayList<Integer> propojenacisla = new ArrayList<>(); //Zacina sortingovani masochisticke for (int l = 0; l < Integer.parseInt(odnozeaznamosti.split(" ")[1]); l++) { if (znamosti.size() != 0) { propojenacisla.add(Integer.parseInt(znamosti.get(0).split(" ")[0])); int counter = 0; do { if (znamosti.size() != 0) { propojenacisla = (ArrayList<Integer>) hledatko(propojenacisla.get(counter), propojenacisla); } else break; counter++; } while (counter < propojenacisla.size()); Collections.sort(propojenacisla); cistitko(propojenacisla); propojenacisla.clear(); } else { break; } } for (int c : odnoze) { if (c != odnoze.get(odnoze.size() - 1)) System.out.print(c + " "); else System.out.println(c); } odnoze.clear(); } else { for (int m = 0; m < Integer.parseInt(odnozeaznamosti.split(" ")[1]);m++ ) { sc.nextLine(); } System.out.println(0); } } } public static ArrayList<Integer> hledatko(int hledam, ArrayList<Integer> vystup) { int i = 0; do { if (Integer.parseInt(znamosti.get(i).split(" ")[0]) == hledam && vystup.contains(Integer.parseInt(znamosti.get(i).split(" ")[1])) == false) { vystup.add(Integer.parseInt(znamosti.get(i).split(" ")[1])); znamosti.remove(i); i--; } else if (Integer.parseInt(znamosti.get(i).split(" ")[1]) == hledam && vystup.contains(Integer.parseInt(znamosti.get(i).split(" ")[0])) == false) { vystup.add(Integer.parseInt(znamosti.get(i).split(" ")[0])); znamosti.remove(i); i--; } i++; } while (i < znamosti.size()); return vystup; } public static void cistitko(ArrayList<Integer> vstup) { for (int i = vstup.size() - 1; i > 0;i--) { odnoze.remove(vstup.get(i)); } } }

Zrzečka

  1. Pro každý testovací případ načíst počet kopek ořechů a počty ořechů v jednotlivých kopkách uložit do celočíselného pole.
  2. Spočítat celkový počet oříšků ve všech kopkách. Pokud počet oříšků není dělitelný počtem kopek, vypsat, že úlohu nelze splnit. Spočítat průměrný počet ořechů v kopce.
  3. Projít postupně všechny kopky. Pro každou kopku spočítat rozdíl mezi jejím počtem oříšků a průměrným počtem oříšků. Pokud je rozdíl lichý, vypsat, že úlohu nelze splnit. Pokud je rozdíl sudý, vydělit ho dvěmi a výsledek přičít do celkového počtu výměn.
  4. Pokud je celkový počet výměn lichý, vypsat, že úlohu nelze splnit. Jinak vypsat celkový počet výměn vydělený dvěmi.

Příklad zdrojového kódu:

#include <stdio.h> #include <stdlib.h> void solve(void) { int k; int *orechy; int ideal = 0; int reseni = 0; int liche = 0; int sude = 0; scanf("%d", &k); orechy = malloc(k*sizeof(int)); for (int i = 0; i < k; i++) { scanf("%d", &orechy[i]); ideal += orechy[i]; if (orechy[i] % 2 == 0) sude++; else liche++; } if (ideal % k) { puts("Nelze splnit."); return; } ideal /= k; if ((sude && liche) || (ideal % 2 ? sude : liche)) { puts("Nelze splnit."); return; } for (int i = 0; i < k; i++) reseni += abs(ideal-orechy[i]); printf("%dn", reseni/4); free(orechy); } int main(void) { size_t p; scanf("%d", &p); while (p--) solve(); 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ů.

Bobr

  1. Vzhledem k maximální délce potoku (20 000 řádek) je možné využít hrubou sílu.
  2. Pro každý potok načíst vzdálenosti levého a pravého břehu od levého okraje mapy do dvou polí.
  3. Postupně spočítat délku přechodu pro každou kombinaci čtverečků levého a pravého břehu (celkem 400 000 000 kombinací). U čtverečků levého a pravého břehu ve stejné řádce stačí odečíst vzdálenosti od levého okraje mapy. U čtverečků z různých řádek je třeba navíc připočítat vertikální vzdálenost (rozdíl indexů řádek).
  4. Pamatovat si minimum, pokud je spočtená délka přechodu menší než minimum, nahradit minimum touto hodnotou.
  5. Pokud miminum dosáhne 1, skončit. Méně to být podle zadání nemůže.
  6. Vypsat zjištěné minimum.

Příklad zdrojového kódu:

#include <stdio.h> #define MAXN 20005 #define MIN(a,b) ((a) < (b) ? (a) : (b)) int strana(int *l, int *p, int n) { int prev = p[0]; int min = prev - l[0]; for (int i=1; i<n; i++){ prev = MIN(p[i], prev + 1); min = MIN(min, prev - l[i]); } return min; } int vyres(void) { int n; scanf("%d", &n); int l[MAXN], p[MAXN]; for (int i=0; i<n; i++) scanf("%d %d", &l[i], &p[i]); int min = strana(l, p, n); for (int i=0, j=n - 1; i<j; i++, j--){ int t = l[i]; l[i] = l[j]; l[j] = t; t = p[i]; p[i] = p[j]; p[j] = t; } min = MIN(min, strana(l, p, n)); return min; } int main(void) { int behu; scanf("%d", &behu); for (int i=0; i<behu; i++) printf("Pocet dilu: %dn", vyres()); }

Drakiáda

  1. Pro každý testovací případ načíst do pole délky jednotlivých tyček.
  2. Čtverec má 4 strany, pokud tedy celkový součet délek všech tyček (tyčky je nutno použít všechny) není dělitelný čtyřmi, čtverec nelze sestavit. Pokud dále existuje tyčka delší než jedna strana čtverce (celková délka tyček dělená čtyřmi), čtverec opět nelze sestavit.
  3. Problém sestavení čtverce rozdělit na čtyři sestavení jedné strany. Pokud je možné vytvořit z tyček čtyři strany o stejné délce, je možno vytvořit i čtverec.
  4. Vytvořit pole indikující, zda byla daná tyčka použita či ne a nastavit u všech tyček, že nebyly použity.
  5. Rekurzivně zkoušet přidávat jednotlivé tyčky (přičítat jejich délky), dokud není dosaženo délky jedné strany, nebo není tato délka přesažena. Pokud je délka přesažena, tyčku odstranit a zkusit další.
  6. Pokud je délka jedné strany dosažena čtyřikrát a jsou použity všechny tyčky (indikováno polem), čtverec lze sestavit.

Příklad zdrojového kódu:

#include<stdio.h> #include<vector> #include<algorithm> #include<queue> #include<set> #include<unordered_map> using namespace std; int flag[1500000]; int main(void){ int T; int k; int mocniny[26]; mocniny[0]=1; for(k=1;k<26;k++){ mocniny[k]=2*mocniny[k-1]; } scanf("%i", &T); for(k=1;k<=T;k++){ int N; int i; int l; scanf("%i", &N); int Pole[N]; int soucet=0; for(i=0;i<N;i++){ scanf("%i", &Pole[i]); soucet+=Pole[i]; } if(soucet%4!=0){ printf("NEn"); continue; } int s[mocniny[N]]; int j=0; s[0]=0; for(i=1;i<mocniny[N];i++){ //printf("%i %in", i, j); if(mocniny[j]==i) {s[i]=Pole[j]; j++; if(s[i]==soucet/4) flag[i]=k; } else { s[i]=s[mocniny[j-1]]+s[i-mocniny[j-1]]; if(s[i]==soucet/4) flag[i]=k; for(l=0;l<N;l++){ if(((i&mocniny[l])>0)&&(flag[mocniny[l]]==k||flag[i-mocniny[l]]==k)) {flag[i]=k; break;} } } } //printf("n"); for(i=1;i<mocniny[N];i++){ //printf("%i %in", s[i], flag[i]); if(s[i]==soucet/2&&flag[i]==k&&flag[mocniny[N]-1-i]==k) {printf("ANOn"); break;} if(i==mocniny[N]-1) printf("NEn"); } } return 0; }

Jídelna

  1. Pro každý testovací případ načíst jednu řádku s pozicemi leváků (L) a praváků (P) u stolu do řetězce.
  2. Čítač nebezpečných dvojic inicializovat na 0. Procházet řetězec od začátku do konce a zkoumat vždy dva znaky za sebou. Pokud se vyskytne kombinace „PL“, inkrementovat čítač nebezpečných dvojic.
  3. Vypsat hodnotu čítače nebezpečných dvojic.

Příklad zdrojového kódu:

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int count = Integer.parseInt(br.readLine()); String table; while(--count >= 0){ StringTokenizer st = new StringTokenizer(br.readLine()); int collisions = 0; while(st.hasMoreTokens()) { collisions += checkForCollision(st.nextToken()); } System.out.println(collisions); } } private static int checkForCollision(String table) { int counter = 0; for (int i = 0; i < table.length() - 1; ++i) { if (table.charAt(i) == 'P' && table.charAt(i + 1) == 'L') { ++counter; } } return counter; } }

Lupiči a četníci

  1. Lupiči mohou dosáhnout propuštění, ale není to jisté, záleží na pořadí a množství výslechů. Protože se spolu nemohou domlouvat mezi výslechy, použijí pro komunikaci sklenici vody. Každý řadový lupič musí požádat o vodu, pokud o ni ještě nežádal a pokud je sklenice při jeho příchodu do výslechové místnosti prázdná. Koumák musí vodu vypít a jakmile ji vypije tolikrát, kolik má kompliců, pronese propouštěcí formuli. Pokud ale výslechy skončí dříve, než se k tomu dostane, k propuštění nedojde.
  2. Je zadán pouze jeden scénář výslechů reprezentován čísly lupičů. Tato čísla lupičů načíst do pole. Při načítání určit, kolik je různých čísel lupičů a vytvořit si pole s čísly lupičů s výjimkou 0 (číslo Koumáka).
  3. Vytvořit si pole indikující, zda jednotliví řadoví lupiči již žádali o vodu a nastavit u všech lupičů, že ne.
  4. Připravit si proměnnou představující sklenici a nastavit ji na prázdnou. Připravit si čítač výslechů a inicializovat ho na 0. Postupně procházet pole s výslechy (čísly lupičů) v cyklu. V každé obrátce inkrementovat čítač výslechů.
  5. Pokud je číslo lupiče větší než 0 (běžný lupič), sklenice je prázdná a lupič zatím nežádal o vodu, požádat o vodu (tj. sklenici nastavit na plnou). U daného lupiče si do pole poznačit, že již žádal o vodu.
  6. Pokud je číslo lupiče 0 (Koumák) a sklenice je plná, vypít sklenici (tj. nastavit sklenici na prázdnou) a zjistit, zda už všichni ostatní lupiči žádali o vodu (průchodem pole). Pokud ano, pronést osvobozující formuli (tj. ukončit cyklus procházení pole výslechů).
  7. Po ukončení cyklu vypsat hodnotu čítače výslechů s uvozovacím textem „Pocet vyslechu =“. Pokud cyklus došel až do konce a všichni lupiči doposud nepožádali o vodu (nebo nebyla příležitost to zjistit), vypsat text „Lupici nedostali sanci.“, jinak vypsat text „Jsme volni!“.

Příklad zdrojového kódu:

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.logging.Level; import java.util.logging.Logger; /** * * @author pilsprog */ public class ProblemD { /** * @param args the command line arguments */ public static void main(String[] args) { new ProblemD(); } public ProblemD() { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); ArrayList<Integer> vyslechy = new ArrayList<>(); try { int max = 0; String s = ""; while (!(s = br.readLine()).startsWith("-1")) { vyslechy.add(Integer.parseInt(s)); if (Integer.parseInt(s) > max) { max = Integer.parseInt(s); } } boolean[] marked = new boolean[max + 1]; boolean glass = false; int discovered = 0; if (max == 0) { System.out.println("Pocet vyslechu = " + (1)); System.out.println("Jsme volni!"); System.exit(0); } for (int i = 0; i < vyslechy.size(); i++) { if (vyslechy.get(i) == 0) { if (glass) { discovered++; glass = false; if (discovered == max) { System.out.println("Pocet vyslechu = " + (i + 1)); System.out.println("Jsme volni!"); System.exit(0); } } } else if (!glass && !marked[vyslechy.get(i)]) { marked[vyslechy.get(i)] = true; glass = true; } /*for (int j = 0; j < marked.length; j++) { System.out.println(marked[j]); }*/ //System.out.println("-------------------"); } System.out.println("Pocet vyslechu = " + vyslechy.size()); System.out.println("Lupici nedostali sanci."); } catch (IOException ex) { Logger.getLogger(ProblemD.class.getName()).log(Level.SEVERE, null, ex); } } }

Mraveniště

  1. Pro každý testovací případ načíst počet prvků neklesající posloupnosti a počet dotazů.
  2. Načíst jednotlivé prvky posloupnosti do pole. Při načítání si zároveň vytvářet pole frekvencí výskytu prvků, ve kterém je každý prvek nahrazen počtem svého výskytu (např. budou-li na vstupu tři čísla 1, budou všechna nahrazena číslem 3). Dále si vytvářet pole počátečních a pole koncových indexů (tj. pole určující pro každý prvek, na kterém indexu začínají, respektive končí prvky se stejnou hodnotou.
  3. Nad polem frekvencí výskytu prvků vytvoříme binární strom (postupně od listů tvořených prvky pole vytvořit další patra stromu, v předchůdci bude vždy větší z hodnot obou následníků.
  4. Načítat jednotlivé dotazy (tj. hranice intervalu) a pro každý provést následující:
  5. Pokud je levý a pravý index shodný, vypsat 1. Pokud jsou prvky na levém a pravém indexu shodné, vypsat rozdíl pravého a levého indexu zvýšený o 1. Pokračovat s dalším dotazem.
  6. Zjistit, zda se nalevo od levého indexu nenachází stejný prvek jako na levém indexu. Pokud ano, posunout levý index na první jiný prvek napravo (s využitím pole koncových indexů). Zjistit, zda se napravo od pravého indexu nenachází stejný prvek jako na pravém indexu. Pokud ano, posunout pravý index na první jiný prvek nalevo (s využitím pole počátečních indexů).
  7. Pomocí binárního stromu vyhledat nejvyšší hodnotu v poli frekvencí výskytu prvků mezi (případně posunutým) levým a pravým indexem.
  8. Vypsat maximum z nalezené nejvyšší hodnoty, rozdílu mezi původním levým indexem a posunutým levým indexem a rozdílu mezi původním pravým indexem a posunutým pravým indexem.

Příklad zdrojového kódu:

#include <stdio.h> #include <stdlib.h> #include <string.h> void fill_plus(int *input, int *plus, int n) { int val = input[n-1]+1; for (int i = n-1; i >= 0; i--) { if (val == input[i]) { plus[i] = plus[i+1]+1; } else { plus[i] = 1; val = input[i]; } } } int maxint(int *plus, int i, int j) { int max = 0; while (i <= j) { int val = plus[i]; if (i+val > j) val = plus[i]-plus[j]+1; if (val > max) max = val; i += plus[i]; } return max; } int main(int argc, char **argv) { int n, q; while (scanf("%d %d", &n, &q) == 2) { int *input = malloc(n*sizeof(int)); int *plus = malloc(n*sizeof(int)); for (int i = 0; i < n; i++) scanf("%d ", &input[i]); fill_plus(input, plus, n); /*for (int i = 0; i < n; i++) printf("%2d ", input[i]); putchar('n'); for (int i = 0; i < n; i++) printf("%2d ", plus[i]); putchar('n');*/ while (q--) { int i, j; scanf("%d %d", &i, &j); printf("%dn", maxint(plus, i-1, j-1)); } free(input); free(plus); } return 0; }