Здравствуйте, Nelud, Вы писали:

N>Есть у нас много-много чисел и надо среди них наити сумму нескольких чисел такую, что бы она делилась на данное нам число N. Проблема в том что стоит ограничение времени и перебор не поможет, нужно что то другое придумать.

Конечно, ее можно решать и полным перебором (это я в защиту умного человека), но, как правильно было отмечено — времени может не хватить.

Будем искать множество индексов чисел в исходной последовательности. Рассмотрим n чисел a_1, a_1+a_2, ..., a_1+...+a_n, и остатки от деления их на n: r_1, r_2, ..., r_n. Если найдется число i, такое что r_i=0, то множество{1,2,...,i} — искомое. Если нет, то найдутся i, j: r_i=r_j, (по принципу Дирихле!) т.к. остатки r_1, r_2, ..., r_n не принимают более n-1 различных значений. Тогда множество {i+1,...,j} — ответ.

Из приведенных математических выкладок ( ) следует, что искомое множество индексов существует всегда, и существует хотя бы одно множество, элементы которого идут подряд. А вот если бы нам нужно было отыскать такие числа, сумма которых была бы n (а не делилась на n), то задача из линейной превратилась бы в NPC!

Подчеркивание означает индекс (ну, как в ТеХ-е).

Эта задача была предложена в 95 году на всеукраинской олимпиаде (школьников) по информатике.

http://www.uoi.kiev.ua/digest/uoi/1995/task11.html