PilsProg 2021

Výsledky Lite

#JménoPříjmeníSplněných úlohČas
1VojtěchHolý9516,442
2ŠimonKala6304,978
3KryštofJelínek437,794
4MichalPavlíček3206,908
5LukášTomoszek3218,907

Cena udělená za 1. místo v PilsProg Lite: Externí 1TB 2.5" HDD

Výsledky kvalifikace

#JménoPříjmeníSplněných úlohČasFinále
1KristýnaPetrlíková6298,070Postupuje do finále
2LukášTomoszek6622,849Postupuje do finále
3JiříKalvoda61 173,314Postupuje do finále
4TomášMüller5814,761Postupuje do finále
5VáclavJanáček51 831,444Postupuje do finále
6OndřejSladký51 839,216Postupuje do finále
7DominikFarhan41 801,814Postupuje do finále
8AdamBlažek2773,330Postupuje do finále
9MarikaKosohorská21 266,023Postupuje do finále
10ŠimonKala21 303,247Postupuje do finále
11OndřejKovář22 309,363Postupuje do finále
12KryštofJelínek120,845-
13JakubKopčil1119,466-
14MichalPavlíček1198,347-
15RobertOnder1821,530-

Výsledky finále

#JménoPříjmeníSplněných úlohČas
1JiříKalvoda45,744
2VáclavJanáček47,676
3KristýnaPetrlíková33,817
4AdamBlažek34,062
5OndřejSladký22,172
6LukášTomoszek22,204
7DominikFarhan24,868
8ŠimonKala00,000
9TomášMüller00,000
10MarikaKosohorská00,000
11OndřejKovář00,000

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ů
AxB170110
AplusB17023
Největší ze tří celých čísel17033
Pascalův trojúhelník17043

Lite1 úlohy

NázevČísloÚspěšných řešitelů
Hospoda21113
Hvězdičkové hodnocení21123
Skalární součin21133

Lite2 úlohy

NázevČísloÚspěšných řešitelů
Délka slov21143
Digitální hodiny21153
Násobek matice21163

Lite3 úlohy

NázevČísloÚspěšných řešitelů
Druhé největší21173
Hledání podřetězce21182
Nejmenší společný násobek21192

Kvalifikační úlohy

NázevČísloÚspěšných řešitelů
Borské obrazce21216
Okno212215
Pizza21237
Registrační systém21246
Řeky21255
Tunelín212610

Finálové úlohy

NázevČísloÚspěšných řešitelů
Moderní umění21314
Dámy v ohrožení21327
Ostrovy21330
Šifrovaná zpráva21347
Zachraňte Sněhurku21352

A jaké bylo finále?

Finále začíná ...

Harmonogram PilsProg 2021

Lite ú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.

Hospoda

  1. Pro každý testovací případ si načíst hodiny a minuty počátku a konce otevírací doby a hodiny a minuty příchodu do hospody.
  2. Převést si všechny načtené časy na minuty.
  3. Pokud je počátek otevírací doby menší než konec otevírací doby, přičíst ke konci 24 hodin.
  4. Pokud je příchod do hospody mezi počátkem a koncem otevírací doby, vypsat „Otevreno“.
  5. Jinak přičíst k času příchodu do hospody 24 hodin a, pokud je nyní příchod do hospody mezi počátkem a koncem otevírací doby, vypsat „Otevreno“. Jinak vypsat „Zavreno“.

Příklad zdrojového kódu:

program Project1; {$mode objfpc}{$H+} uses {$IFDEF UNIX}{$IFDEF UseCThreads} cthreads, {$ENDIF}{$ENDIF} Classes { you can add units after this }; var t, i, i2: integer; cas: array [1..6] of integer; begin readln(t); for i:=1 to t do begin for i2:= 1 to 6 do read(cas[i2]); if (cas[3] < cas[1]) then begin cas[3]:= cas[3] + 24; if (cas[5] < cas[1]) then cas[5]:= cas[5] + 24; end; if ((cas[5] > cas[1]) and (cas[5] < cas[3])) or ((cas[5] = cas[1]) and (cas[6] >= cas[2])) or ((cas[5] = cas[3]) and (cas[6] = cas[4])) then writeln('Otevreno.') else writeln('Zavreno.'); end; readln; readln; end.

Hvězdičkové hodnocení

  1. Pro zadaný počet hodnocení načíst jednotlivá hodnocení jako řetězce.
  2. Pro každé hodnocení projít řetězec a spočítat počet hvězdiček a určit počet procent (jedna hvězdička odpovídá 20 %).
  3. Sečíst jednotlivé počty procent a vydělit počtem hodnocení. Výsledek vypsat zaokrouhlený na celé číslo dle standardních matematických pravidel.

Příklad zdrojového kódu:

#include <iostream> #include <string> #include <cmath> using namespace std; int main() { string a; double n, b = 0; cin >> n; for (size_t i = 0; i < n; i++) { cin >> a; b += a.size() % 6; } cout << round(b * 20 / n) << endl; }

Skalární součin

  1. Načíst si velikost obou vektorů a načíst jednotlivé složky vektorů do polí.
  2. Projít obě pole najednou, počítat součiny odpovídajících složek vektorů a přičítat je do celkové sumy.
  3. Celkovou sumu vypsat.

Příklad zdrojového kódu:

#include <stdio.h> int main() { int n; scanf("%d", &n); float vec1[n]; float vec2[n]; for (int i = 0; i < n; ++i) { scanf("%f", &vec1[i]); } for (int i = 0; i < n; ++i) { scanf("%f", &vec2[i]); } float result = 0; for (int i = 0; i < n; ++i) { result += vec1[i] * vec2[i]; } printf("%1.2f", result); }

Délka slov

  1. Načíst počet slov.
  2. Připravit si pole celých čísel o délce odpovídající maximální délce slov (50 znaků) a všechny jeho prvky nastavit na 0. Toto pole bude nakonec obsahovat počty délek slov.
  3. Načítat jednotlivá slova jako řetězce (celé řádky).
  4. U každého načteného slova určit jeho délku (nepočítat případný konec řádky na konci slova - závisí na způsobu načítání) a buňku pole na indexu odpovídající určené délce slova inkrementovat.
  5. Projít pole počtů délek slov a vypsat všechny jeho nenulové prvky (index a hodnotu ve formátu „index: hodnota“).

Příklad zdrojového kódu:

program Project1; {$mode objfpc}{$H+} uses {$IFDEF UNIX}{$IFDEF UseCThreads} cthreads, {$ENDIF}{$ENDIF} Classes, sysutils { you can add units after this }; var n,i,x: integer; s: string; pocet: array [1..50] of integer; begin for i:=1 to 50 do pocet[i]:= 0; readln(n); for i:=1 to n do begin readln(s); s:= Trim(s); x:= length(s); pocet[x]:= pocet[x] + 1; end; for i:=1 to 50 do if (pocet[i] <> 0) then writeln (i,': ',pocet[i]); readln; end.

