Задача "Лампочки" на Pascal (№337 с acmp.ru)

[Ghost3]

Здравствуйте! Вот решил взяться за сложную задачку "Лампочки", и у меня неплохо получилось к моему удивлению
Моя программа, которую я писал минут 20, не проходит тест №6 с ошибкой Runtime error.
Есть кто решал эту задачу? Можете подсказать хотя бы примерно, что в этом 6-ом тесте?

Вот моя программа:

var n,k,i,j,x,y:longint; a,b:array[0..10000] of int64;
begin

assign (input, 'input.txt'); reset(input);
assign (output, 'output.txt'); rewrite(output);

{Присваиваю всем значениям массива 0}
read(n,k);
for i:=0 to n do
 begin
 a[i]:=0;
 end;

{считываю числа 2й строки}
for j:=1 to k do
 begin
 read(x);
 b[j]:=x;
 end;

{тут заменяю b[j]-ый элемент нулем, если он был равен единице и наоборот. b[j] - это числа со 2й строки}
for i:=0 to n-1 do
begin
 for j:=1 to k do
  begin
   if (i=0) then
   begin
   if a[i+b[j]]=1 then a[i+b[j]]:=0 else a[i+b[j]]:=1;
   end
   else
   begin
   if ((i mod b[j])=0) then
    begin
    if a[i+b[j]]=1 then a[i+b[j]]:=0 else a[i+b[j]]:=1;
    end;
   end;
  end;
end;

{здесь считаю кол-во элементов равных 1-му}
y:=0;
for i:=1 to n do
begin
if a[i]=1 then y:=y+1;
end;
writeln(y);
end.

Ps: по-моему не такая уж и супер-сложная задача, надо лишь помозговать над ней побольше.

[Abstraction]

Йолки. Пусть N=10^9. И вот Вы, такой красивый, обращаетесь в первом же цикле к a[10000], a[20000], a[20001]... дальше объяснять?

[Ghost3]

Угу, только как записать-то?

a,b:array[0..10000000000] of int64;

Ошибка: слишком большой диапозон =\

Хотя можно как-нибудь умудрится разбить a на несколько массивов...

[Abstraction]

Правильный ответ: не надо хранить состояния всех лампочек.
Алгоритм O(N) по времени и O(P) по памяти пишется достаточно легко, но что-то мне подсказывает, что он не пройдёт по времени. А вот быстрее чем O(N) - это надо очень сильно думать, задачу простой никак не назовёшь.

[Luuzuk]

Заменить массив списком например) Только тогда есть риск попасть на OutOfAMemory)

Попробуйте подойти к задаче несколько иначе: не писать в массив состояния всех лампочек, а только номера загоревшихся.

Псевдокод:

// у нас есть список номеров лампочек, которые горят ("А"). Он сейчас пуст

1. Считать период инверсии
2. Рассчитать номера инвертируемых лампочек (обозначим как "B")
3. Пройдем циклом по всем номерам из списка "B" ("Bi"):
  3.1. Если в списке "А" есть элемент "Bi", то удаляем его (т.к. погаснет)
  3.2. Если в списке "А" не оказалось "Bi", то добавляем "Bi" в список "А" (т.к. загорится)
4. Идем к п.1, считываем новый номер и так пока номера не кончатся

P.S. путь неоптимальный, приведен просто как пример)

[Ghost3]

Там время 2 секунды, неужели не хватит?

Luuzuk
Спасибо, я такой недогадливый =) Сейчас попробую.

[Luuzuk]

Сообщение от Ghost3

Там время 2 секунды, неужели не хватит?

При N = 10^9 на мой псевдокод времени скорее всего не хватит, как может не хватить и памяти) но выводить формулу тупо лень

[Ghost3]

А по-моему ваш пример куда в разы быстрее моего. И мой пока успешно проходил 5 тестов, и на 6-ом была ошибка связанная не с нехваткой времени =)

Можете подсказать как сделать цикл с шагом в "x"?

[Abstraction]

Сообщение от Luuzuk

Заменить массив списком например) Только тогда есть риск попасть на OutOfAMemory)

Попробуйте подойти к задаче несколько иначе: не писать в массив состояния всех лампочек, а только номера загоревшихся.

Псевдокод:

// у нас есть список номеров лампочек, которые горят ("А"). Он сейчас пуст

1. Считать период инверсии
2. Рассчитать номера инвертируемых лампочек (обозначим как "B")
3. Пройдем циклом по всем номерам из списка "B" ("Bi"):
  3.1. Если в списке "А" есть элемент "Bi", то удаляем его (т.к. погаснет)
  3.2. Если в списке "А" не оказалось "Bi", то добавляем "Bi" в список "А" (т.к. загорится)
4. Идем к п.1, считываем новый номер и так пока номера не кончатся

P.S. путь неоптимальный, приведен просто как пример)

Хинт: можно хранить только переключения (не более 50 элементов), после чего пройти циклом от 1 до N и для каждого значения сообразить, горит лампочка после всех переключений, или нет.

1. Прочитать в массив все инверсии (две инверсии с одним периодом отменяют друг друга) - массив из P элементов, каждый элемент - 0 или 1.
2. Переписать в другой массив (P2) те индексы, для которых элемент в P равен 1.
3. Пройти циклом от 1 до N, для каждого числа пройти по всем элементам P2 и проверить, делится или нет. Если число элементов P2, на которые делится, нечётно - добавить 1 к числу горящих лампочек.

Но, повторюсь, пройти не должно - 10^9 итераций, на каждой не менее 10 операций, даже при 4GHz это ~2.5 секунды.

[Abstraction]

Сообщение от Luuzuk

При N = 10^9 на мой псевдокод времени скорее всего не хватит, как может не хватить и памяти) но выводить формулу тупо лень

Формулу, горит ли n-ная лампочка? В общем случае вычислимой за малое время формулы не существует Нужно как-то организовывать имеющиеся делители в решётки, считать НОК каких-то подмножеств (вероятно, отделяя простые делители большие 7)... В общем, задача местами интересная, действительно.