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

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

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

13 - 14 май 2006 г.

    Задача C. Най-дълга  подредица

    Дадено е множество със свойството: от всяка негова редица може да се избере сходяща подредица. Как се нарича такова множество? Отговорът на този въпрос няма отношение към задачата, която ще бъде поставена, но има пряко отношение към общата математическа култура на състезателите.
    А сега и задачата: Дадена е редица X от N цели числа. Да се намери най-дългата подредица,  сумата от елементите на която се дели (без остатък) на зададено число K. Казваме, че Z е подредица на  X, ако Z може да бъде получена чрез премахване на някои членове на X. Празното множество е подредица (с дължина 0) и цялата редица също е подредица (с дължина N).

    Вход
    Първият ред на входа съдържа две числа N и K. Следващите редове съдържат точно N цели числа - елементите на редицата. Входът съдържа повече от един пример и завършва с N = 0. Всички числа на входа са цели положителни числа, по-малки от 1000, с изключение на последното число, което е 0.

    Изход
    Всеки ред на изхода съдържа дължината на най-дългата намерена подредица за поредния пример от входа.