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

[Luuzuk]

Можно попробовать "распараллелить" проверку состояния лампочки: вместо массива состояний использовать одну весьма большую переменную "Х" (в худшем случае 10^9 бит), в которой каждый бит будет обозначать состояние каждой конкретной лампочки. Для каждого переключения сгенерировать маску (аналогично: есть инверсия - бит 1, нет инверсии - бит 0), с которой провести побитовое "xor" того самого "Х") После всех операций количество единиц в "Х" будет совпадать с кол-вом горящих лампочек

[BDA]

Luuzuk, не хватит памяти.
Простейшее решение, не проходящее 6 тест по времени:

type
  tarray = array[1..100] of byte;

var
  n, i, count: longint;
  k: byte;
  p: tarray;

begin
  assign(input, 'input.txt'); reset(input);
  assign(output, 'output.txt'); rewrite(output);
  readln(n, k);
  for i := 1 to k do
    read(p[i]);
  count := 0;
  for i := 1 to n do
  begin
    tmp := 0;
    for j := 1 to k do
      tmp := tmp xor ord(i mod p[j] = 0);
    count := count + tmp;
  end;   
  writeln(count);
end.

Оптимизация, позволяющая еле-еле пройти 6 тест и "завалиться" на 7:

type
  tarray = array[1..100] of byte;

var
  n, i, j, count: longint;
  k, tmp: byte;
  p: tarray;
  s: set of byte;

begin
  assign(input, 'input.txt'); reset(input);
  assign(output, 'output.txt'); rewrite(output);
  readln(n, k);
  for i := 1 to k do
  begin
    read(tmp);
    if not (tmp in s) then
      s := s + [tmp]
    else
      s := s - [tmp];
  end;
  tmp := 0;
  for i := 1 to 50 do
    if i in s then
    begin
      inc(tmp);
      p[tmp] := i;
    end;
  k := tmp;
  if k = 0 then
  begin
    writeln(0);
    exit;
  end;
  count := 0;
  for i := 1 to n do
  begin
    tmp := 0;
    for j := 1 to k do
      tmp := tmp xor ord(i mod p[j] = 0);
    count := count + tmp;
  end;   
  writeln(count);
end.

[Abstraction]

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

Можно попробовать "распараллелить" проверку состояния лампочки: вместо массива состояний использовать одну весьма большую переменную "Х" (в худшем случае 10^9 бит), в которой каждый бит будет обозначать состояние каждой конкретной лампочки. Для каждого переключения сгенерировать маску (аналогично: есть инверсия - бит 1, нет инверсии - бит 0), с которой провести побитовое "xor" того самого "Х") После всех операций количество единиц в "Х" будет совпадать с кол-вом горящих лампочек

И? Ассимптотика по времени всё одно O(N*P). Хотя, может быть, получится чуть быстрее.

[Ghost3]

Вот попробовал кое-что...

var n,k,i,j,x,y:int64;
b:array[1..100]of integer;
a:array[1..1000000000] of string;
begin

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

read(n,k);
y:=0;
for j:=1 to k do
 begin
 read(x);
 b[j]:=x;
 end;

for j:=1 to k do
begin
x:=b[j];
for i:=x to n do
 begin
  if a[i]='0' then
  begin a[i]:='1'; y:=y+1; end
  else begin a[i]:='0'; y:=y-1; end;
  x:=x+b[j];
 end;
end;

writeln(y);
end.

Ошибка времени выполнения: System.OutOfMemoryException: Выдано исключение типа "System.OutOfMemoryException".
Стек:
   в Program9.aaa..ctor()
   в Program9.Program.Main()

Ууу, пока писал уже вон сколько новых постов =)

Ну уберем один нолик из

a:array[1..1000000000] of string;

Ошибка исчезает. Однако и тут проблема со счетом xD

[Ghost3]

Хах, кое-что получилось, но не прошла компиляцию:

Строчки 11 и 17, где "for"

For loop control variable must have ordinal type

var n,k,i,j,x,y:int64;
b:array[1..100]of integer;
a:array[1..100000000] of int64;
begin

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

read(n,k);
y:=0;
for j:=1 to k do
 begin
 read(x);
 b[j]:=x;
 end;

for j:=1 to k do
begin
i:=b[j];
while i<=n do
 begin
  if a[i]=0 then
  begin a[i]:=1; y:=y+1; end
  else begin a[i]:=0; y:=y-1; end;
  i:=i+b[j];
 end;
end;

writeln(y);
end.

Хотя бы те 2 примера на странице задачки проходит программа.

[BDA]

array[1..100000000] of int64;
100000000 * 64 бита = 100000000 * 8 байт = 762 мегабайта - удачи

[Ghost3]

Ахахах =)

Что-то я тупить начал =)
Реально непростая задача. Надо опыта набраться побольше.

[Ghost3]

Думаю, стоит подумать над таким решением (но оно в Си), и попытаться переделать его под паскаль если это возможно.
Ps: сам по немногу изучаю C++ по учебнику Шилдта, он удобнее чем паскаль, и "плюшек" у него больше.

#include <stdio.h>
#include <stdlib.h>
#define SIZE 172
#define INVSIZE 10

void colorP (int *arr, int size, int step)
{
int i = -1;
while (i + step < size)
{
i += step;
arr[i] = ~arr[i];
}
}

void setInversion (int *arr, int *inv, int size, int invSize)
{
int i;
for (i = 0; i < invSize; i++)
{
colorP(arr,size,inv[i]);
}
}

int getAmount (int *arr, int size)
{
int i, c = 0;
for (i = 0; i < size; i++)
{
if (arr[i] == -1) c++;
}
return c;
}

int main()
{
int arr[SIZE] = { 0 };
int i;
int inv[INVSIZE] = { 19,2,7,13,40,23,16,1,45,9 };
setInversion(arr, inv, SIZE, INVSIZE);
printf("%d", getAmount(arr,SIZE));
return 0;
}

[BDA]

Да переписать-то его - не проблема (при беглом просмотре не заметил ничего сложного), но, имхо, оно обладает той же сложностью O(K*N).
Приду домой - перепишу на паскаль.
(переписанный код будет в этом посте, если никто раньше не перепишет)

Update Это решение потребует 4*SIZE байт для массива, что не укладывается в ограничение по памяти. Так что, похоже, никакого смысла переписывать нет.

const
  SIZE = 172;
  INVSIZE = 10;

type
  tarray = array[1..size] of integer;
  tinv = array[1..invsize] of integer;

const
  b: tinv = (19, 2, 7, 13, 40, 23, 16, 1, 45, 9 );

var
  a: tarray;
  i: longint;

procedure colorP(var a: tarray; step: integer);
var
  i: longint;
begin
  i := 0;
  while (i + step <= size) do
  begin
    inc(i, step);
    a[i] := not a[i];
  end;
end;

procedure setInversion(var a: tarray; const b: tinv);
var
  i: longint;
begin
  for i := 1 to invsize do
    colorP(a, b[i]);
end;

function getAmount(const a: tarray): longint;
var
  c, i: longint;
begin
  c := 0;
  for i := 1 to size do
    if (a[i] = -1) then inc(c);
  getAmount := c;
end;

begin
  for i := 1 to size do
    a[i] := 0;
  setInversion(a, b);
  writeln(getAmount(a));
end.

Выбросил переменные size и invsize из функций (хотя лучше этого не делать). Данный код решает только пример с сайта (в силу введенных констант). Я думаю, видно, что это решение требует очень много памяти.