PilsProg 2024

Výsledky Lite

#	Jméno	Příjmení	Splněných úloh	Čas
1	Matyáš	Vítek	9	10,227
2	Lukáš	Patejdl	9	43,213
3	Petr	Zaoral	9	317,119
4	Jan	Brichcín	9	356,246
5	Štefan	Prokop	9	652,246
6	David	Janovský	7	155,529
7	David	Macner	6	73,041
8	Michal	Špelina	6	579,748
9	Jakub	Pulinger	5	376,968
10	Filip	Fischer	3	134,890
11	Jakub	Kašák	1	142,755
12	Kristián	Maas	1	143,967

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

Výsledky kvalifikace

#	Jméno	Příjmení	Splněných úloh	Čas	Finále
1	Jáchym	Kouba	6	49,718	Postupuje do finále
2	Matyáš	Vítek	6	832,402	Postupuje do finále
3	Hlib	Arseniuk	5	283,896	Postupuje do finále
4	Anna-Kristina	Migel	5	547,544	Postupuje do finále
5	Petr	Starý	5	2 252,759	Postupuje do finále
6	Erik	Ježek	5	5 017,888	Postupuje do finále
7	Matyáš	David	4	186,949	Postupuje do finále
8	Jan	Brichcín	4	243,128	Postupuje do finále
9	David	Macner	4	264,787	Postupuje do finále
10	Michal	Špelina	4	2 889,613	Postupuje do finále
11	Lucian	Poljak	4	4 742,560	Postupuje do finále
12	Petr	Zaoral	3	160,344	Postupuje do finále
13	Ondřej	Bartoš	3	446,892	Postupuje do finále
14	Jakub	Svítek	3	705,708	Postupuje do finále
15	Lukáš	Patejdl	1	4,239	-
16	Tomáš	Zlámal	1	7,687	-
17	Štefan	Prokop	1	92,430	-
18	Štěpán	Kuch	1	98,959	-
19	Alexandr	Vituško	1	170,497	-
20	Jakub	Urban	1	188,267	-
21	Václav	Zach	1	485,002	-

Výsledky finále

#	Jméno	Příjmení	Splněných úloh	Čas
1	Jáchym	Kouba	3	6,128
2	Matyáš	Vítek	2	1,347
3	Jakub	Svítek	2	1,799
4	Erik	Ježek	2	2,018
5	Anna-Kristina	Migel	2	2,227
6	Petr	Zaoral	2	2,450
7	Ondřej	Bartoš	2	2,963
8	Jan	Brichcín	2	3,342
9	Lucian	Poljak	2	3,412
10	Petr	Starý	2	4,109
11	Matyáš	David	1	1,260
12	David	Macner	1	2,684
13	Michal	Špelina	0	0,000
14	Hlib	Arseniuk	0	0,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ů
AxB	1701	39
AplusB	1702	34
Největší ze tří celých čísel	1703	31
Pascalův trojúhelník	1704	18

Lite1 úlohy

Název	Číslo	Úspěšných řešitelů
Malá násobilka	2411	7
Meziměna	2412	6
Řazení hvězdiček	2413	7

Lite2 úlohy

Název	Číslo	Úspěšných řešitelů
Délka filmu	2414	9
Histogram	2415	9
Zrcadlová matice	2416	9

Lite3 úlohy

Název	Číslo	Úspěšných řešitelů
Filtr hodnot	2417	9
Index minima	2418	9
Symetrická matice	2419	9

Kvalifikační úlohy

Název	Číslo	Úspěšných řešitelů
Pálivá sklizeň	2421	8
Stupnice pálivosti	2422	21
Výběrové zemědělství	2423	4
Výroba omáček	2424	10
Zalévání papriček	2425	12
Zeď proti škůdcům	2426	13

Finálové úlohy

Název	Číslo	Úspěšných řešitelů
Kivule berou	2431	10
Líný cyklista	2432	1
Okresní silnice	2433	0
Poštovní pevnost	2434	12
Schodiště	2435	0

A jaké bylo finále?

Harmonogram PilsProg 2024

Zahájení registrace: 30.10.2023
Zahájení Lite kola: 7.11.2023 14:00
- Zahájení Lite1 kola: 7.11.2023 14:00
- Ukončení Lite1 kola: 13.11.2023 14:00
- Zahájení Lite2 kola: 21.11.2023 14:00
- Ukončení Lite2 kola: 27.11.2023 14:00
- Zahájení Lite3 kola: 5.12.2023 14:00
- Ukončení Lite3 kola: 11.12.2023 14:00
Ukončení Lite kola: 11.12.2023 14:00
Zahájení kvalifikačního kola: 11.1.2024 14:00
Ukončení kvalifikačního kola: 6.3.2024 14:00
Finálové kolo: 16.3.2024 09:00 - 13:00, KIV - UC311

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.