Digitální hodiny

  1. Připravit si obrazy jednotlivých číslic 0 až 9 jako dvourozměrná pole znaků o 9 řádkách a 5 sloupcích.
  2. Připravit si plochu pro vykreslení číslic jako dvourozměrné pole o 9 řádkách a (4 * 5 + 3 * 3) = 29 sloupcích (5 sloupců na každou číslici a 3 sloupce na každou mezeru mezi číslicemi).
  3. Načíst hodiny a minuty a získat jednotlivé číslice (vždy 4, používají se nevýznamové nuly).
  4. Odpovídající obrazy jednotlivých číslic překopírovat do plochy pro vykreslení číslic na správné pozice vypočtené na základě konstatní šířky obrazu číslice a mezery.
  5. Vykreslit dvojtečku na správnou pozici do plochy pro vykreslení číslic.
  6. Plochu pro vykreslení číslic vypsat po řádkách.

Příklad zdrojového kódu:

/* Program * * */ #include <stdio.h> int main() { int i, j, t[4]; char p[5][6] = {" ", "* ", " *", "* *", " *** "}; int flag[10][9] = { {4, 3, 3, 3, 0, 3, 3, 3, 4}, {0, 2, 2, 2, 0, 2, 2, 2, 0}, {4, 2, 2, 2, 4, 1, 1, 1, 4}, {4, 2, 2, 2, 4, 2, 2, 2, 4}, {0, 3, 3, 3, 4, 2, 2, 2, 0}, {4, 1, 1, 1, 4, 2, 2, 2, 4}, {4, 1, 1, 1, 4, 3, 3, 3, 4}, {4, 2, 2, 2, 0, 2, 2, 2, 0}, {4, 3, 3, 3, 4, 3, 3, 3, 4}, {4, 3, 3, 3, 4, 2, 2, 2, 4}, }; // int flag[9][2] = {{0,0},{1,5},{6,6},{2,4},{3,3}} //printf("%s \n", p[2]); scanf("%1d %1d %1d %1d", &t[0], &t[1], &t[2], &t[3]); //printf("%d%d %d%d \n", t[0], t[1], t[2], t[3]); for( i = 0; i < 9; i++ ) { for( j = 0; j < 4; j++ ) { // Colon printing if( j == 2 ) { if( i == 2 || i == 6 ) printf(" * "); else printf(" "); } printf("%s", p[flag[t[j]][i]]); if( j != 1 && j != 3 ) printf(" "); } if( i != 8 ) putchar('\n'); } return 0; }

Násobek matice

  1. Pro každý testovací případ načíst rozměry matice a jednotlivé prvky matice do dvourozměrného pole. Dále načíst koeficient, kterým se bude matice násobit.
  2. Projít celou matici pomocí dvou vnořených cyklů po řádkách, násobit její jednotlivé prvky koeficientem a výsledky vypisovat na standardní výstup.
  3. Za každým vypsaným výsledkem kromě posledního sloupce vypsat mezeru. Za posledním výsledkem na řádce odřádkovat.
  4. Po vypsání celé výsledné matice odřádkovat.

Příklad zdrojového kódu:

/* Program * * */ #include <stdio.h> int main() { int i, j, k, n, r, s, f[50][50] = {0}; scanf("%d", &n); while( n-- ) { scanf("%d %d", &r, &s); for( i = 0; i < r; i++ ) { for( j = 0; j < s; j++ ) { scanf("%d", &f[i][j]); } } scanf("%d", &k); for( i = 0; i < r; i++ ) { for( j = 0; j < s; j++ ) { printf("%d ", k * f[i][j]); //f[i][j] *= k; } putchar('\n'); } putchar('\n'); } return 0; }

Druhé největší

  1. Pro každý testovací případ načíst počet prvků posloupnosti a prvky posloupnosti si načíst do pole.
  2. Připravit si proměnné pro největší a druhý největší prvek a obě nastavit na nižší hodnotu, než je nejmenší možný prvek posloupnosti.
  3. Projít celé pole od začátku v cyklu.
  4. Porovnávat aktuální prvek s největším prvkem.
  5. Pokud je aktuální prvek větší než největší prvek, největší prvek přiřadit do druhého největšího a aktuální do největšího.
  6. Jinak porovnat druhý největší prvek s aktuálním prvkem a, pokud je aktuální prvek větší, přiřadit ho do druhého největšího.
  7. Po skončení cyklu vypsat druhý největší prvek na standardní výstup.

Příklad zdrojového kódu:

#include <iostream> using namespace std; int main() { int repeats; cin >> repeats; int* arr = new int [repeats](); int temp, largest, second_largest; for (int c = 0; c < repeats; c++) { int nums; cin >> nums; largest = NULL; second_largest = NULL; for (int n = 0; n < nums; n++) { cin >> temp; if (temp >= largest || largest == NULL) { if (temp != largest) { second_largest = largest; } largest = temp; } else if (temp >= second_largest || second_largest == NULL) { second_largest = temp; } //cout << ":" << temp << " " << largest << " " << second_largest << "\n"; } arr[c] = second_largest; } for (int c = 0; c < repeats; c++) { cout << arr[c]; if (c != repeats - 1) { cout << "\n"; } } delete[]arr; }

Hledání podřetězce

  1. Načíst počet řádek, hledaný podřetězec a následně jednotlivé řádky textu do pole řetězců.
  2. V cyklu projít načtené pole řetězců a pomocí knihovní metody hledání podřetězce hledat zadaný podřetězec v daném prvku pole (tj. řádce).
  3. Pokud je podřetězec nalezen, skončit a vypsat číslo řádky a pozici podřetězce. Podle použité funkce pro hledání podřetězce a řídící proměnné cyklu upravit číslo řádky a/nebo pozici tak, aby začínaly od 1.
  4. Pokud nebyl pořetězec nalezen v žádné řádce, vypsat "0".

Příklad zdrojového kódu:

#include <iostream> #include <string> using namespace std; int main() { int lines; cin >> lines; int loc = 0; int line = 0; string substr; cin >> substr; string str; for (int c = 0; c < lines; c++) { getline(cin, str); if (loc == 0 && str.find(substr) != string::npos) { loc = str.find(substr)+1; line = c; } } if (loc != 0) { cout << line << " " << loc; } else { cout << 0; } }

