НОВ  БЪЛГАРСКИ  УНИВЕРСИТЕТ

Департамент Информатика

XVIIІ РЕПУБЛИКАНСКА СТУДЕНТСКА ОЛИМПИАДА ПО ПРОГРАМИРАНЕ

13 - 14 май 2006 г.

    Задача A. Разрязване на прът

    Метален прът трябва да бъде нарязан на няколко парчета. Цената в лева за извършване на едно отрязване е равна на дължината на рязания прът в метри. В даден момент може да бъде правен само един разрез. Различни стратегии за нарязване водят до различна цена.
    Например да разгледаме прът с дължина 10 метра, който трябва да бъде нарязан във 2-рия, 4-тия и 7-мия метър. Бихме могли да извършим това като направим най-напред разрез в 2-ри метър, после в 4-ти метър и накрая 7-ми метър. Това струва 10 + 8 + 6 = 24 лева. Друг подход може да бъде да отрежем първо в 4-ти метър, после във 2-ри и в 7-ми метър. Сега цената е 10 + 4 + 6 = 20 лева.
    Да се напише програма A, която пресмята минималната цена на нарязване на прът с дадена дължина.

    Вход.
    Входът съдържа данни за няколко пръта. Първият ред за всеки тестов случай съдържа положително число l < 10⁵, което представлява дължината на металния прът, който трябва да бъде нарязан. Вторият ред съдъжа положително число n < 10⁴, задаващо броя на разрезите за този прът. Следващият ред съдържа n положителни числа c_i, (0 < c_i < l), задаващи местата, в които трябва да бъдат направени разрезите. Прочитането на стойност l = 0 означава край на входа.

    Изход.
    Отпечатва се минималната цена на нарязване на съответния прът по зададения формат в примера.