English
Zobacz więcej:
- dla uczniów szkół podstawowych: oij.edu.pl/start/
- dla uczniów szkół średnich: oi.edu.pl/l/jak_zaczac/
Zadanie Klocki reaktywacja (klr)
Klocki reaktywacja
Limit pamięci: 32 MB
Bajtazar bez żadnego problemu opanował sztukę układania 
klocków na prostokątnej planszy. Postanowił stawić czoła większemu wyzwaniu. Zastnanawia się na ile sposobów można 
klocków ułożyć w 
-wymiarową kostkę o boku 
, tak by suma numerów klocków w każdej 
-wymiarowej hiperpłaszczyźnie była liczbą pierwszą. Pokazał tę sztuczkę Bajtolinie, jednak nie wydawała się nią zainteresowana.
Mimo to, Bajtazar nie poddawał się. Dzięki wyjątkowym zdolnościom w układaniu klocków Bajtazar szybko wspinał się po kolejnych szczeblach kariery. Znalazł pracę w Ministerstwie Infrastruktury. Jego zadaniem jest optymalizacja pracy robotników budowlanych. Obecnie zajmuje się naprawą autostrady A1. Rozdział pracy wygląda następująco: autostradę dzieli się na odcinki długości 
kilometrów. Jeśli pierwszy odcinek zaczyna się na 
-tym kilometrze1,
to 
-ty z nich zaczyna się na kilometrze 
. Dla każdego kilometra autostrady wiemy czy wymaga on naprawy. Ekipy robotników należy wysłać na każdy 
-kilometrowy odcinek, w którym trzeba wyremontować co najmniej jeden kilometr. Zadaniem Bajtazara jest znalezienie takiego podziału autostrady na odcinki, by liczba odcinków na które zostaną wysłane załogi budowlane była jak najmniejsza. Pierwszy odcinek podziału musi się zaczynać na jednym z pierwszych 
kilometrów. Dodatkowo wiemy, że żaden spośród 
pierwszych kilometrów autostrady nie wymaga naprawy.
Zadanie
Napisz program, który:
- wczyta ze standardowego wejścia opis uszkodzeń autostrady,
- wyznaczy podziały autostrady na odcinki minimalizujące wymaganą ilość ekip budowlanych,
- wypisze wynik na standardowe wyjście.
Wejście
W pierwszym wierszu znajdują się dwie liczby całkowite 
i 
(
) - długość pojedynczego odcinka oraz ilość uszkodzonych kilometrów.
Druga linia zawiera rosnący ciąg 
liczb całkowitych 
(
) poodzielanych pojedynczymi spacjami. Każda z nich oznacza jeden kilometr autostrady, który wymaga naprawy.
Wyjście
W pierwym wierszu należy wypisać minimalną ilość wysłanych ekip remontowych. Druga linia powinna zawierać wszystkie możliwe kilometry, na których może rozpoczynać się pierwszy odcinek podziału, wypisane w kolejności rosnącej.
Przykład
Dla danych wejściowych:
4 3 7 14 15
poprawną odpowiedzią jest:
2 1 2 4
1.
-ty kilometr autostrady to odcinek zaczynający się 
kilometrów od jej początku i mający długość 1km.
Zapożyczenie z chorwackiej olimpiady informatycznej: Jakub Łącki.