На форумі обговорюються лише питання, пов'язані з олімпіадою
Ви не зайшли.
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 не получается (даже вручную...)
так:
====
||||_ _
||||==
Поза форумом