Nejmenší společný násobek

  1. Pro každý testovací případ načíst dvě čísla a a b a uložit je do proměnné schopné uchovat i hodnotu 1012 (např. long v Javě).
  2. Nejmenší společný násobek (NSN) určit pomocí největšího společného dělitele (NSD) podle vzorce NSN(a, b) = (a * b) / NSD(a, b).
  3. Největší společný dělitel určit následovně:
  4. Určit minimum z a a b.
  5. Připravit si proměnnou pro největšího společného dělitele a inicializovat ji na 1.
  6. V cyklu for opakujícím se v intervalu <minimum; 2> zjišťovat, zda jsou obě čísla dělitelná aktuálním indexem. Pokud ano, přiřadit aktuální index do proměnné pro největšího společného dělitele a cyklus předčasně ukončit.
  7. Po skončení cyklu použít hodnotu NSD, spočítat NSN a vypsat ho na standardní výstup.

Příklad zdrojového kódu:

program Project1; {$mode objfpc}{$H+} uses {$IFDEF UNIX}{$IFDEF UseCThreads} cthreads, {$ENDIF}{$ENDIF} Classes { you can add units after this }; const MAX = 1000000; var n,i,i2,i3,c1,c2,nasobek: integer; pole,p2: array [1..MAX] of integer; celkem: Int64; begin readln(n); for i:=1 to n do begin for i2:= 1 to MAX do begin pole[i2]:= 0; p2[i2]:= 0; end; read(c1); readln(c2); nasobek:= 1; celkem:= 1; if (((c1 mod c2) = 0) or ((c2 mod c1) = 0)) then begin if ((c1 mod c2) = 0) then celkem:= c1; if ((c2 mod c1) = 0) then celkem:= c2 end else begin for i2:=2 to c1 do while ((c1 mod i2)= 0) do begin c1:= c1 div i2; pole[i2]:= pole[i2] + 1; end; for i2:=2 to c2 do while ((c2 mod i2)= 0) do begin c2:= c2 div i2; p2[i2]:= p2[i2] + 1; end; for i2:=1 to MAX do begin if ((pole[i2]<> 0) or (p2[i2]<> 0)) then begin if (pole[i2] >= p2[i2]) then for i3:= 1 to (pole[i2]) do nasobek:= nasobek*i2; if (pole[i2] < p2[i2]) then for i3:= 1 to (p2[i2]) do nasobek:= nasobek*i2; celkem:= celkem*nasobek; nasobek:= 1; end; end; end; writeln(celkem); end; readln; end.

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.

Borské obrazce

  1. Načíst si rozměry oblasti a následně její jednotlivé znaky např. do dvourozměrného pole.
  2. Problém spočívá v nalezení komponent v černobílém rastru.
  3. Jednotlivé komponenty lze identifikovat např. pomocí prohledávání do šířky (DFS) - postupně procházet všechny pixely a pro každý dosud neidentifikovaný pixel spustit DFS, které navštíví a označí identifikátorem všechny pixely v celé komponentě. Uvažovat sousednost přes osmi-okolí pixelu.
  4. Podobně lze identifikovat komponenty volného prostoru, jen místo osmi-okolí použít čtyř-okolí. Vnější volný prostor vyloučit - rozšířit mapu o 1 pixel a vyloučit identifikátor příslušné komponenty.
  5. Pro řešení celé úlohy nejdříve očíslovat komponenty volného prostoru a až poté spustit identifikaci obrazců. V průběhu identifikace každého obrazce (v rámci DFS) udržovat množinu identifikátorů komponent volného prostoru, které s obrazcem sousedí. Technicky lze realizovat např. uložením identifikátorů do hash-set.
  6. Velikost této množiny společně s pozicí výchozího pixelu vypsat na výstup.

Příklad zdrojového kódu:

#include <bits/stdc++.h> using namespace std; int s, r; char pole[300][300]; int mapa[300][300]; int out[50000]; void funkce(int x, int y, char t, int in) { if(x<0 or y<0 or x>=r or y>=s) return; if(pole[x][y]!=t) return; if(mapa[x][y]) return; mapa[x][y]=in; for(int i=-1; i<2; i++) { for(int j=-1; j<2; j++) { if(t=='.' and (j==-1 and i==-1)) continue; if(t=='.' and (j==-1 and i==1)) continue; if(t=='.' and (j==1 and i==-1)) continue; if(t=='.' and (j==1 and i==1)) continue; funkce(x+i, y+j, t, in); } } } int main() { cin >> s >> r; int pocet=0; for(int i=1; i<=r; i++) { for(int j=1; j<=s; j++) cin >> pole[i][j]; } r+=2; s+=2; for(int i=0; i<r; i++) { for(int j=0; j<s; j++) if (pole[i][j]==0) pole[i][j]='.'; } for(int i=0; i<r; i++) { for(int j=0; j<s; j++) { if(mapa[i][j]==0) { pocet++; funkce(i, j, pole[i][j], pocet); } } } /* for(int i=0; i<r; i++) { for(int j=0; j<s; j++) { if(mapa[i][j]<10) cout << " "; cout << mapa[i][j] << " "; } cout << endl; } */ for(int i=0; i<r; i++) { for(int j=0; j<s; j++) { if(pole[i][j]=='.' and out[mapa[i][j]]==0) { out[mapa[i][j]]=-1; if(i==0 and j==0) continue; out[mapa[i-1][j]]++; } } } for(int i=0; i<r; i++) { for(int j=0; j<s; j++) { if(pole[i][j]=='*' and out[mapa[i][j]]>=0) { cout << "Obrazec na pozici " << i << " " << j << ", pocet der " << out[mapa[i][j]] << endl; out[mapa[i][j]]=-1; } } } return 0; }

Okno

  1. Pro každé okno načíst počet řad budovy (výška okna).
  2. Počet dílků podle výšky okna určit např. vzorcem 3((r(1 + r)) / 2) - r, kde r je počet řad.
  3. Vzhledem k maximální možné výšce budovy používat pro výpočty 64bitový celočíselný datový typ, aby nedošlo k přetečení.
  4. Z počtu dílků udělat zbytek po celočíselném dělení 1000007 a ten vypsat na výstup jako výsledek.

Příklad zdrojového kódu:

program Project1; {$mode objfpc}{$H+} var i: longint; pocet,suma,n,o: Qword; begin readln(o); for i:=1 to o do begin readln(n); suma := ((n-1)*(4+3*n)) div 2; pocet := 2+suma; pocet := pocet mod 1000007; writeln(pocet); end; end.

