|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Andrey Popyk 2:5020/400 25 May 2001 10:36:04
To : Andrey Dashkovsky
Subject : RE: a[i1]+a[i2]+...+a[ik] = N*p
--------------------------------------------------------------------------------
Привет Ihor.
24 Мая ты писал:
IB> Есть такая задача: дано масив N чисел a[1], a[2],..., a[N].
IB> Из него нужно выбрать такое подмножество из k<=N элементов, чтобы
IB> a[i1] + a[i2] + ... + a[ik] делилось на N (если такое подмножество
IB> существует вообще)
IB> Так как N может быть довольно большим (около 10000), то перебор в
IB> лоб (то есть "брать элемент - не брать") дающий сложность О(2^N) есть
IB> недопустимым.
IB> Кто нибудь знает нормальный алгоритм решения этой задачи?
Эта задача (если я не ошибаюсь ;) решается так:
Сформируем массив M[1..N], где M[i]:=( a[1]+a[2]+...+a[i] ) mod N
Теперь возможны два случая
1) В массиве M[p]=0 для некоторого p.
В этом случае ответом есть подмножество a[1], a[2],...,a[p]
2) M[p]<>0 для любого p.
Возможных остатков от деления на N есть ровно N.
А так как в нашем массиве нет нуля (а внем N чисел от 1 до N),
то в нем найдутся по крайней мере 2 одинаковых элемента
M[p] = M[d] и p<d.
Тогда ответом будет последовательность чисел a[p+1], a[p+2],...,a[d].
Вроде все.
Удачи.
--
Отправлено через сервер Talk.Ru - http://www.talk.ru
--- ifmail v.2.15dev5
* Origin: Talk.Ru (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
RE: a[i1]+a[i2]+...+a[ik] = N*p