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


На форумі обговорюються лише питання, пов'язані з олімпіадою

Ви не зайшли.

#26 2005-12-22 13:10:29

ROBOT
Олімпієць
Звідки: Ялта
Зареєстрований: 2005-10-26
Повідомлень: 158

Re: II тур - тесты и решения

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.

I have Delphi 7, BP 7.0, FP 1.0.4, Windows XP
Мои решения олимпиад на  Паскале: http://h0h0l.narod.ru/
Моя проверялка: http://www.proveryalka.narod.ru/
ICQ: 266367671

Поза форумом

 

#27 2005-12-22 15:26:28

Rybak
Олімпієць
Звідки: Киев, Украина
Зареєстрований: 2005-10-04
Повідомлень: 83
Вебсайт

Re: II тур - тесты и решения

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 баллов. Странно что дельфи не показывает ворнингов насчет этого sad

Поза форумом

 

#28 2005-12-23 13:36:21

ROBOT
Олімпієць
Звідки: Ялта
Зареєстрований: 2005-10-26
Повідомлень: 158

Re: II тур - тесты и решения

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 баллов. Странно что дельфи не показывает ворнингов насчет этого sad

спасибо, жаль что не знал..
главнное, я ведь проверял на больших числах - RunTimeError не было и я подумал, что всё ОК

Відредаговано ROBOT (2005-12-23 13:37:22)


I have Delphi 7, BP 7.0, FP 1.0.4, Windows XP
Мои решения олимпиад на  Паскале: http://h0h0l.narod.ru/
Моя проверялка: http://www.proveryalka.narod.ru/
ICQ: 266367671

Поза форумом

 

#29 2005-12-23 13:47:19

ROBOT
Олімпієць
Звідки: Ялта
Зареєстрований: 2005-10-26
Повідомлень: 158

Re: II тур - тесты и решения

Rybak написав:

Странно что дельфи не показывает ворнингов насчет этого sad

Я писал на Паскале


I have Delphi 7, BP 7.0, FP 1.0.4, Windows XP
Мои решения олимпиад на  Паскале: http://h0h0l.narod.ru/
Моя проверялка: http://www.proveryalka.narod.ru/
ICQ: 266367671

Поза форумом

 

#30 2005-12-23 14:32:16

Art[ASoft]
Олімпієць
Звідки: Alexandriya
Зареєстрований: 2005-11-13
Повідомлень: 19
Вебсайт

Re: II тур - тесты и решения

вот решение:

Код:

{ 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)


Good lamer - dead lamer!
FOS for ever!

Поза форумом

 

#31 2005-12-23 14:34:04

ROBOT
Олімпієць
Звідки: Ялта
Зареєстрований: 2005-10-26
Повідомлень: 158

Re: II тур - тесты и решения

Максим Медведь написав:

Объясните, пожалуйста, как в DSP может быть при тесте
22 16 5 3
ответ
22
???
У меня больше, чем 21 не получается (даже вручную...)

так:
====
||||_ _
||||==


I have Delphi 7, BP 7.0, FP 1.0.4, Windows XP
Мои решения олимпиад на  Паскале: http://h0h0l.narod.ru/
Моя проверялка: http://www.proveryalka.narod.ru/
ICQ: 266367671

Поза форумом

 

Нижній колонтитул

Powered by Likt
© Copyright 2002–2009 Likt