Gözəl Aralıq
Mətn sözlər ardıcıllığından ibarətdir və hər bir söz simvollardan təşkil olunub. Sizin vəzifəniz bu sözləri W sütunlu və kifayət qədər çox sətirli bir şəbəkəyə yerləşdirməkdir. Tərtibatın estetik görünməsi üçün aşağıdakı şərtlərə riayət edilməlidir:
1. Sözlər mətndəki orijinal ardıcıllığını saxlamalıdır. Aşağıdakı şəkillər 4 sözlü "This is a pen" mətninin 11 sütuna düzgün və yanlış tərtibat nümunələrini göstərir.
2. Eyni sətirdə yan-yana olan iki söz arasında ən azı bir boşluq simvolu olmalıdır. Digər şərtləri yerinə yetirmək üçün bəzən bir neçə boşluq qoymaq lazım gələ bilər.
Şəkil 3: YANLIŞ – Sözlər arasında boşluqlar olmalıdır.
3. Hər bir söz, içindəki simvolların sayına bərabər ardıcıl sütunları tutmalıdır. Bir sözü sətirlərə bölmək və ya boşluqlar əlavə etməklə iki və ya daha çox hissəyə ayırmaq olmaz.
Şəkil 4: YANLIŞ – Tək bir sözdəki simvollar ardıcıl olmalıdır.
4. Mətn hər iki tərəfə düzləşdirilməlidir. Yəni, bir sətirin ilk sözü sətirin ilk sütunundan başlamalı və son sətirdən başqa, bir sətirin son sözü son sütunda bitməlidir.
Şəkil 5: YANLIŞ – Sətirlər həm sol, həm də sağ tərəfə düzləşdirilməlidir.
Mətn ən gözəl şəkildə yerləşdirildikdə, artıq uzun boşluqlar olmur. Məsələn, Şəkil 6-dakı tərtibatda ən çox 2 ardıcıl boşluq var ki, bu da Şəkil 1-dəki 3 ardıcıl boşluğa malik tərtibatdan daha gözəldir. Verilən giriş mətninə və sütunların sayına əsasən, sözlər arasında ən uzun ardıcıl boşluqların uzunluğunun minimum olduğu bir tərtibat tapın.
Şəkil 6: Yaxşı və ən gözəl tərtibat.
Giriş verilənləri
Giriş bir neçə datasetdən ibarətdir, hər biri aşağıdakı formatda verilir:
W N
x_1 x_2 ... x_N
W, N və x_i hamısı tam ədədlərdir. W sütunların sayıdır (3 ≤ W ≤ 80000). N sözlərin sayıdır (2 ≤ N ≤ 50000). x_i i-ci sözdəki simvolların sayıdır (1 ≤ x_i ≤ (W-1)/2). Qeyd edək ki, x_i üçün yuxarı hədd həmişə şərtləri yerinə yetirən bir tərtibatın mövcudluğunu təmin edir.
Son dataset iki sıfırdan ibarət bir sətirlə tamamlanır.
Çıxış verilənləri
Hər bir dataset üçün sözlər arasında ən uzun ardıcıl boşluqların mümkün olan ən kiçik sayını çap edin.