Pizza

  1. Načíst si počet ančoviček a následně jejich souřadnice a uložit si je.
  2. Cílem je z pizzy vykrojit co možná největší klínky (kruhové výseče) bez ančoviček a určit, kolik zabírají celkem procent celé pizzy. To lze určit např. pomocí zametacích algoritmů, kdy uvažujeme polopřímku ukotvenou svým počátečním bodem ve středu pizzy a tato polopřímka rotuje třeba proti směru hodinových ruček.
  3. Polopřímka postupně navštíví počátky a konce jednotlivých úseček. Postupnou reakcí na tyto události vyčíslovat překryv (počet ančoviček na zametací polopřímce) - počáteční bod každé úsečky zvedá číslo překryvu o 1 a koncový bod ho snižuje o 1. V místech, kde číslo překryvu spadne na 0, jsou volné úseky.
  4. Spočítat délku oblouku kružnice každého takového úseku, všechny je sečíst dohromady a normalizovat.
  5. Postup lze technicky realizovat pomocí radiálního řazení koncových bodů.
  6. Výsledek převést na procenta, zaokrouhlit a vypsat na výstup.

Příklad zdrojového kódu:

import java.awt.Point; import java.util.ArrayList; import java.util.Comparator; import java.util.Scanner; public class Pizza { private static ArrayList<Pair<Point, Point>> givenPoints = new ArrayList<Pair<Point, Point>>(); private static Scanner sc = new Scanner(System.in); public static void main(String[] args) { loadData(); System.out.println(String.format("%d%%", getResult())); } public static DoublePair getMiddlePoint(Point a, Point b) { double xDiff = (a.x-b.x)/2.0; double yDiff = (a.y-b.y)/2.0; return new DoublePair(b.x+xDiff, b.y+yDiff); } static class AnglePointComparator implements Comparator<AnglePoint> { @Override public int compare(AnglePoint o1, AnglePoint o2) { return o1.compareTo(o2); } } static class AnglePoint implements Comparable<AnglePoint> { private Double degrees, x, y; public AnglePoint(Double x, Double y) { this.x = x; this.y = y; degrees = getAngle(); } public AnglePoint(int x, int y) { this((double)x, (double)y); } public Double getAngle() { double angle = Math.atan2(y, x); if (angle <= 0) { angle = 2*Math.PI+angle; } return Math.toDegrees(angle); } @Override public int compareTo(AnglePoint o) { return degrees.compareTo(o.degrees); } @Override public String toString() { return String.format("[%d, %d] %.2f", x, y, degrees); } } public static int getResult() { ArrayList<DoublePair> triangles = new ArrayList<DoublePair>(); for (Pair<Point, Point> givenPoint : givenPoints) { Triangle triangle = new Triangle(givenPoint.key, givenPoint.value); triangles.addAll(triangle.calculate()); } triangles.sort(new DoublePairComparator()); ArrayList<DoublePair> newTriangles = new ArrayList<DoublePair>(); DoublePair current = null; for (DoublePair triangle : triangles) { if (current != null) { if (canMerge(current, triangle)) { current = mergeIntervals(current, triangle); } else { newTriangles.add(current); current = triangle; } } else { current = triangle; } } if (current != null) { newTriangles.add(current); } double badPointPercentage = 0; for (DoublePair triangle : newTriangles) { badPointPercentage += triangle.value - triangle.key; } badPointPercentage = (badPointPercentage / 360.0) * 100; int goodPointPercentage = (int) Math.round(100 - badPointPercentage); return goodPointPercentage; } private static boolean canMerge(DoublePair smaller, DoublePair bigger) { boolean first = smaller.key.compareTo(bigger.key) < 1; boolean second = bigger.key.compareTo(smaller.value) < 1; return first && second; } public static DoublePair mergeIntervals(DoublePair interval1, DoublePair interval2) { double min = Math.min(interval1.key, interval2.key); double max = Math.max(interval1.value, interval2.value); return new DoublePair(min, max); } static class Triangle { private Point pointA, pointB; public Triangle(Point calcPoint, Point otherPoint) { this.pointA = otherPoint; this.pointB = calcPoint; } public ArrayList<DoublePair> calculate() { ArrayList<DoublePair> pairs = new ArrayList<DoublePair>(); double angle = getAngleFromThreePoints(pointB, pointA); DoublePair middle = getMiddlePoint(pointA, pointB); ArrayList<AnglePoint> anglePoints = new ArrayList<AnglePoint>(); AnglePoint middlePoint = new AnglePoint(middle.key, middle.value); AnglePoint anglePointA = new AnglePoint(pointA.x, pointA.y); AnglePoint anglePointB = new AnglePoint(pointB.x, pointB.y); anglePoints.add(middlePoint); anglePoints.add(anglePointA); anglePoints.add(anglePointB); anglePoints.sort(new AnglePointComparator()); int middleIndex = anglePoints.indexOf(middlePoint); int mainIndex = middleIndex == 0 ? anglePoints.size()-1 : middleIndex-1; double position = anglePoints.get(mainIndex).degrees; angle += position; while (angle >= 360 && position >= 360) { angle -= 360; position -= 360; } if (angle > 360) { pairs.add(new DoublePair(position, 359.99999)); pairs.add(new DoublePair(0.0, angle - 360)); } else if (angle == 360) { pairs.add(new DoublePair(position, 359.99999)); } else { pairs.add(new DoublePair(position, angle)); } return pairs; } } public static double getAngleFromThreeSides(double side1, double side2, double opposite) { double numerator = Math.pow(side1, 2) + Math.pow(side2, 2) - Math.pow(opposite, 2); double denominator = 2 * side1 * side2; return Math.toDegrees(Math.acos(numerator / denominator)); } public static double getAngleFromThreePoints(Point nonZeroPointA, Point nonZeroPointB) { Point c = new Point(0, 0); double distanceC = getDistance(nonZeroPointA, nonZeroPointB); double distanceB = getDistance(nonZeroPointA, c); double distanceA = getDistance(nonZeroPointB, c); return getAngleFromThreeSides(distanceA, distanceB, distanceC); } public static void loadData() { int numOfPairs = Integer.valueOf(sc.nextLine()); for (int i = 0; i < numOfPairs; i++) { String[] line = sc.nextLine().split(" "); Point point1 = new Point(Integer.valueOf(line[0]), Integer.valueOf(line[1])); Point point2 = new Point(Integer.valueOf(line[2]), Integer.valueOf(line[3])); givenPoints.add(new Pair<Point, Point>(point1, point2)); } } public static double getDistance(Point a, Point b) { double xDiff = Math.abs(a.x - b.x); double yDiff = Math.abs(a.y - b.y); double distance = Math.sqrt(Math.pow(xDiff, 2) + Math.pow(yDiff, 2)); return distance; } static class DoublePairComparator implements Comparator<DoublePair> { @Override public int compare(DoublePair o1, DoublePair o2) { return o1.compareTo(o2); } } static class DoublePair implements Comparable<DoublePair> { private Double key; private Double value; public DoublePair(Double key, Double value) { this.key = key; this.value = value; } public Double getKey() { return key; } public Double getValue() { return value; } @Override public int compareTo(Pizza.DoublePair o) { if (!key.equals(o.key)) { return key.compareTo(o.key); } else { return value.compareTo(o.value); } } @Override public String toString() { return String.format("%s %s", key.toString(), value.toString()); } } static class Pair<X, Y> { private X key; private Y value; public Pair(X key, Y value) { this.key = key; this.value = value; } public X getKey() { return key; } public Y getValue() { return value; } @Override public String toString() { return String.format("%s %s", key.toString(), value.toString()); } } }

