Przejdź do treści

Tablice (Część 1)

Materiały

Dla nauczyciela

Materiał dla nauczyciela

Dla ucznia

Tablice (MAIN2)

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.

Sprawdź kod na Szkopule

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.

Sprawdź kod na Szkopule

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.

Sprawdź kod na Szkopule