Estetyczny tekst
Limit pamięci: 128 MB
Rozważmy dowolny tekst złożony z słów ponumerowanych od do .
Dowolny podział tego tekstu na wierszy reprezentujemy za
pomocą takiego ciągu liczb , że słowa
o numerach od do znajdują się w pierwszym wierszu,
słowa o numerach od do znajdują się w drugim wierszu
itd., a słowa o numerach od do znajdują się
w ostatnim, -tym wierszu.
Każde słowo ma określoną długość (wyrażoną liczbą znaków).
Długość słowa o numerze oznaczamy przez
.
Ponadto każde dwa sąsiednie słowa w wierszu są oddzielone
odstępem szerokości jednego znaku.
Długością wiersza nazywamy sumę długości wszystkich słów w tym wierszu
powiększoną o liczbę odstępów między nimi.
Długość wiersza o numerze oznaczamy przez .
Oznacza to, że jeżeli w wierszu o numerze znajdują się słowa o numerach
od do włącznie, to długość tego wiersza wynosi:
Dla przykładu, rozważmy tekst złożony z słów o długościach
kolejno , , i oraz jego podział na wiersze.
Wówczas długość pierwszego wiersza wynosi , drugiego - ,
a trzeciego - :
XXXX (1. wiersz)
XXX XX (2. wiersz)
XXXXX (3. wiersz)
Współczynnikiem estetyczności podziału danego tekstu na
wierszy nazywamy liczbę wyrażoną wzorem:
W szczególności, jeżeli podział zajmuje tylko jeden wiersz,
jego współczynnik estetyczności jest równy .
Im mniejszy jest współczynnik estetyczności, tym bardziej
estetyczny jest dany podział.
Rozpatrujemy tylko takie podziały, w których długość żadnego wiersza nie
przekracza pewnej stałej liczby .
Spośród wszystkich takich podziałów danego tekstu na dowolną
liczbę wierszy poszukujemy podziału najbardziej estetycznego,
czyli o minimalnym współczynniku estetyczności.
W podanym powyżej przykładzie współczynnik estetyczności podziału
jest równy i jest to minimalna wartość współczynnika estetyczności dla
lub .
Zadanie
Napisz program, który:
-
wczyta ze standardowego wejścia liczby i oraz
długości kolejnych słów,
-
wyznaczy minimalny współczynnik estetyczności dla tych
podziałów, w których długość żadnego wiersza nie przekracza ,
-
wypisze wynik na standardowe wyjście.
Wejście
Pierwszy wiersz standardowego wejścia zawiera liczby całkowite
i , , ,
oddzielone pojedynczym odstępem.
Drugi i ostatni wiersz wejścia zawiera liczb całkowitych będących
długościami kolejnych słów, dla
, pooddzielanych pojedynczymi odstępami.
Wyjście
Pierwszy i jedyny wiersz standardowego wyjścia powinien zawierać
jedną liczbę całkowitą:
minimalny współczynnik estetyczności dla tych podziałów,
w których długość żadnego wiersza nie przekracza .
Przykład
Dla danych wejściowych:
6 4
4 3 2 5
poprawnym wynikiem jest:
3
a dla danych wejściowych:
4 2
1 2
poprawnym wynikiem jest:
0
Autor zadania: Bartosz Walczak.