Registrační systém

  1. Úloha popisuje frontu, kde se nové prvky přidávají na konec, ale prvky pro zpracování se vybírají na náhodných pozicích. Pro každý vybraný prvek je třeba určit počet předchůdců. Problémem je složitost operací odstranění prvku a počítání předchůdců, aby nebylo nutné sekvenčně prohledávat frontu.
  2. To lze docílit vlastní implementací binárního vyhledávacího stromu (BST). Při použití stromu se lze vyhnout průběžnému vyvažování, pokud je strom zkonstruován hned pro všechny prvky na vstupu, i když při mazání prvků bude vyváženost stromu postupně degradovat.
  3. Pro výpočet pořadí prvku si v každém uzlu stromu udržovat počet prvků v celém jeho podstromu. Pro výpočet počtu předchůdců vybraného prvku se ve stromě vydat od tohoto prvku směrem ke kořeni a přičítat počty prvků z levých podstromů, kde to bude nutné.

Příklad zdrojového kódu:

#include <bits/stdc++.h> using namespace std; #define MOD 1000007 int n; int druhySort=0; int tree[200000]; struct X { char t; unsigned int poradi; char id[20]; int cas; int k; } pole[200000]; bool operator < (X a, X b) { if(druhySort) { if(a.poradi<=b.poradi) return 1; return 0; } for(int i=0; i<20; i++) { if(a.id[i]<b.id[i]) return 1; if(a.id[i]>b.id[i]) return 0; } if(a.t=='i') return 1; if(b.t=='i') return 0; return 1; } void pricti(unsigned int index, int co) { while(index<=n) { tree[index]+=co; index = index + (index & (-index)); } } int suma(unsigned int index) { int soucet=0; while(index>0) { soucet += tree[index]; index = index & (index-1); } return soucet; } int main() { int k=0; cin >> n; for(int i=0; i<n; i++) { cin >> pole[i].t >> pole[i].id >> pole[i].cas; pole[i].poradi=i; if(pole[i].t=='i') { pole[i].k=k++; } } sort(pole, pole+n); for(int i=0; i<n; i++) { if(pole[i].t=='o') { pole[i].k=pole[i-1].k; pole[i].cas-=pole[i-1].cas; } } druhySort=1; sort(pole, pole+n); /*for(int i=0; i<n; i++) cout << pole[i].t << " " << pole[i].id << " " << pole[i].k << endl;*/ int nedok=0; for(int i=0; i<n; i++) { if(pole[i].t=='i') { nedok++; pricti(pole[i].k+1, 1); } else { int pred=suma(pole[i].k); nedok--; int nas = nedok - pred; //cout << pole[i].k << " "; cout << pole[i].id << " " << pole[i].cas << " " << pred << " " << nas << endl; pricti(pole[i].k+1, -1); } //for(int i=0; i<n; i++) cout << suma(i) << " "; //cout << endl; } return 0; }

Řeky

  1. Načíst si počet řek a následně jednotlivé řeky a uložit je do vhodné struktury.
  2. Říční síť má charakter grafu, kde vrcholy reprezentují jednotlivé přístavy, jezy a soutoky. Graf má topologii lesa - každá komponenta souvislosti je strom, a v našem případě má každý takový strom i svůj kořen (poslední místo na řece, která se nikam nevlévá).
  3. Pro každý strom spustit prohledávání do hloubky (DFS) směrem od kořene k listům. Při DFS si udržovat cestu od kořene do aktuálního vrcholu v poli.
  4. Pro každý vrchol na této cestě si poznamenat jeho vzdálenost od kořene a kumulovaný součet všech jezů. Pro aktuální vrchol tak lze spekulovat, že by mohl být startovním vrcholem trasy požadované délky a dohledat pro něj příslušný koncový vrchol pomocí binárního vyhledávání v poli.
  5. Díky akumulovanému součtu jezů pak můžeme pouhým odečtením dvou hodnot spočítat počet jezů, které se nacházejí na trase. Vyhovující trasy vypsat v pořadovaném formátu na výstup.
  6. Protože ale už samotné parsování vstupních dat a reprezentace říční sítě byly poněkud pracnější úkony, v testovacích datech byla jistá benevolence, aby prošlo i méně efektivní řešení bez využití binárního hledání a v každém datasetu byl jen jeden strom.

Příklad zdrojového kódu:

