Задачка. Состоит из двух подзадач. Может быть, уже была.

1. Есть множество из n неотрицательных чисел. Докажите, что всегда можно выбрать непустое подмножество такое, что сумма чисел в нем кратна n.

Вопрос, как к программистам:

2. Постройте линейный алгоритм для нахождения какого-нибудь такого подмножества.

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

DF>Задачка. Состоит из двух подзадач. Может быть, уже была.

DF>1. Есть множество из n неотрицательных чисел. Докажите, что всегда можно выбрать непустое подмножество такое, что сумма чисел в нем кратна n.

Рассмотрим n подмножеств, каждое следующее из которых вложено в предыдущее. Найдется либо такое, что остаток 0, либо два с одинаковым остатком. Вычитаем меньшее подмн-во из большего.

DF>Вопрос, как к программистам:

DF>2. Постройте линейный алгоритм для нахождения какого-нибудь такого подмножества.

Рассматриваем множ-во как последовательность E[i]

S[0] = 0
R[1..n-1] = 0

for(i = 1;...)
   S[i] = S[i-1]+E[i]
   r = S[i] % n;
   if (r=0)
         Ответ: E[1]..E[i]
   if ( R[r] = 0 )
      R[r] = i
   else
      Ответ: E[ R[r]+1 ]..E[i]