Malá násobilka

Načíst číslo, pro které má být malá násobilka vypsána.
V cyklu se známým počtem opakování vypisovat jednotlivé řádky. Jako druhý činitel použít řídící proměnnou.
Je třeba dát si pozor na odsazení součinu, obzvláště pro číslo 10, kdy je rozdíl až o dvě místa.

Příklad zdrojového kódu:


program U2411MalaNasobilka;
  var
    n, i, d: Byte;
begin
  ReadLn(n);
  if n=10 then d:=3
  else d:=2;
  for i:=0 to 10 do WriteLn(i:2, ' x ', n, ' = ', i*n:d);
  ReadLn;
end.

Meziměna

Načíst počet testovacích případů.
Pro každý testovací případ si načíst částku v původní měně, kurz nákupu původní měny a kurz prodeje cílové měny.
Částku vynásobit kurzem nákupu a vydělit kurzem prodeje.
Vypsat výslednou částku zaokrouhlenou na dvě desetinná místa.

Příklad zdrojového kódu:


import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int count = in.nextInt();
        for (int i = 0; i < count; i++) {
            double first = in.nextDouble();
            double second = in.nextDouble();
            double third = in.nextDouble();
            double result = Math.round(first * second / third * 100) / 100.0;
            System.out.println(result);
        }
    }
}

Řazení hvězdiček

Načíst počet hvězdičkových hodnocení a následně jednotlivá hodnocení jako řetěce (řádky) do pole řetězců.
Seřadit pole libovolným řadícím algoritmem podle délky řetězců (hvězdičkových hodnocení).
Vypsat seřazené pole, každé hvězdičkové hodnocení na samostatnou řádku.

Příklad zdrojového kódu:


#include <iostream>
#include <map>
using namespace std;

int main(){
    
    int n;
    string s;
    cin>>n;
    map<string, int> m;
    m["*"]=0;
    m["**"]=0;
    m["***"]=0;
    m["****"]=0;
    m["*****"]=0;

    for (int i=0;i<n;i++){
        cin>>s;
        m[s]=m[s]+1;
    }

   for (auto it = m.rbegin(); it != m.rend(); it++) {
        for (int j = 0; j < it->second; j++) {
            cout << it->first << endl;
        }
    }
    return 0;
}

Délka filmu

Načíst počet testovacích případů.
Pro každý testovací případ si načíst oba časy a rozdělit je na hodiny a minuty.
Oba časy převést na minuty.
Pokud je počáteční čas v minutách větší než koncový čas v minutách, přičíst ke koncovému času 24 hodiny v minutách (1440 minut).
Odečíst počáteční čas od koncového a výsledek převést na hodiny a minuty.
Vypsat délku filmu v hodinách a minutách v požadovaném formátu (pozor na počáteční nuly).

Příklad zdrojového kódu:


#include <iostream>
#include <string>

int mins(const std::string &time)
{
    return std::stoi(time.substr(0, 2)) * 60 + std::stoi(time.substr(3, 2));
}

void mins2(int minuty, int &h, int &min)
{
    h = minuty / 60;
    min = minuty % 60;
}

int main()
{
    int iters{};

    std::cin >> iters;

    for (int i{}; i < iters; ++i)
    {
        std::string start, end;
        std::cin >> start >> end;

        int startMin = mins(start);
        int endMin = mins(end);

        int delka = (endMin >= startMin) ? endMin - startMin : endMin + 1440 - startMin;

        int hodinyFilm, minFilm{};
        mins2(delka, hodinyFilm, minFilm);

        std::cout << (hodinyFilm < 10 ? "0" : "") << hodinyFilm << ":" << (minFilm < 10 ? "0" : "") << minFilm << std::endl;
    }

    return 0;
}

Histogram

Načíst počet hodnot histogramu a následně jednotlivé hodnoty např. do pole.
Při načítání si určit maximální hodnotu, která udává výšku histogramu (tj. počet řádek).
Vytvořit si dvourozměrné pole znaků sloužící jako plátno pro vykreslení histogramu bez omezení standardního výstupu (kde je výpis možný pouze po řádkách).
Dle jednotlivých hodnot vykreslit do histogramu jednotlivé sloupce.
Vypsat plátno na standardní výstup po řádkách.

Příklad zdrojového kódu:


program U2415Histogram;
  var
    count, x, y, max: Byte;
    h: Array of Byte;
