\documentclass{article}
\usepackage[slovak]{babel}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[cm]{fullpage}
\usepackage{hyperref}

\begin{document}
\title{Domáca úloha č. 2}
\author{1-AIN-105, Zima 2019}
\date{Termín: 5.11.2017, 8:10, na cvičení}
\maketitle
\def\question#1#2{\item[\bf #1.] [{\it #2 bodov}\/]}

Skôr ako sa pustíte do riešenia domácej úlohy, oboznámte sa so
všeobecnými pokynmi, ktoré sú priložené na konci tohto dokumentu.
Riešenia, ktoré odovzdáte, musia byť vaše vlastné. Neopisujte
a nesnažte sa nájsť riešenia v literatúre alebo na internete!

\begin{itemize}

\question{1}{20} Zistite, či pre uvedený problém je daný
greedy algoritmus správny. Dokážte správnosť algoritmu alebo uveďte
kontrapríklad.
\begin{enumerate}
\item[a)] {\bf Podivná hra.} Na stole je v rade vyložených $2n$
  kartičiek s číslami. Hru hrajú dvaja hráči, pričom každý z nich si
  môže v každom ťahu zobrať jednu z dvoch krajných kartičiek.
  Vyhráva ten, kto má na konci väčší súčet čísel na svojich kartičkách.
  Cieľom
  prvého hráča je vyhrať, nech druhý hráč hrá akokoľvek.

  {\bf Algoritmus pre prvého hráča.} Vždy keď je na ťahu, zoberie
  z dvoch krajných kartičiek tú s väčším číslom.

\item[b)] {\bf Plátanie hadíc.} Na nemenovanej fakulte požiarna
  inšpekcia našla deravú požiarnu hadicu. Keďže peňazí je málo, údržba
  sa rozhodla hadicu zaplátať. Hadica má $k$ malých dier vo
  vzdialenostiach $d_1<d_2<\dots<d_k$ centimetrov od začiatku.
  Máme k dispozícii záplaty, ktoré pokryjú 5 cm dĺžky. Cieľom
  je zalepiť všetky diery s použitím najmenšieho možného počtu záplat.

  {\bf Algoritmus.} Položíme ľavý koniec záplaty na najľavejšiu
  dieru. Zmažeme zo zoznamu všetky diery pokryté záplatou a opakujeme, až
  kým neostanú žiadne diery.
\end{enumerate}

\question{2}{20} {\bf Nádherné ticho hôr.} V obchoďáku stojí rad, dlhý,
pomalý. Konkrétne, v rade na pokladňu stojí $n$ zákazníkov s rôzne
zaplnenými košíkmi. Nablokovanie košíka zákazníka číslo $i$ trvá čas
$t_i$. Zákazník bude naštvaný, ak v rade bude čakať dlhšie ako trvá
nablokovanie jeho košíka (do čakania samotné blokovanie nerátame, rátame
iba blokovanie všetkých zákazníkov vybavených pred ním).
Manažér sa preto rozhodol, že niektorých
zákazníkov uprednostní a preusporiada rad pri
pokladni. Pomôžte manažérovi usporiadať čakajúcich zákazníkov tak, aby
bol naštvaný najmenší možný počet zákazníkov.

Napríklad, uvažujme $n=5$ zákazníkov s časmi $t_1=15$, $t_2=2$,
$t_3=1$, $t_4=5$ a $t_5=3$. Ak ich usporiadame v poradí $(1,2,3,4,5)$,
tak všetci zákazníci okrem zákazníka číslo 1 budú naštvaní. Ak ich
však usporiadame v poradí $(3,2,5,1,4)$, bude naštvaný len jeden
zákazník. (To je aj jedno z možných optimálnych riešení.)

\question{3}{20} {\bf Programátorská úloha} (viď všeobecné pokyny).
Dané sú reťazce S a T.
Zistete koľko krát sa reťazec T vyskytuje ako podpostupnosť (nie nutne súvislá) v S.

{\bf Formát vstupu.}
Na vstupe sú dva riadky.
V prvom riadku sa nechádza reťazec S, v druhom reťazec T.
Oba obsahujú iba veľké písmena anglickej abecedy a majú dĺžku aspoň 2 a najviac 500 znakov.

{\bf Formát výstupu.}  Vypíšte jeden riadok a v ňom jedno celé číslo:
Počet výskytov T v S ako podpostupnosť.
Ak je počet väčší ako 10000, vypíšte:
VIAC AKO 10000

{\bf Príklad.}~

\begin{minipage}[t]{0.45\textwidth}
{\bf vstup:}
\begin{verbatim}
PEPEXSS
PES
\end{verbatim}
\end{minipage}
\begin{minipage}[t]{0.45\textwidth}
{\bf výstup:}
\begin{verbatim}
6
\end{verbatim}
\end{minipage}

\begin{minipage}[t]{0.45\textwidth}
{\bf vstup:}
\begin{verbatim}
AAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAA
\end{verbatim}
\end{minipage}
\begin{minipage}[t]{0.45\textwidth}
{\bf výstup:}
\begin{verbatim}
VIAC AKO 10000
\end{verbatim}
\end{minipage}

\end{itemize}

\newpage
\input vseob.texm
\end{document}