W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
W Bajtocji ruszyła rekonstrukcja dawnej budowli. Mimo że budowa potrwa jeszcze wiele miesięcy, to bilety, na pierwszą wizytę wykupiło już wielu mieszkańców. Nie wiadomo jeszcze, ile osób będzie w stanie przebywać w budowli w jednym czasie ze względu na ograniczenia wytrzymałościowe. Będzie to pewna liczba pierwszych w kolejności osób, które wykupiły bilety.
Budowla została zbudowana w specyficzny sposób. W pierwszej kolejności ułożono pewną parzystą liczbę słupów. Następnie na kolejne pary słupów położono płytę. Później na każdej płycie stawiano jeden słup. Następnie ponowiono proces układania płyt - na kolejnych dwóch słupach leżących na płytach najwyższego piętra układano płyty z pojedynczym słupem i tak powstawały kolejne piętra. Projekt był tak zaplanowany, aby na każdym piętrze była parzysta liczba słupów, więc zawsze dawało się zbudować kolejne piętra. Każdy słup ma określoną wytrzymałość, czyli maksymalne obciążenie, jakie może utrzymać.
Uroczyste otwarcie odbędzie się na szczycie budowli, na której zgromadzi się pewna liczba mieszkańców Bajtocji. Łącznie stworzą dość duże obciążenie, równe ich łącznej wadze. Wiadomo, że obciążenie rozkłada się zawsze równomiernie na dwa słupy, podtrzymujące płytę, oraz że płyty mogą wytrzymać dowolne obciążenie.
Rekonstruktor postanowił wymienić pewną liczbę słupów. Po każdej wymianie jednego słupa chciałby wiedzieć, ile maksymalnie osób z kolejki będzie mogło wziąć udział w uroczystym otwarciu. Zakładamy, że waga płyt i słupów jest pomijalnie mała.
Pierwszy wiersz standardowego wejścia zawiera trzy liczby całkowite
(
), oznaczające odpowiednio liczbę pięter
budowli, liczbę mieszkańców Bajtocji, którzy wykupili już bilety oraz liczbę słupów
do wymiany.
Kolejne wierszy zawiera opisy poszczególnych pięter od najwyższego do najniższego.
Kolejne wiersze zawierają
liczb całkowitych.
W każdym wierszu znajduje się więc
liczb całkowitych
(
),
gdzie
jest wytrzymałością
-tego w kolejności (od lewej) słupa na
-tym piętrze
(od góry).
W następnym wierszu znajduje się liczb całkowitych
(
),
gdzie
oznacza wagę osoby, która jako
-ta kupiła bilet.
Kolejne wierszy opisuje wymieniane słupy.
Każdy wiersz zawiera trzy liczby całkowite
(
), oznaczające,
że wytrzymałość słupa
(od lewej) na piętrze
(od góry) zostaje zamieniona
na wytrzymałość
.
W testach wartych co najmniej punktów zachodzą dodatkowe warunki
i
.
Standardowe wyjście powinno zawierać wierszy. W kolejnych wierszach powinna znaleźć się
jedna liczba całkowita, równa maksymalnej liczbie osób z kolejki, która może wziąć udział
w uroczystym otwarciu po wymianie
słupów.
Dla danych wejściowych:
2 5 3 3 5 6 1 4 3 1 3 5 3 8 1 1 5 2 2 3 1 1 6
poprawną odpowiedzią jest:
2 2 3 3
Autor zadania: Jacek Tomasiewicz.