На форумі обговорюються лише питання, пов'язані з олімпіадою
Ви не зайшли.
Bot17 написав:
ROBOT написав:
1. Временная ложность:
wood: o(n)
dsp: o(m*n*(m+n))
building: o(m*nj*min(m,n))
primenum: o(ln(maxlongint)^3/(ln(a)*ln(b)*ln(c))*ln(ln(maxlongint)^3/(ln(a)*ln(b)*ln(c))))
country: o(n)
2. Тесты: http://www.proveryalka.narod.ru/tests.html
3. Решения: http://www.h0h0l.narod.ru
4. Оценка сложности задач:
COUNTRY - 20
BUILDING - 30
PRIMENUM - 30
WOOD - 50
DSP - 50Сколько у тебя баллов,умник?
166 баллов (37 - 36 - 40 - 40 - 13)
а на онлайне 169 (40 - 36 - 40 - 40 - 13)
Не пойму, почему у меня не работает country
Мой алгоритм как у ivan, наверное опечатка в проге...
моя прога:
var
i,n,c1,c2,c0,c3,ans,a12,a13,a21,a23,a31,a32,min:longint;
m:array[0..60000] of byte;
function solve(var a,b,c:longint):longint;
begin
min:=a;
if min>b then min:=b;
if min>c then min:=c;
dec(a,min);
dec(b,min);
dec(c,min);
solve:=min;
end;
begin
{assign(input,'input.txt');
assign(output,'output.txt');
reset(input);
rewrite(output);}
read(n);
c1:=0;c2:=0;c3:=0;
for i:=1 to n do read(m[i]);
for i:=1 to n do m[i]:=round(6.5*m[i]-1.5*sqr(m[i]))-4;
for i:=1 to n do
case m[i] of
1:inc(c1);
2:inc(c2);
3:inc(c3);
end;
a12:=0;a13:=0;a21:=0;a23:=0;a31:=0;a32:=0;
for i:=1 to n do
begin
if I in [1..c1] then c0:=1;
if I in [c1+1..c1+c2] then c0:=2;
if I in [c1+c2+1..c1+c2+c3] then c0:=3;
case (10*c0+m[i]) of
12:inc(a12);
13:inc(a13);
21:inc(a21);
23:inc(a23);
31:inc(a31);
32:inc(a32);
end;
end;
ans:=solve(a12,a23,a31)+solve(a21,a13,a32);
ans:=ans+((a12+a13+a21+a23+a31+a32) div 2);
write(ans);
{ close(input);
close(output);}
end.Поза форумом
ROBOT написав:
Не пойму, почему у меня не работает country
Ошибка здесь:
...
for i:=1 to n do
begin
if I in [1..c1] then c0:=1;
if I in [c1+1..c1+c2] then c0:=2;
if I in [c1+c2+1..c1+c2+c3] then c0:=3;
...Дело в том, что [x..y] задает множество, и размер у него может быть только 256. Поэтому код
if I in [1..c1] then c0:=1;
выполняется как
if I in [1..c1 mod 256] then c0:=1;
Если эти строки заменить на <=, получаешь 40 баллов. Странно что дельфи не показывает ворнингов насчет этого ![]()
Поза форумом
Rybak написав:
ROBOT написав:
Не пойму, почему у меня не работает country
Ошибка здесь:
Код:
... for i:=1 to n do begin if I in [1..c1] then c0:=1; if I in [c1+1..c1+c2] then c0:=2; if I in [c1+c2+1..c1+c2+c3] then c0:=3; ...Дело в том, что [x..y] задает множество, и размер у него может быть только 256. Поэтому код
Код:
if I in [1..c1] then c0:=1;выполняется как
Код:
if I in [1..c1 mod 256] then c0:=1;Если эти строки заменить на <=, получаешь 40 баллов. Странно что дельфи не показывает ворнингов насчет этого
спасибо, жаль что не знал..
главнное, я ведь проверял на больших числах - RunTimeError не было и я подумал, что всё ОК
Відредаговано ROBOT (2005-12-23 13:37:22)
Поза форумом
Rybak написав:
Странно что дельфи не показывает ворнингов насчет этого
Я писал на Паскале
Поза форумом
вот решение:
{ 12.12.05 - 13.12.05 }
var
a:array[1..3] of longint;
b:array[1..50000] of integer;
c:array[1..3,1..3] of longint;
i,n,j,count,cn1,cn2,cn3,min:longint;
q:boolean;
function prov(i,pos:longint):longint;
var count:longint;
begin
count:=0;
for j:=pos to pos+a[i]-1 do begin
if b[j] <> i then begin inc(c[i,b[j]]); inc(count); end;
end;
prov:=count;
end;
function max3(a,b,c:longint):longint;
begin
if (a>=b)and(a>=c) then max3:=a;
if (b>=c)and(b>=a) then max3:=b;
if (c>=a)and(c>=b) then max3:=c;
end;
begin
read(n);
for i:=1 to n do begin read(b[i]); inc(a[b[i]]); end;
cn1:=prov(1,1);
cn2:=prov(3,a[1]+1);
cn3:=prov(2,a[1]+a[3]+1);
writeln(max3(cn1,cn2,cn3));
end.Туповато конечно( зачем массив с ????? ) но работает
Відредаговано Art[ASoft] (2005-12-23 14:34:42)
Поза форумом
Максим Медведь написав:
Объясните, пожалуйста, как в DSP может быть при тесте
22 16 5 3
ответ
22
???
У меня больше, чем 21 не получается (даже вручную...)
так:
====
||||_ _
||||==
Поза форумом