begin
  ReadLn(count);
  SetLength(h, count);
  max:=0;
  for x:=1 to count do begin
    Read(h[x]);
    if h[x]>max then max:=h[x];
  end;
  ReadLn;
  for y:=max downto 1 do begin
    for x:=1 to count do begin
      if h[x]>=y then Write('| ')
      else Write('. ');
    end;
    WriteLn;
  end;
  ReadLn;
end.

Zrcadlová matice

Načíst řád matice.
Vypisovat nuly jako jednotlivé prvky matice mimo vedlejší diagonálu po řádkách (např. pomocí dvou vnořených cyklů se známým počtem opakování).
Vypisovat jedničky, pokud se prvek dle indexů nachází na vedlejší diagonále.

Příklad zdrojového kódu:


program JednotkovaMatice;

var
  r, i, j: integer;

begin
  readln(r);

  for i := 1 to r do
  begin
    for j := 1 to r do
    begin
      if j = r - i + 1 then
        write('1 ')
      else
        write('0 ');
    end;
    writeln;
  end;
end.

Filtr hodnot

Načíst počet testovacích případů.
Pro každý testovací případ si načíst počet prvků posloupnosti, dolní a horní mez a následně načítat jednotlivé prvky.
Pro každý prvek ověřit, zda je v otevřeném intervalu daném dolní a horní mezí. Pokud ano, prvek vypsat (všechny do jedné řádky oddělené mezerou).
U prvního vypisovaného prvku dát pozor, aby před ním nebyla vypsána mezera.
Po vypsání posledního prvku odřádkovat.

Příklad zdrojového kódu:


package me.prokop.pilsprog.lite3.filtr;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        int inputs;
        inputs = s.nextInt();
        List<Integer> nums = new ArrayList<>();
        for (int i = 0; i < inputs; i++) {
            s.nextLine();
            nums.clear();
            int inputNums = s.nextInt();
            int min = s.nextInt();
            int max = s.nextInt();
            for (int j = 0; j < inputNums; j++) {
                int n = s.nextInt();
                if (n > min && n < max) {
                    nums.add(n);
                }
            }
            System.out.println(nums.toString().replace("[", "").replace("]", "").replace(",", ""));
        }
    }
}

Index minima

Načíst počet testovacích případů.
Pro každý testovací případ si načíst počet hodnot a následně načítat jednotlivé hodnoty.
U každé hodnoty ověřit, jestli se nejedná o aktuální minimum. Pokud ano, zaznamenat si hodnotu jako aktuální minimum a její index.
Po ověření všech čísel vypsat uložený index minima.

Příklad zdrojového kódu:


#include <iostream>

using namespace std;

int main()
{
    int t{};
    int p{};
    int nc{};
    cin >> t;
    for (int i{}; i < t; i++)
    {
        cin >> p;
        int x = 0;
        int cisla[p];
        for (int ii{}; ii < p; ii++)
        {
            cin >> cisla[ii];
        }
        nc = cisla[0];
        for (int s = 1; s < p; s++)
        {
            if (cisla[s] < nc)
            {
                nc = cisla[s];
                x = s;
            }
        }
        cout << x << endl;
    }
    return 0;
}

Symetrická matice

Načíst počet testovacích případů.
Pro každý testovací případ si načíst řád matice a následně její jednotlivé prvky do dvourozměrného pole.
Projít prvky pod hlavní diagonálou a porovnávat je s odpovídajícímí prvky nad hlavní diagonálou.
Pokud je nalezen rozdíl, porovnávání předčasně ukončit a vypsat „ne“. Pokud žádný rozdíl nalezen není, vypsat „ano“.

Příklad zdrojového kódu:


package me.prokop.pilsprog.lite3.symmat;

import java.util.Scanner;

public class Main {
    public static boolean validate(int[][] m, int r) {
        for (int y = 0; y < r; y++) {
            for (int x = 0; x < r; x++) {
                if (m[y][x] != m[x][y]) {
                    return false;
                }
            }
        }
        return true;
    }
    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        int testCases = s.nextInt();
        s.nextLine();
        for (int i = 0; i < testCases; i++) {
            int matSize = s.nextInt();
            int mat[][] = new int[matSize][matSize];
            for (int j = 0; j < matSize; j++) {
                s.nextLine();
                for (int k = 0; k < matSize; k++) {
                    mat[k][j] = s.nextInt();
                }
            }
            System.out.println(validate(mat, matSize) ? "ano" : "ne");
        }
    }
}

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.

Pálivá sklizeň

