Форум Всеукраїнської інтернет-олімпіади NetOI

LeonID написав:

В мене інший алгоритм до задачі Column. Проходячи масив рахую нулики як від'ємні числа, а одинички як додатні. Наприклад 000111001 буде таким -3 3 -2 1. Потім для кожного відємного числа рахую кількість додатніх зліва і відємних справа, для додатніх навпаки. Результатом буде найменша сума. Час лінійний. Код покажу потім.

Код задачі Column. Незважаючи на свій розмір бере свої заслужені 60 балів:

var
b:array[1..33000]of integer;
vlv,dlv,vpr,dpr,sum:array[0..33000]of integer;
a,i,k,n,sumd,sumv,min:longint;
flag1,flag2:boolean;
begin
read(n);
flag1:=true;flag2:=true;k:=0;
for i:=1 to n do begin
    read(a);
    if a=0 then begin
       if flag1 then begin
       k:=k+1;
       flag1:=false;
       flag2:=true;
       end;
    b[k]:=b[k]-1;
    end;
    if a=1 then begin
       if flag2 then begin
       k:=k+1;
       flag2:=false;
       flag1:=true;
       end;
    b[k]:=b[k]+1;
    end;
end;
for i:=2 to k do begin
  if b[i]>0 then
  vlv[i]:=vlv[i-2]+abs(b[i-1]);
  if b[i]<0 then
  dlv[i]:=dlv[i-2]+abs(b[i-1]);
end;
for i:=k-1 downto 1 do begin
  if b[i]>0 then
  vpr[i]:=vpr[i+2]+abs(b[i+1]);
  if b[i]<0 then
  dpr[i]:=dpr[i+2]+abs(b[i+1]);
end;
sumd:=0;sumv:=0;
for i:=1 to k do begin
    if b[i]>0 then sumd:=sumd+b[i];
    if b[i]<0 then sumv:=sumv+abs(b[i]);
end;
for i:=1 to k do begin
    if b[i]<0 then
    sum[i]:=dlv[i]+vpr[i+1];
    if b[i]>0 then
    sum[i]:=vpr[i]+dlv[i-1];
end;
inc(k);
sum[k]:=sumd;
inc(k);
sum[k]:=sumv;
min:=maxlongint;
for i:=1 to k do
    if min>sum[i] then min:=sum[i];
writeln(min);
end.

Эта задача (в смысле математический инвариант)
Це яка? Column?

Відредаговано MItornaDOS (2011-01-26 21:17:29)

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

Почему такая "секретность"? Имеются ли этому какие нибудь логические обьяснения? Ну, там... "времени не хватает"... "технические проблемы"..."опасаемся апелляций"...."ищем наилучшие решения участников"... и т.п.

Просто, интересно. Почему не сейчас? И самое главное: почему не после каждого тура?

(пардон, за надоедливость

LVV написав:

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

Почему такая "секретность"? Имеются ли этому какие нибудь логические обьяснения? Ну, там... "времени не хватает"... "технические проблемы"..."опасаемся апелляций"...."ищем наилучшие решения участников"... и т.п.

Просто, интересно. Почему не сейчас? И самое главное: почему не после каждого тура?

(пардон, за надоедливость

1. Авторские решения и тесты, а так же протоколы проверки  всех работ  ( и сами роботы) участников будут доступны ПОСЛЕ ОКОНЧАНИЯ ОЛИМПИАДЫ. Работает он-лайн проверка на полном наборе тестов - можно доводить свои решения до полного балла.
2.Не после каждого тура - как раз и потому, что участникам нужно заниматься следующим туром, а не искать черную кошку в темной комнате. Подобные материалы до недавнего времени, кроме как на NetOI, вообще не обнародовались, на Всеукраинской это стали делать всего пару лет назад, подозреваю - по нашему примеру.
Аппеляций мы не боимся. Единственное "слабое" место - это несколько отличные условия при он-лайн проверке и официальной - невозможно гарантровать постоянно одинаковый уровень загрузки сервера, что может давать различия в 1-2 теста на задачах с малым тайм-лимитом (он у нас дискретизируется до 0.01, и не особо "щедрые"). Вот потому и существует ОФИЦИАЛЬНАЯ ПРОВЕРКА в однопользовательском режиме.
Она проводится несколько раз для надежности, все протоколы, по каждому тесту сохраняются и вкладываются в итоговый архив.

Хтось колись набирав таку ж кількість балів як Пупкін Василь?

Bk написав:

Хтось колись набирав таку ж кількість балів як Пупкін Василь?

Так. Подивіться минулі олімпіади.
Пупкін - це консолідований автор задач. Якщо в нього не буде повного балу.....:-)

MItornaDOS написав:

"Teма листа: NetOI-2009_4 Registration"
хм... я скопіпастив і так і надіслав
Послати ще раз тільки з "NetOI-2010_4 Registration"?
а то я не зразу замітив опечатку...

так