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.
Wszystkie budynki we wschodniej części Bajtogrodu zostały zbudowane zgodnie z zasadami starego bajtobudownictwa: stoją one jeden przy drugim (nie ma między nimi przerw). Razem tworzą bardzo długą ścianę budynków o zróżnicowanej wysokości, ciągnącą się ze wschodu na zachód.
Burmistrz Bajtogrodu, Bajtazar, postanowił że ścianę budynków należy od północnej strony pokryć plakatami. Bajtazar zastanawia się, jaką minimalną liczbą plakatów można pokryć całą północną ścianę budynków. Plakaty mogą mieć kształt prostokątów o bokach pionowych i poziomych. Plakaty nie mogą zachodzić na siebie, natomiast mogą stykać się brzegami. Każdy plakat musi w całości przylegać do ścian pewnych budynków i cała powierzchnia północnych ścian budynków musi być pokryta plakatami.
Napisz program, który:
Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą (), oznaczającą liczbę budynków stojących w rzędzie. Kolejne wierszy zawiera po dwie liczby całkowite i (), oddzielone pojedynczym odstępem i oznaczające długość i wysokość -tego budynku w rzędzie.
Pierwszy i jedyny wiersz wyjścia powinien zawierać jedną liczbę całkowitą, minimalną liczbę prostokątnych plakatów, którymi można całkowicie pokryć północne ściany budynków.
Dla danych wejściowych:
5 1 2 1 3 2 2 2 5 1 4
poprawną odpowiedzią jest:
4
Na rysunkach została przedstawiona sama północna ściana rzędu budynków. Drugi z rysunków przedstawia przykładowe pokrycie ściany czterema plakatami.
Autor zadania: Jakub Radoszewski.