Keříky a jejich skóre načíst ze vstupu do obousměrného spojového seznamu.
Simulovat a počítat sklízecí cykly od prvního až po poslední, kdy už není co sklidit. Keříky ke sklizni uchovávat v pomocné frontě.
Simulovat nanečisto 1. sklízecí cyklus. Projít celý spojový seznam a kontrolovat podmínku skliditelnosti u každého keříku. Je-li keřík skliditelný, označit si u něj, že bude sklizen v 1. sklízecím cyklu a zařadit jej do pomocné fronty.
Opakovat, dokud není pomocná fronta prázdná:
- Vyjmout keřík z fronty. Zkontrolovat zda následník v seznamu lze sklidit vůči předchůdci (v příštím cyklu).
- Pokud lze sklidit, zapamatovat si u něj čas sklizně o jedna větší než u keříku vytaženého z fronty.
- Sklidit keřík, který byl vytažen z fronty (odstranit ho ze seznamu).
Vypsat čas sklizně posledního keříku vytaženého z fronty.

Příklad zdrojového kódu:



import java.util.Scanner;

/**
 * Ukol1
 */
public class PalivaSklizen {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int pocetKeru = Integer.parseInt(sc.nextLine());
        String[] kereTxT = sc.nextLine().split(" ");
        sc.close();
        int[] kere = new int[pocetKeru];
        int[] maxPocetProKazdeho = new int[pocetKeru];
        for (int i = 0; i < maxPocetProKazdeho.length; i++) {
            maxPocetProKazdeho[i]--;
        }
        for (int i = 0; i < kere.length; i++) {
            kere[i] = Integer.parseInt(kereTxT[i]);
        }
        int maxPocetSklizni = 0;
        for (int i = pocetKeru - 1; i >= 0; i--) {
            int maxThis = checkUsability(i, kere, maxPocetProKazdeho);
            if (maxThis > maxPocetSklizni) {
                maxPocetSklizni = maxThis;
            }
        }

        System.out.println(maxPocetSklizni);
    }

    private static int checkUsability(int givenIndex, int[] array, int[] maxPocty) {
        int maxNeeded = 0;
        int lastKer = 0;
        if (maxPocty[givenIndex] >= 0) {
            return maxPocty[givenIndex];
        }
        if (givenIndex == 1 && array[1] == array[0])
            return 0;
        for (int i = givenIndex; i >= 0; i--) {
            if (array[i] >= array[givenIndex]) {
                if (i == 0)
                    maxNeeded = 0;
                else if (lastKer > array[i]) {
                    maxNeeded += (1 - checkUsability(i + 1, array, maxPocty));
                } else
                    maxNeeded++;
            } else {
                break;
            }
            lastKer = array[i];
        }
        maxPocty[givenIndex] = maxNeeded;
        return maxNeeded;
    }
}

Stupnice pálivosti

Načíst ze vstupu první řádku a dle její délky určit počet teploměrů. Vytvořit si pole celých čísel o příslušné velikosti.
Načítat jednotlivé řádky a inkrementovat hodnoty v poli na těch indexech, kde se nachází symbol rtuti teploměru, inkrementovat hodnotu.
Načtením všech řádek si určit maximální hodnotu.
Pole čísel seřadit libovolným řadícím algoritmem sestupně.
Vykreslit seřazené pole jako teploměry pálivosti po řádkách. Pro určení, zda pro příslušný teploměr v dané řádce vykreslovat znak rtuti, použít maximální hodnotu.

Příklad zdrojového kódu:


#include <stdio.h>
#include <stdlib.h>

int main(int argc, char *argv[])
{
	int length = 0;
	int working = 1;
	while (working)
	{
		int tlength = 0;
		int hot = 0;
		char c;
		while ((c = getchar()) != EOF && working)
		{
			if (c == '\n')
			{
				break;
			} 
			else
			{
				switch (c)
				{
					case 'o':
						working = 0;
						break;
					case ' ':
					case '.':
						tlength++;
						break;
					case '|':
						tlength++;
						hot++;
						break;
				}
			}
		}
		
		if (!working)
		{
			break;
		}
		
		length = tlength;
		
		for (int i = 0; i < length; i++)
		{
			if ((i + 1) % 2 == 0)
			{
				printf(" ");
			}
			else if (hot > 0)
			{
				hot--;
				printf("|");
			} else
			{
				printf(".");
			}
		}
		printf("\n");
	}
	
	for (int i = 0; i < length; i++)
	{
		if ((i + 1) % 2 == 0)
		{
			printf(" ");
		}
		else
		{
			printf("o");
		}
	}
	printf("\n");
	
	return 0;
}

Výběrové zemědělství

