Tablice (Część 1)
Materiały
Dla nauczyciela
Dla ucznia
Zadania
Zadanie 1. Temperatury
Bajtek na lekcji przyrody uczy się określać różne zjawiska pogodowe. Jednym z zadań, które otrzymał, jest codzienne notowanie temperatury. Bajtek rzetelnie zapisywał liczby na karteczce każdego dnia. Teraz przygląda się uzyskanym wynikom i zastanawia, ile razy i w które dni uzyskał określoną temperaturę. Pomożesz mu?
Wejście
W pierwszej linii wejścia znajduje się jedna liczba całkowita \(n\) (\(1 \leq n \leq 10^3\)), oznaczająca liczbę dni pomiarowych. W drugiej linii wejścia znajduje się \(n\) liczb całkowitych - zanotowanych w kolejnych dniach temperatur \(t_i\) (\(-50 \leq t_i \leq 100\)). W trzeciej linii znajduje się jedna liczba \(x\) (\(-50 \leq x \leq 100\)) - szukana temperatura.
Wyjście
Na wyjściu w jednej linii powinna znaleźć się liczba dni \(k\), w które została zmierzona temperatura \(x\), oraz \(k\) liczb oznaczających numery dni, w które zmierzono temperaturę \(x\). Liczby należy podać w kolejności rosnącej i oddzielić pojedynczymi spacjami.
Przykład
| Wejście | Wyjście |
|---|---|
| 5 -2 0 1 -2 3 -2 |
2 1 4 |
Wskazówka
Potrzebne jest dwukrotne przeszukanie tablicy: zliczenie wartości oraz wypisanie indeksów.
Zadanie 2. Najlepsze sumy
Najlepszą sumą ciągu liczb \(a_1, a_2, ..., a_n\) nazywamy największą wartość wśród sum złożonych z sąsiednich elementów tego ciągu. Na przykład dla ciągu: \(1, 2, -5, 7\) mamy następujące sumy:
\(1\)
\(1+2 = 3\)
\(1+2+(-5) = -2\)
\(1+2+(-5)+7 = 5\)
\(2\)
\(2+(-5) = -3\)
\(2+(-5)+7 = 4\)
\(-5\)
\(-5+7 = 2\)
\(7\)
Zatem najlepszą sumą jest \(7\) (zwróć uwagę, że jeden element też uznajemy za sumę). Zaproponuj algorytm wyznaczania najlepszej sumy dla dowolnego ciągu liczb całkowitych. Na jego podstawie napisz program do obliczenia najlepszych sum ciągów liczb.
Wejście
W jednej linii znajduje się ciąg liczb całkowitych zakończony liczbą \(0\). Liczb jest nie więcej niż \(500000\), ich wartość mieści się w przedziale \([-1000, 1000]\).
Wyjście
Największa suma złożona z kolejnych elementów ciągu.
Przykład
| Wejście | Wyjście |
|---|---|
| 1 2 -5 7 0 |
7 |
Wskazówka
Najlepszy wynik zawsze będzie nieujemny.
Zadanie 3. Bankiet
W restauracji Utalentowany Miś zaplanowano bankiet dla finalistów OIG. Goście zasiądą przy okrągłych stołach w ściśle określony sposób. Kierownik sali otrzymał listę gości wraz z informacją, kto ma siedzieć z lewej strony każdego z nich. Ile stołów musi przygotować na bankiet?
Wejście
W pierwszym wierszu zapisano liczbę gości \(N\) (\(1 \leq N \leq 30 000\)). Goście są ponumerowani kolejnymi liczbami naturalnymi od \(1\) do \(N\). W drugim wierszu zapisano numer gościa siedzącego po lewej stronie pierwszego gościa. W trzecim wierszu zapisano numer gościa siedzącego po lewej stronie drugiego gościa itd. W \(i\)-tym wierszu zapisano numer gościa siedzącego po lewej stronie (\(i–1\))-tego gościa. W \(N+1\)-szym wierszu zapisano numer gościa siedzącego po lewej stronie \(N\)-tego gościa.
Wyjście
W pierwszym wierszu wypisz liczbę stolików potrzebnych do usadzenia wszystkich gości.
Przykład
| Wejście | Wyjście |
|---|---|
| 12 4 10 7 3 2 6 1 5 11 8 12 9 |
4 |
Wskazówka
Zasymuluj sadzanie kolejnych dzieci przy stolikach.