Tablice (Część 2)
Materiały
Dla nauczyciela
Dla ucznia
Zadania
Zadanie 1. Pociąg
Jaś pracuje na rampie kolejowej i przeładowuje wagony. Wiedząc, jak ciężkie mogą być wagony, postanowił zakupić specjalny dźwig. Może on podnieść dowolną liczbę wagonów jednocześnie, ważne, żeby stały one obok siebie. Niestety, nawet taki super-sprzęt posiada maksymalny udźwig. Jak duży ciężar musi podnieść dźwig Jasia?
Wejście
W pierwszym wierszu wejścia znajduje się liczba wagonów \(n\) pewnego pociągu \((2 \leq n \leq 10^6)\). W drugiej linii znajduje się \(n\) liczb całkowitych \(w_i\) – ciężar każdego z wagonów (\(1 \leq w_i \leq 10^6\)). W trzeciej linii znajduje się jedna liczba całkowita \(k\) – liczba zestawów wagonów (\(1 \leq k \leq 10^6\)). W kolejnych \(k\) liniach znajdują się informacje o zestawach wagonów, które należy podnieść dźwigiem, odpowiednio numer pierwszego \(w_p\) i ostatniego wagonu \(w_k\) do podniesienia (należy jednocześnie podnieść wszystkie wagony od \(w_p\) do \(w_k\) włącznie).
Wyjście
Twój program powinien w \(k\) liniach ciężar każdego z zestawów wagonów.
Przykład
| Wejście | Wyjście |
|---|---|
| 5 3 5 4 5 4 2 2 3 3 5 |
9 13 |
Wskazówka
Stwórz tablicę z sumami wag wagonów na prefiksach tablicy.
Zadanie 2. Bitib, Bajtjab i Palindrom
Bitib i Bajtjab lubią takie ciągi liczb, które obaj mogą czytać jednocześnie - Bitib od pierwszej do ostatniej, zaś Bajtjab od ostatniej do pierwszej, a mimo to czytają to samo. Czy liczby na kartce, którą właśnie znaleźli, można tak poprzestawiać, aby otrzymać ulubiony przez chłopców sposób ich ustawienia?
Wejście
W pierwszym wierszu wejścia znajduje się jedna liczba naturalna n nie większa niż milion. W następnej linii znajduje się n liczb naturalnych nie większych niż milion.
Wyjście
Jedyny wiersz wyjścia zawiera słowo „TAK” – jeśli z elementów ciągu można zbudować palindrom, lub „NIE” – jeśli nie jest to możliwe.
Przykład
| Wejście | Wyjście |
|---|---|
| 5 15 15 81 18 81 |
TAK |
| 6 15 15 15 15 18 81 |
NIE |
W pierwszym przykładzie, przykładowy możliwy do uzyskania palindrom: \(81 15 18 15 81\)
Wskazówka
Jakie znaczenie ma parzystość liczby wystąpień wartości?
Zadanie 3. Odciski palca
Pan Integer pracuje nad programem do odczytywania odcisków palców. Najwięcej uwagi poświęca modułowi odpowiedzialnemu za sprawdzanie, czy pewien kwadratowy czteroelementowy fragment odnalezionego obrazu (zdjęty z przedmiotu odcisk) może być jakąś częścią dużego obrazu (pełnego wzoru). Zastanawia się przy tym, ile razy fragment pojawił się w jakiejkolwiek formie na dużym obrazie. Pomóż mu to obliczyć!
Wejście
W pierwszej i drugiej linii wejścia znajdują się po dwie dwucyfrowe liczby pierwsze – odnaleziony fragment obrazu. W drugiej linii wejścia znajdują się dwie liczby całkowite \(h\) oraz \(w\) (\(1 \leq h, w \leq 1000\)), odpowiednio wysokość i szerokość dużego obrazu. W kolejnych \(h\) liniach znajduje się po w rozdzielonych spacją dwucyfrowych liczb pierwszych.
Wyjście
Liczba wystąpień dowolnej permutacji fragmentu obrazu we wzorze.
Przykład
| Wejście | Wyjście |
|---|---|
| 11 13 17 19 2 3 23 11 13 29 17 19 |
1 |
| 11 13 17 19 3 4 23 11 13 17 29 17 19 11 11 17 17 13 |
3 |
| 11 13 17 19 1 4 11 13 17 19 |
0 |
Wskazówka
Iloczyn czterech dowolnych liczb pierwszych (niekoniecznie różnych) będzie unikatowy.