Pro každý testovací případ načíst ze vstupu řetězce udávající původní (A) a požadovanou (B) podobu záhonu.
Použijeme 2D dynamické programování. Postupovat přes prefixy A a B od triviální velikosti po plný řetězec.
Výpočet realizovat přes pomocnou tabulku M: M[i][j] = true, pokud je řetězec B[0...(i-1)] transformovatelný z řetězce A[0...(j-1)], jinak false.
Vyplnění tabulky začít nastavením M[i][j] na false pro celou tabulku. Dále nastavit diagonálu M[i][i] pro i od 0 do délky kratšího řetězce z A a B včetně. Pokud jde předchozí prefix délky i-1 transformovat a znak A[i] je malé nebo velké B[i], nastavit true, jinak false.
Vyplnit tabulku po řádkách vždy od sloupce za diagonálou. M[i][j] nastavit true, pokud je splněna alespoň jedna z podmínek, jinak false:
- Vynechat znak A[i], pokud je malý, pak musí odpovídat prefix s předchozím řetězcem.
- Použít znak A[j], pokud je velký.
- Změnit znak A[j] z malého na velký a použít ho.
Vypsat hodnotu z posledního prvku 2D tabulky M (pro true vypsat „ano“, pro false „ne“).

Příklad zdrojového kódu:


import java.util.*;

public class VyberoveZemedelstvi {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int count = in.nextInt();
        loop:
        for (int i = 0; i < count; i++) {
            char[] possible = in.next().toCharArray();
            char[] wanted = in.next().toCharArray();
            Set<Integer> curr = new HashSet<>(1);
            curr.add(-1);
            for (char c : possible) {
                boolean isOptional = Character.isLowerCase(c);
                Set<Integer> newSet = new HashSet<>(isOptional ? curr.size() * 2 : curr.size());
                for (int num : curr) {
                    if (isOptional) {
                        if (wanted.length >= num + 2 && Character.toUpperCase(c) == wanted[num + 1]) newSet.add(num + 1);
                        newSet.add(num);
                    } else {
                        if (wanted.length >= num + 2 && c == wanted[num + 1]) newSet.add(num + 1);
                    }
                }
                if (newSet.isEmpty()) {
                    System.out.println("NE");
                    continue loop;
                }
                curr = newSet;
            }
            System.out.println(curr.stream().max(Integer::compareTo).get() + 1 == wanted.length ? "ANO" : "NE");
        }
    }
}

Výroba omáček

Načíst ze vstupu požadovaný počet lahviček a časy výroby jednotlivých míst.
Určovat celkovou produkci pro konkrétní časy mocninné řady 2^kpočínaje. Zjistit tak výrobu v čase 1, 2, 4, 8, 16, 32 atd.
Celkovou výrobu v daném čase určit celočíselným dělením daného času časem výroby jednotlivých míst pro každé výrobní místo a výsledky sečíst.
Určování výroby pro rostoucí čas ukončit, jakmile výroba přesáhne požadovaný počet lahviček.
Pomocí binárního vyhledávání najít nejmenší čas nutný k výrobě požadovaného počtu lahviček. Jako počáteční hranice vyhledávání použít předposlední (menší než požadovaný počet) a poslední (větší než požadovaný počet) spočtenou produkci.
Produkci v konkrétním čase potřebnou pro binární vyhledání počítat stejným způsobem jako výše pro čas rostoucí mocninnou řadou.
Vypsat čas nalezený binárním vyhledáváním.

Příklad zdrojového kódu:


#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

bool check(const vector<long long> &pi, long long l, long long cas)
{
    long long x{};
    for (long long i{}; i < pi.size(); ++i)
    {
        x += cas / pi[i];
    }

    return x >= l;
}

int main()
{
    long long v, l, c = 0;

    cin >> v >> l;
    vector<long long> pi(v);

    for (int i{}; i < v; ++i)
    {
        cin >> pi[i];
    }

    long long min = 1;
    long long max = *max_element(pi.begin(), pi.end()) * l;

    while (min < max)
    {
        long long mid = min + (max - min) / 2;

        if (check(pi, l, mid))
        {
            max = mid;
        }
        else
        {
            min = mid + 1;
        }
    }

    cout << min << endl;

    return 0;
}

Zalévání papriček

Načíst ze vstupu počet keříků a naměřených vzdáleností.
Všechny naměřené vzdálenosti načíst a vytvořit z nich graf, kde keříky odpovídají vrcholům a naměřené vzdálenosti hranám.
Pro reprezentaci grafu lze využít např. matici sousednosti (počet vrcholů je dostatečně malý).
Algoritmem pro hledání minimální kostry grafu určit délku minimální kostry.
Vypsat nalezenou délku minimální kostry grafu.

Příklad zdrojového kódu:


program U2425;
const
  MAX_N=1000;
  MAX_M=2000;
type
  tV=record
    s, e, d: LongInt;
  end;
var
  keriky: array[0..MAX_N-1] of LongInt;
  vzdalenosti: array[0..MAX_M-1] of tV;
  count, vCount, link, min, i, j: LongInt;
  temp: tV;

