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.
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)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 .
Napisz program, który:
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.
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 .
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.