15533. Klasyka 1 [AL_09_08]

Zadanie:
https://pl.spoj.com/problems/AL_09_08

Skrócony opis problemu:

Dla danego tekstu $s$ o długości $n$ i wzorca $p$ o długości $m$ ($m \le n$) należy znaleźć ilość wystąpień $p$ w $s$. Zarówno $s$ jak i $p$ składają się z małych liter alfabetu łacińskiego, lecz w $p$ może pojawić się jeden znak '?', który będzie oznaczał dowolny znak.

15510. Gra [AL_09_07]

Zadanie:
https://pl.spoj.com/problems/AL_09_07

Skrócony opis problemu:

Dana jest moneta, na której wypada orzeł z prawdopodobieństwem $\frac{2}{3}$, a reszka z $\frac{1}{3}$. Czy prawdopodobieństwo $P(A)$, że w $n$ rzutach wypadło $k$ reszek jest większe, mniejsze czy równe prawdopodobieństwu $P(B)$ przy dodatkowej wiedzy, że w pierwszym rzucie wypadła reszka?

15509. Wycieczka 2 [AL_09_06]

Zadanie:
https://pl.spoj.com/problems/AL_09_06

Skrócony opis problemu:

Otrzymujesz na wejściu macierz sąsiedztwa $M$ o rozmiarze $n$ oraz macierz $N$, w której w $i$-tym wierszu i $j$-tej kolumnie powinna być ilość dróg z wierzchołka $i$ do wierzchołka $j$ o długości 2 (a więc z dokładnie jednym pośrednikiem; 2 oznacza ilość krawędzi, a nie wierzchołków). Twoim zadaniem jest zweryfikowanie czy faktycznie dla każdej pary wierzchołków $(i;j)$ na wejściu podano prawidłową liczbę $N_{i,j}$ dróg o długości 2 między tymi wierzchołkami. Jeśli w macierzy $N$ wszystkie liczby się zgadzają wypisz TAK. W przeciwnym wypadku wypisz NIE.

Np. dla macierzy sąsiedztwa:

0 1

1 0

Od wierzchołka 1 można przejść do wierzchołka 1 na 1 sposób (przez wierzchołek 2), od 2 do 2 też na 1 (przez wierzchołek 1), ale już od 1 do 2 i od 2 do 1 nie można (więc na 0 sposobów). Macierz $N$ powinna zatem wyglądać tak:

1 0

0 1