function NajdiKoren(uzel: LongInt): LongInt;
begin
  if keriky[uzel]=uzel then
    NajdiKoren:=uzel
  else
    NajdiKoren:=NajdiKoren(keriky[uzel]);
end;

procedure SpojKoren(uzel1, uzel2: LongInt);
begin
  keriky[NajdiKoren(uzel1)]:=NajdiKoren(uzel2);
end;

begin
  ReadLn(count);
  ReadLn(vCount);
  for i:=0 to vCount-1 do begin
    Read(vzdalenosti[i].s);
    Read(vzdalenosti[i].e);
    ReadLn(vzdalenosti[i].d);
  end;
  for i:=0 to count-1 do keriky[i]:=i;
  for i:=0 to vCount-2 do begin
    for j:=i+1 to vCount-1 do begin
      if (vzdalenosti[i].d-vzdalenosti[j].d)>0 then begin
        temp:=vzdalenosti[i];
        vzdalenosti[i]:=vzdalenosti[j];
        vzdalenosti[j]:=temp;
      end;
    end;
  end;
  min:=0;
  link:=0;
  for i:=0 to vCount-1 do begin
    if link=count-1 then break;
    if NajdiKoren(vzdalenosti[i].s)<>NajdiKoren(vzdalenosti[i].e) then
    begin
      min:=min+vzdalenosti[i].d;
      SpojKoren(vzdalenosti[i].s, vzdalenosti[i].e);
      Inc(link);
    end;
  end;


  WriteLn(min);
  ReadLn;
end.

Zeď proti škůdcům

Načíst ze vstupu maximální index, počet příkazů a pak načítat jednotlivé příkazy.
Použít zametací algoritmus, kdy se „zametá“ podél zdi a udržuje se aktuální výška zdi.
Z každého příkazu na vstupu vytvořit dvě události změny výšky (zvýšení zdi na počátečním indexu a snížení na koncovém).
Události seřadit podle jejich indexu vzestupně. V případě shody indexů upřednostnit událost zvýšení zdi před snížením zdi.
Projít události v tomto pořadí a přičítat změny výšky do pomocné proměnné, ve které vyjde maximum
Vypsat nalezené maximum.

Příklad zdrojového kódu:


#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n, p;
    cin >> n >> p;
    vector<long long> vysky(n + 2, 0);

    for (int i = 0; i < p; ++i) {
        int z, k, v;
        cin >> z >> k >> v;
        vysky[z] += v;
        vysky[k + 1] -= v;
    }

    long long nejvyssi=0, vyska = 0;
    for (int i = 1; i <= n; ++i) {
        vyska += vysky[i];
        nejvyssi = max(nejvyssi, vyska);
    }

    cout << nejvyssi;
    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ů.

K nahlédnutí je rovněž prezentace s popisem řešení předvedená po skončení finále.

Kivule berou

Načíst si pozice jednotlivých kulových karet a uložit si ho např. do pole boolean reprezentující zamíchaný balíček karet. Hodnoty karet nejsou důležité, jde pouze o to, zda to jsou nebo nejsou kule.
Připravit si datovou strukturu umožňující přidávat i odebírat prvky ze začátku i z konce (modifikovaná fronta implementovaná např. obousměrným spojovým seznamem). Tuto strukturu použít k reprezentaci balíčků karet obou hráčů a karet na stole.
Simulovat průběh hry - rozdat karty oběma hráčům, přesouvání karet mezi kartami na stole a kartami hráčů. Je potřeba dbát na směr dle rubu a líce karet a podle toho volit správné odebírání a přidávání do datových struktur.
Hru ukončit v okamžiku, kdy jeden z hráčů nemá v datové struktuře žádné karty.
Vypsat číslo vítězného hráče.

Příklad zdrojového kódu:


#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <unordered_set>

using namespace std; 

int main()
{
    unordered_set<int> s;
    for (int i = 0; i < 8; i++) {
        int x; cin >> x;
        s.insert(x);
    }
    queue<int> prvni, druhy; vector<int> stul;
    for (int i = 32; i>0; i--) {
        if (i % 2 == 1) druhy.push(i);
        else prvni.push(i);
    }

    while (prvni.size()<32 && druhy.size()<32) {
        if (!druhy.empty() && druhy.size()<32) {
            stul.push_back(druhy.front());
            if (s.find(druhy.front()) != s.end()) {
                for (int i = 0; i < stul.size(); i++) {
                    prvni.push(stul[i]);
                }
                stul.clear();
            }
            druhy.pop();
        }
        if (!prvni.empty() && prvni.size()<32) {
            stul.push_back(prvni.front());
            if (s.find(prvni.front()) != s.end()) {
                for (int i = 0; i < stul.size(); i++) {
                    druhy.push(stul[i]);
                }
                stul.clear();
            }
            prvni.pop();
        }
    }
    if (prvni.size() == 32) cout << 2 << endl;
    else cout << 1 << endl;
}

