Article
Дизайн и Анализ на Алгоритми, 2011
Time Limit: 0.4s, Memory Limit: 64MiB
Като стажант в Българската Академия за Изследване на Генната Архитектура (накратко БАЗИНГА), на Ели се пада честта да популяризира работата на академията. Освен банерите, които трябва да направи (задача Bazinga), тя е решила да пусне рекламно каре в местния вестник. За съжаление рекламите са скъпи, а ресурсите, дадени на Ели от академията, не са особено много.
Във вестника се плаща на заета площ, като на парите, които са ѝ отпуснати за това стигат за A квадратни пиксела (тоест каре с височина H и дължина W пиксела, като W * H ≤ A). За рекламите се ползва monospace font (всички букви са с еднакъв размер и са "квадратни", тоест всяка използва квадратче P на P пиксела). Така между отделни букви в една дума не трябва да се оставя допълнително разстояние, както и между букви на съседни редове. По този начин лесно може да се изчисли, по даден размер на карето, дали даден текст може да се побере там или не.
Ели не може да пренася думи от ред на ред в рекламното каре. Ако две думи са разделени с шпация в текста, то те трябва или да са разделени с шпация и в рекламното каре, или едната да е в края на реда, а следващата да е в началото на следващия ред. Шпацията също отнема квадратче P на P пиксела.
Знаейки максималната заета площ A, на която трябва да се простира рекламата, и текста, който тя трябва да съдържа, сега Ели се чуди какъв е размерът на най-големия фонт (тоест най-голямото P), който може да ползва?
Във вестника се плаща на заета площ, като на парите, които са ѝ отпуснати за това стигат за A квадратни пиксела (тоест каре с височина H и дължина W пиксела, като W * H ≤ A). За рекламите се ползва monospace font (всички букви са с еднакъв размер и са "квадратни", тоест всяка използва квадратче P на P пиксела). Така между отделни букви в една дума не трябва да се оставя допълнително разстояние, както и между букви на съседни редове. По този начин лесно може да се изчисли, по даден размер на карето, дали даден текст може да се побере там или не.
Ели не може да пренася думи от ред на ред в рекламното каре. Ако две думи са разделени с шпация в текста, то те трябва или да са разделени с шпация и в рекламното каре, или едната да е в края на реда, а следващата да е в началото на следващия ред. Шпацията също отнема квадратче P на P пиксела.
Знаейки максималната заета площ A, на която трябва да се простира рекламата, и текста, който тя трябва да съдържа, сега Ели се чуди какъв е размерът на най-големия фонт (тоест най-голямото P), който може да ползва?
Вход
На първия ред на стандартния вход ще бъде зададена максималната площ A, която може да заема рекламното каре. На втория ред ще бъде зададен текста, който то трябва да съдържа. Той ще бъде с дължина по-малка или равна на 20000 символа и ще съдържа само малки и главни латински букви, цифри и шпации. Различните думи ще бъдат разделени с точно един интервал.
Изход
На единствен ред на стандартния изход изведете едно цяло число – максималния размер на фонта P, който може да използва Ели. Ако текстът не може да се изпише дори при фонт 1, вместо това изпечатайте 0.
Ограничения
- 1 ≤ A ≤ 10,000
Примерен Вход | Примерен Изход |
---|---|
751 Design Analysis AlgorithmsY2011 | 5 |
13 This text is way too long. | 0 |
В първия пример оптималният отговор може да бъде получен при височина 10 и широчина 75, като така имаме 2 реда и събираме по 15 символа на ред.