#include <iostream> #include <vector> #include <string> #include <sstream> #include <algorithm> using std::cout; using std::cin; using std::string; using std::vector; using std::pair; vector<string> river_names; vector<vector<int>> rivers; vector<vector<pair<int, vector<int>>>> ports; int get_river_ind(string name) { for (unsigned int i = 0; i < river_names.size(); i++) if (river_names[i] == name) return i; return -1; } /* vector<int> get_next_port(int port_ind, int riv_ind) { if (ports[riv_ind].size() > port_ind + 1) { // kdyz na tehle rece return vector<int>{port_ind + 1, riv_ind}; } // rivers[riv_ind][0] je reka do ktere se vleva a rivers[riv_ind][1] je misto kde se vleva int port = get_port_index_by_dist(rivers[riv_ind][0], rivers[riv_ind][1]); return vector<int>(port, rivers[riv_ind][0]); } vector<int> get_port_index_by_dist(int riv_ind, int dist) { for (unsigned int i = 0; i < ports[riv_ind].size(); i++) { if (ports[riv_ind][i].first <= dist) } //return -1; } */ int am_below(vector<int> weirs, int above) { int n = 0; for (unsigned int i = 0; i < weirs.size(); i++) { if (weirs[i] <= above) n++; } return n; } vector<int> next_port(int port_id, int riv_id) { // kdyz na tehle rece if (ports[riv_id].size()-1 > port_id + 1) { //cout << "X\n"; return vector<int>{port_id + 1, riv_id, ports[riv_id][port_id].first-ports[riv_id][port_id + 1].first, (int)ports[riv_id][port_id + 1].second.size()}; } // kdyz se vleva do jine reky int len = ports[riv_id][port_id].first; int new_river_id = rivers[riv_id][0]; int new_port_id; int place = rivers[riv_id][1]; int weirs = ports[riv_id][ports[riv_id].size() - 1].second.size(); //cout << "a " << weirs << "\n"; bool found = false; if (new_river_id == -1) return vector<int>{-1}; while (!found) { for (unsigned int i = 0; i < ports[new_river_id].size() - 1; i++) { if (ports[new_river_id][i].first <= place) { //cout << ":" << i << " " << ports[new_river_id][i].first << " " << ports[new_river_id].size() << "\n"; weirs += am_below(ports[new_river_id][i].second, place); //cout << "b " << weirs << "\n"; len += place - ports[new_river_id][i].first; place = ports[new_river_id][i].first; found = true; new_port_id = i; break; } } if (!found) { weirs += am_below(ports[new_river_id][ports[new_river_id].size() - 1].second, place); //cout << "c " << weirs << "\n"; len += place; place = rivers[new_river_id][1]; new_river_id = rivers[new_river_id][0]; if (new_river_id == -1) return vector<int>{-1}; } } //cout << "d " << weirs << "\n"; return vector<int>{new_port_id, new_river_id, len, weirs}; } int main() { unsigned int rivers_am; cin >> rivers_am; cin.ignore(); // this prevent getline from giving the first line as an empty line for (unsigned int i = 0; i < rivers_am; i++) { // Deals with river names string word; string tm; string main_name = ""; string second_name = ""; int vleva = -1; bool has_second_name = false; std::getline(cin, tm); std::istringstream st(tm); while (st >> word) { if (word == ">") { has_second_name = true; continue; } if (has_second_name) { char* p; strtol(word.c_str(), &p, 10); if (*p == 0) { vleva = std::stoi(word); } else { second_name += word + " "; } } else { main_name += word + " "; } } river_names.push_back(main_name); rivers.push_back(vector<int>{-1, -1}); ports.push_back(vector<pair<int, vector<int>>>{}); int riv_ind = get_river_ind(main_name); if (has_second_name) { rivers[riv_ind] = vector<int>{get_river_ind(second_name), vleva}; } // Deals with river points unsigned int points_am; cin >> points_am; vector<int> ports_tm; vector<int> weirs_tm; for (unsigned int j = 0; j < points_am; j++) { unsigned int place; string thing; cin >> place >> thing; cin.ignore(); if (thing == "jez") weirs_tm.push_back(place); else ports_tm.push_back(place); } std::sort(ports_tm.begin(), ports_tm.end(), std::greater<int>()); std::sort(weirs_tm.begin(), weirs_tm.end(), std::greater<int>()); for (unsigned int j = 0; j < ports_tm.size(); j++) { vector<int> n; if (j == 0) { for (unsigned int k = 0; k < weirs_tm.size(); k++) { if (weirs_tm[k] > ports_tm[j]) n.push_back(weirs_tm[k]); } } else { for (unsigned int k = 0; k < weirs_tm.size(); k++) { if (weirs_tm[k] > ports_tm[j] && weirs_tm[k] < ports_tm[j-1]) n.push_back(weirs_tm[k]); } } ports[riv_ind].push_back(pair<int, vector<int>>{ports_tm[j], n}); } vector<int> n; if (!ports_tm.empty()) { for (unsigned int k = 0; k < weirs_tm.size(); k++) { if (weirs_tm[k] < ports_tm[ports_tm.size()-1]) n.push_back(weirs_tm[k]); } } ports[riv_ind].push_back(pair<int, vector<int>>{-1, n}); // for weirs that are lower than any port } unsigned int trip_len; cin >> trip_len; cin.ignore(); for (unsigned int i = 0; i < rivers_am; i++) { for (int j = (int)ports[i].size() - 2; j >= 0; j--) { //if (j == ports[i].size() - 2 && rivers[i][0] == -1) continue; //cout << i << " " << j << "\n"; int len = 0; int end_river_id = i; int wier_am = 0; int port_id = j; bool broken = false; while (len < trip_len) { //cout << "USING: " << port_id << " " << end_river_id << " " << wier_am << "\n"; vector<int> x = next_port(port_id, end_river_id); /*for (int n = 0; n < x.size(); n++) cout << x[n] << " "; cout << "\n";*/ if (x[0] == -1) { broken = true; break; } port_id = x[0]; end_river_id = x[1]; len += x[2]; wier_am += x[3]; } if (!broken) cout << river_names[i] << ports[i][j].first << " -> " << river_names[end_river_id] << ports[end_river_id][port_id].first << " " << len << " " << wier_am << "\n"; //else cout << "_\n"; } } //cout << "\n"; //DEBUG /*for (unsigned int i = 0; i < rivers_am; i++) { cout << river_names[i] << " "; for (unsigned int j = 0; j < ports[i].size(); j++) { cout << ports[i][j].first << ": "; for (unsigned int k = 0; k < ports[i][j].second.size(); k++) cout << ports[i][j].second[k] << ", "; } cout << "\n"; }*/ }