Líný cyklista

Načíst si první řádku uniformní mřížky a podle počtu čísel na ní určit velikost mřížky (tj. šířku i výšku).
Načíst zbývající řády a uložit si výšky v jednotlivých bodech mřížky např. do 2D pole.
Načíst pozici domova, pozici univerzity a vzdálenost sousedních bodů mřížky.
Z načtených bodů uniformní mřížky vytvořit graf, kdy body tvoří vrcholy a horizontální a vertikální spojnice bodů tvoří hrany.
Spočítat ohodnocení jednotlivých hran jako čas potřebný k projetí po hraně pomocí vzorce uvedeného v zadání.
Použít algoritmus pro hledání nejkratší cesty v ohodnoceném grafu (např. Dijkstrův algorimus) a najít délku (tj. dobu trvání) nejkratší cesty.
Nalezenou délku převést na sekundy (pokud nebylo učiněno již dříve) a vypsat.

Příklad zdrojového kódu:


#include <iostream>
#include <cmath>
#include <algorithm>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
using namespace std;

struct pohyb
{
	float cas;
	pair<int, int> poz;
};

struct compare
{
	bool operator()(pohyb a, pohyb b)
	{
		return a.cas > b.cas;
	}
};


void B()
{
	string st;
	getline(cin, st);
	stringstream s(st);
	
	vector<int> tempv;
	string temp;
	while (s >> temp)
	{
		tempv.push_back(stoi(temp));
	}

	int n = tempv.size();
	vector<vector<int>> mapa (n, vector<int>(n));
	for (int i = 0; i < tempv.size(); i++)
		mapa[i][0] = tempv[i];

	
	for (int i = 1; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			cin >> mapa[j][i];
		}
	}

	pair<int, int> start;
	pair<int, int> cil;

	cin >> start.first >> start.second >> cil.first >> cil.second;
	float d;
	cin >> d;


	priority_queue <pohyb, vector<pohyb>, compare> halda;
	pohyb novy;
	novy.cas = 0;
	novy.poz = start;
	halda.push(novy);

	vector<pair<int, int>> pohyby = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };
	vector<vector<float>> casy(n, vector<float>(n, -1));
	casy[start.first][start.second] = 0;

	//for (int i = 0; i < n; i++)
	//{
	//	for (int j = 0; j < n; j++)
	//	{
	//		cout << mapa[j][i] << " ";
	//	}
	//	cout << endl;
	//}

	while (!halda.empty())
	{
		pohyb poz = halda.top();
		halda.pop();

		if ((casy[poz.poz.first][poz.poz.second] != -1) && (casy[poz.poz.first][poz.poz.second] != 0))
			continue;

		//cout << poz.poz.first << " " << poz.poz.second << " dsfdsfsd" << endl;
		casy[poz.poz.first][poz.poz.second] = poz.cas;

		if ((poz.poz.first == cil.first) && (poz.poz.second == cil.second))
		{
			break;
		}

		for (int i = 0; i < 4; i++)
		{
			if ((poz.poz.first + pohyby[i].first >= 0) && (poz.poz.first + pohyby[i].first < n) && (poz.poz.second + pohyby[i].second >= 0) && (poz.poz.second + pohyby[i].second < n))
			{
				pohyb pridej;
				pridej.poz.first = poz.poz.first + pohyby[i].first;
				pridej.poz.second = poz.poz.second + pohyby[i].second;

				if (casy[pridej.poz.first][pridej.poz.second] != -1)
					continue;

				float vert = (float)(mapa[pridej.poz.first][pridej.poz.second] - mapa[poz.poz.first][poz.poz.second]) / (float)1000;
				float uhel = atan(vert / d) * 180 / 3.1415926535;
				float vzd = sqrt(d * d + vert * vert);
				float rychlost = max((float)30 - (float)uhel, (float)4);
				pridej.cas = poz.cas + ((float)vzd / (float)rychlost);

				//cout << pridej.poz.first << " " << pridej.poz.second << endl;
				//cout << vert << endl;
				//cout << uhel << endl;
				//cout << vzd << endl;
				//cout << rychlost << endl;
				//cout << pridej.cas << endl;
				//cout << endl;


				halda.push(pridej);
			}
		}
	}

	//for (int i = 0; i < n; i++)
	//{
	//	for (int j = 0; j < n; j++)
	//	{
	//		cout << casy[j][i] << "   ";
	//	}
	//	cout << endl;
	//}

	cout << round(casy[cil.first][cil.second] * 3600) ;
}

int main()
{
	B();

	return 0;
}

Okresní silnice

Načíst si preferované rychlosti jednotlivých vozidel.
Pro načtená vozidla provést simulaci pohybu vozidel po malých časových krocích.
Vozidla udržovat ve dvou seznamech - auta na silnici v jejich pořadí a odstavená auta.
Dokud není první auto v cíli pro každé auto na silnici provést v každém kroku:
- Posunout vozidlo na novou pozici.
- Akumulovat čas v koloně.
- Akumulovat čas porušování předpisů.
- Upravit příznak lze-předjet.
- Zkontrolovat vypršení časových limitů případně odstavení auta (přesun ze silnice do odstavených případně obráceně).
Seřadit aut - pokud jsou na stejné pozici, pokud může předjet a podle rychlosti, jinak podle pozice

Příklad zdrojového kódu:

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

Poštovní pevnost

Načíst si počet emailů.
Následně načítat příslušný počet řádek jako text.
Pokud načtená řádka nezačíná na hvězdičku, inkrementovat čítač úspěšně doručených emailů.
Výsledek vypočítat jako podíl počtu úspěšně doručených emailů a celkového počtu emailů v procentech. Pozor na celočíselné dělení, je třeba provést reálné dělení dvou celých čísel.
Výsledek vypsat na dvě desetinná místa v požadovaném formátu.

Příklad zdrojového kódu:


program U2434;
  uses
    sysutils, math;
  var
    count, i, a, b: LongInt;
    s: String;
begin
  ReadLn(count);
  a:=0;
  for i:=0 to count-1 do begin
    ReadLn(s);
    if s[1]='*' then Inc(a);
  end;
  b:=count-a;
  WriteLn('Uspesnost: ', FloatToStrF(SimpleRoundTo((b/count)*100, -2), ffFixed, 0, 2));
  ReadLn;
end.

Schodiště

Načíst si maximální vzdálenost, počet bodů a souřadnice jednotlivých bodů a seřadit si body podle souřadnice x od nejnižšího bodu k nejvyššímu.
Rozdělit si chůzi robota na dvě části - cestu po schodišti vzhůru a cestu po schodišti dolů. Řešit pomocí dynamického programování.
Body zpracovávat v pořadí jeden za druhým.
Uvažovat tři parametry:
1. i - hraniční bod východní cesty i .. n - 1,
2. j - hraniční bod západní cesty n - 1 .. j,
3. k - další bod v pořadí zpracování bodů.
Parametr k lze určit z parametrů i a j jako max(i, j) + 1.
Mezivýsledky pro i a j ukládat do tabulky DélkaTrasy[i, j] následovně:
- pro k = n - 1: DélkaTrasy[i, j] = vzdálenostBodů(i, k) + vzdálenostBodů(k, j),
- jinak: DélkaTrasy[i, j] = min(DélkaTrasy[k, j] + vzdálenostBodů(i, k), DélkaTrasy[i, k] + vzdálenostBodů(k, j)).
Po vyplnění tabulky bude řešení úlohy v DélkaTrasy[0, 0].

Příklad zdrojového kódu:

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

PilsProg 2024

Výsledky Lite

Výsledky kvalifikace

Výsledky finále

Ilustrační úlohy

Lite1 úlohy

Lite2 úlohy

Lite3 úlohy

Kvalifikační úlohy

Finálové úlohy

A jaké bylo finále?

Harmonogram PilsProg 2024

Lite úlohy - řešení

Malá násobilka

Příklad zdrojového kódu:

Meziměna

Příklad zdrojového kódu:

Řazení hvězdiček

Příklad zdrojového kódu:

Délka filmu

Příklad zdrojového kódu:

Histogram

Příklad zdrojového kódu:

Zrcadlová matice

Příklad zdrojového kódu:

Filtr hodnot

Příklad zdrojového kódu:

Index minima

Příklad zdrojového kódu:

Symetrická matice

Příklad zdrojového kódu:

Kvalifikační úlohy - řešení

Pálivá sklizeň

Příklad zdrojového kódu:

Stupnice pálivosti

Příklad zdrojového kódu:

Výběrové zemědělství

Příklad zdrojového kódu:

Výroba omáček

Příklad zdrojového kódu:

Zalévání papriček

Příklad zdrojového kódu:

Zeď proti škůdcům

Příklad zdrojového kódu:

Finálové úlohy - řešení

Kivule berou

Příklad zdrojového kódu:

Líný cyklista

Příklad zdrojového kódu:

Okresní silnice

Příklad zdrojového kódu:

Poštovní pevnost

Příklad zdrojového kódu:

Schodiště

Příklad zdrojového kódu:

Přihlášení