Tunelín

  1. Načíst si počet odběrných míst a index elektrárny a následně propojení jednotlivých míst a uložit si je jako ohodnocený neorientovaný graf zadaný maticí sousednosti.
  2. Najít minimální kostru grafu, což lze např. pomocí Kruskalova algoritmu.
  3. Délku minimální kostry vypsat na výstup.

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 pptunelin; import java.util.Scanner; /** * * @author ondra */ public class PPTunelin { /** * @param args the command line arguments */ public static void main(String[] args) { Scanner sc = new Scanner(System.in, "Windows-1250"); String a = (sc.nextLine()); String[] cisla = a.split(" "); int mista = Integer.parseInt(cisla[0]); int elektrarna = Integer.parseInt(cisla[1]); int i=0; int mp=0; int p=0; int vysledek = 0; int pripojeno[] = new int[200]; for (i = 0; i < mista; i++) { pripojeno[i] = 0; } int[][] delka =new int[200][200]; for (i=0;i<mista;i++){ a = (sc.nextLine()); cisla = a.split(" "); for (p=0;p<mista;p++){ delka[i][p]=Integer.parseInt(cisla[p]); } } //přečteno pripojeno[0]=elektrarna; int nejmensi=251; int nejmensix=0; int nejmensiy=0; for (p=0;p<mista;p++){ if (delka[elektrarna-1][p]!=0){ if (delka[elektrarna-1][p]<nejmensi){ nejmensi=delka[elektrarna-1][p]; nejmensix=p; } } } vysledek=vysledek+nejmensi; delka[elektrarna-1][nejmensix]=0; delka[nejmensix][elektrarna-1]=0; pripojeno[1]=nejmensix+1; nejmensi=251; for (i=0;i<mista;i++){ delka[i][nejmensix]=0; } for (i=0;i<mista;i++){ delka[i][elektrarna-1]=0; } for (mp=2;mp<mista;mp++){ for (i=0;i<mp;i++){ elektrarna = pripojeno[i]; for (p=0;p<mista;p++){ if (delka[elektrarna-1][p]!=0){ if (delka[elektrarna-1][p]<nejmensi){ nejmensi=delka[elektrarna-1][p]; nejmensix=p; nejmensiy=elektrarna-1; } } } } vysledek=vysledek+nejmensi; pripojeno[mp]=nejmensix+1; delka[nejmensiy][nejmensix]=0; delka[nejmensix][nejmensiy]=0; nejmensi=251; for (i=0;i<mista;i++){ delka[i][nejmensix]=0; } } System.out.println(vysledek); } }

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.

Moderní umění

  1. Načíst si minimální počet teček, rozměr plátna a následně celé plátno a uložit si ho např. do dvourozměrného pole (jeden bod představuje jeden pixel).
  2. Pro určení počtu teček ve výřezu použít prefixový součet ve 2D (PS[i, j] je počet teček v obdélníku od [1, 1] po [i, j]).
  3. Pro výřez šířky w a h spočítat maximální počet teček zachytitelný tímto výřezem pomocí posouvání výřezu z levého horního rohu do pravého dolního rohu a hledáním maxima.
  4. Vytvořit si matici přijatelnosti výřezu, kdy sloupce matice repezentují šířku výřezu a řádky výšku výřezu. Hodnoty v matici jsou 0, pokud výřez přijatený není, a 1, pokud výřez přijatelný je (tj. je alespoň 1 x 1 a obsahuje alespoň požadovaný počet teček).
  5. Pokud je přijatelný výřez o dané šířce a výšce, pak jsou přijatelné i všechny širší a/nebo vyšší výřezy. V matici tak vzniká souvislá oblast nul a jedniček, jejíž hranici (linie jedniček) lze vytrasovat a vyhnout se tak vyhodnocování všech políček.
  6. Z linie jedniček vybrat jen přijatelné rozměry výřezů s minimální plochou.
  7. Pro každý vybraný výřez projít celou matici a najít všechny konkrétní vyhovující výřezy a seřadit je.
  8. Vypsat minimální plochu výřezu a dále nalezené seřazené výřezy.

Příklad zdrojového kódu:

#include <bits/stdc++.h> using namespace std; #define MAX 61234567 int pre[500][500]; char in[500][500]; struct X { int t; int a, b, c, d; } out[2000]; bool operator <(X a, X b) { if(a.t<b.t) return 1; if(a.t == b.t and a.a < b.a) return 1; if(a.t == b.t and a.a == b.a and a.b < b.b) return 1; if(a.t == b.t and a.a == b.a and a.b == b.b and a.c < b.c) return 1; if(a.t == b.t and a.a == b.a and a.b == b.b and a.c == b.c and a.d<=b.d) return 1; return 0; } int velikost; int n, m; int main() { cin >> m; cin >> n; for(int i=0; i<n; i++) cin >> in[i]; for(int i=1; i<=n; i++) { for(int j=1; j<=n; j++) { pre[i][j]=pre[i][j-1]+pre[i-1][j]-pre[i-1][j-1]+in[i-1][j-1]-'0'; } } velikost = n*n; n++; for(int i=0; i<n; i++) { for(int j=0; j<n; j++) { int b=1; for(int a=0; a<n; a++) { while(pre[j][b]-pre[j][a]-pre[i][b]+pre[i][a]<m and b<450) b++; if(b==450) break; velikost = min(velikost, (j-i)*(b-a)); } } } int mo=0; for(int i=0; i<n; i++) { for(int j=0; j<n; j++) { int b=1; for(int a=0; a<n; a++) { while(pre[j][b]-pre[j][a]-pre[i][b]+pre[i][a]<m and b<450) b++; if(b==450) break; if(velikost ==(j-i)*(b-a)) { out[mo].t=pre[j][b]-pre[j][a]-pre[i][b]+pre[i][a]; out[mo].a = i+1; out[mo].b = a+1; out[mo].c = j; out[mo].d = b; mo++; } } } } cout << velikost << endl; sort(out, out+mo); for(int i=0; i<mo; i++) cout << out[i].t << " " << out[i].a << " " << out[i].b << " " << out[i].c << " " << out[i].d << endl; }

Dámy v ohrožení

  1. Načíst si počet dam a jejich jednotlivé souřadnice a uložit si je.
  2. Určit si velikost čtvercové šachovnice podle maxima ze souřadnic královen.
  3. Udělat si např. pole celých čísel reprezentující sloupce, řádky a jednu a druhou diagonálu (pro každou diagonálu je potřeba dvojnásobný počet prvků).
  4. Každou dámu započítat do jejího řádku, sloupce a diagonál.
  5. Pro každou dámu spočítat ostatní dámy ve stejném řádku, sloupci a na diagonálách.
  6. Po průchodu všech dam vypsat maximum.

Příklad zdrojového kódu:

#include <bits/stdc++.h> using namespace std; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int d; cin >> d; vector<pair<int, int>> D(d); vector<int> r(1E6 + 5), s(1E6 + 5), d1(2E6 + 5), d2(2E6 + 5); for (int i = 0; i < d; ++i) { int x, y; cin >> x >> y; x--; y--; D[i] = make_pair(x, y); s[x]++; r[y]++; d1[x + y]++; d2[x - y + 1E6]++; } int max_o = 0; for (pair<int, int> a : D) { int x = a.first, y = a.second; int o = s[x] + r[y] + d1[x + y] + d2[x - y + 1E6] - 4; max_o = max(o, max_o); } cout << max_o << "\n"; }

Ostrovy

  1. Načíst si počet řádek a sloupců mapy a následně mapu po řádkách. Mapu si uložit jako dvourozměrné pole celočíselných výšek.
  2. Připravit si záplavovou mapu, kde ZM[i][j] bude výška hladiny, na které bude pojíčko [i, j] poprvé zaplaveno vodou. Naplnit pomocí simulace vzestupu hladiny z 0 do maxima pomocí prohledávání do šířky (BFS) ve 4-okolí s prioritní frontou, která servíruje níže položená políčka dřív než výše položená políčka. BFS začíná na vnějším okraji mapy (hladina 0). Do aktuálně zpracovávaného políčka ukládá maximum z jeho výšky a maxima výšek dříve zpracovaných políček.
  3. Na záplavové mapě simulovat sestup hladiny vody z maxima až do 0:
    1. Seznam políček [i, j] seřadit sestupně podle ZM[i][j] a zpracovat v tomto pořadí (tj. objevovat políčka ostrovů).
    2. Každé objevené políčko připojit do skupiny políček existujících ostrovů (až 8 sousedů). Použít disjoint-set DS (union-find) pro udržování a detekci spojování skupin.
    3. U každé skupiny udržovat počet členů (tj. rozlohu ostrova). Spojení skupin vede k úpravě rozlohy ostrova a tedy k úpravě mediánu.
    4. Těsně před zpracováním každého nového políčka je potřeba hlídat změnu hladiny, počtu ostrovů, mediánu rozlohy oproti poslednímu výsledku, a buď nahradit poslední výsledek, nebo přidat další do seznamu. Nakonec seznam otočit.
  4. Pro výpočet mediánu je možné využít dynamicky udržovanou seřazenou posloupnost prvků nebo strom (AVL nebo red-black) a nalézt prostřední prvek či prostřední dvojici prvků

Příklad zdrojového kódu:

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

Šifrovaná zpráva

  1. Načíst si počet zpráv.
  2. Pro každou zprávu načíst typ převodu, klíč a text.
  3. Pokud se jedná o šifrování:
    1. Z textu odstranit mezery (tyto nebudou kódovány).
    2. Vytvořit tabulku s počtem sloupců podle délky klíče a počtem řádek podle délky zprávy.
    3. Zapsat text po řádcích do tabulky. Poslední řádek tabulky doplnit mezerami, pokud je potřeba.
    4. Seřadit písmena klíče a odpovídající sloupce tabulky vzestupně stabilním algoritmem řazení.
    5. Projít tabulku po sloupcích, ze znaků vytvořit řetězec.
  4. Pokud se jedná o dešifrování:
    1. Vytvořit tabulku s počet sloupců podle délky klíče a počtem řádek podle délky zprávy.
    2. Zapsat text po sloupcích do tabulky.
    3. Seřadit písmena klíče vzestupně stabilním algoritmem a pomocí této informace zjistit původní (tj. nepřeházené) pozice sloupců.
    4. Dát sloupce do původních pozic
    5. Projít tabulku po řádcích, ze znaků vytvořit řetězec, odstranit všechny mezery na konci řetězce.
  5. Výsledný řetězec vypsat.

Příklad zdrojového kódu:

#include <bits/stdc++.h> using namespace std; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int z; cin >> z; for (int i = 0; i < z; ++i) { char c; cin >> c; string k, t, k_s; cin.ignore(); getline(cin, k); getline(cin, t); k_s = k; sort(k_s.begin(), k_s.end()); if (c == 'Z') { t.erase(remove(t.begin(), t.end(), ' '), t.end()); vector<int> order(k.size()); for (int j = 0; j < k.size(); ++j) { int index = k.find(k_s[0]); order[j] = index; k_s.erase(0, 1); k[index] = 'a'; } for (int j = 0; j < order.size(); ++j) { for (int l = 0; l < ceil(float(t.size()) / order.size()); ++l) { int index = order[j] + l * order.size(); if (index < t.size()) cout << t[index]; else cout << " "; } } } else { vector<int> order(k.size()); for (int j = 0; j < k.size(); ++j) { int index = k.find(k_s[0]); order[index] = j; k_s.erase(0, 1); k[index] = 'a'; } for (int l = 0; l < ceil(float(t.size()) / order.size()); ++l) { for (int j = 0; j < order.size(); ++j) { int index = order[j] * ceil(float(t.size()) / k.size()) + l; if (index < t.size()) cout << t[index]; else cout << " "; } } } cout << "\n"; } } //1 //Z PETR //ODPOVED JE PATNACT

Zachraňte Sněhurku

  1. Načíst si celkovou délku trasy, počet úseků a jejich jednotlivé délky a uložit si je. Načíst si počet houbinek a následně načíst a uložit pozice a ceny hub jednotlivých houbinek.
  2. Úlohu vyřešit pomocí dynamického programování.
  3. M[i, j, k] je minimální cesta ze startu do i-tého kilometru, aby stav zásob byl j hříbků a k muchomůrek.
  4. To určit jako minimum ze 4 možných variant:
    1. M[i - 1, j + 1, k] - konzumace 1 hříbku (i > 0, j + 1 + k <= nosnost a i není „muchomůrkový“)
    2. M[i - 1, j, k + 1] konzumace 1 muchomůrky (pokud i > 0 a j + k + 1 <= nosnost)
    3. M[i, j - 1, k] + h nákup 1 hříbku na pozici i za cenu h (pokud j > 0 a h různo od 0)
    4. M[i, j, k - 1] + m nákup 1 muchomůrky na pozici i za cenu m (pokud k > 0 a m různo od 0)
  5. Minimální délku ručit jako min(M[cíl, *, *]) a vypsat ji.

Příklad zdrojového kódu:

#include <bits/stdc++.h> using namespace std; #define MAX 61234567 int pole[31234][123][123]; int useky[400]; int typ[31234]; pair <int, int> nakupy[31234]; int h; int d; int u; int main() { cin >> d; cin >> u; for(int i=0; i<u; i++) cin >> useky[i]; cin >> h; for(int i=0; i<h; i++) { int pom; cin >> pom; cin >> nakupy[pom].first >> nakupy[pom].second; } for(int i=0; i<=d; i++) { for(int k=0; k<=102; k++) { for(int j=0; j+k<=102; j++) pole[i][j][k]=40000000; } } int kde=1; int suma = 0; for(int i=0; i<u; i++) { suma += useky[i]; while(kde<=suma) typ[kde++]=i%2; } //for(int i=0; i<d; i++) cout << typ[i+1]; //cout << endl; for(int i=0; i<=100; i++) { if(nakupy[0].first==0 and i) break; for(int j=0; i+j<=100; j++) { if(nakupy[0].second==0 and j) break; pole[0][i][j]=i*nakupy[0].first+j*nakupy[0].second; //cout << pole[0][i][j] << " " << i << " " << j << endl; } } /////////////////////// for(int w=1; w<=d; w++) { // cout << w << ":" << endl; for(int i=0; i<=100; i++) { for(int j=0; i+j<=100; j++) { pole[w][i][j]=pole[w-1][i][j+1]; if(typ[w]==0) pole[w][i][j]=min(pole[w][i][j], pole[w-1][i+1][j]); if(nakupy[w].first and i) pole[w][i][j]=min(pole[w][i][j], pole[w][i-1][j]+nakupy[w].first); if(nakupy[w].second and j) pole[w][i][j]=min(pole[w][i][j], pole[w][i][j-1]+nakupy[w].second); } } /*for(int i=0; i<=100; i++) { for(int j=0; i+j<=100; j++) { if(nakupy[w].first and i) pole[w][i][j]=min(pole[w][i][j], pole[w][i-1][j]+nakupy[w].first); if(nakupy[w].second and j) pole[w][i][j]=min(pole[w][i][j], pole[w][i][j-1]+nakupy[w].second); //if(pole[w][i][j]<40000000 and i+j<=3) cout << i << " " << j << " " << pole[w][i][j] << endl; } }*/ } int out = 40000000; for(int i=0; i<=100; i++) { for(int j=0; j+i<=100; j++) { out = min (out, pole[d][i][j]); } } if(out >= 40000000) cout << 0 << endl; else cout << out << endl; return 0; }