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


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

Ви не зайшли.

#26 2009-11-28 23:45:58

guest1
Новий користувач
Зареєстрований: 2006-12-19
Повідомлень: 309
Вебсайт

Re: Обсуждение решений

NewIllusion напоминает какую-то схему метро smile
Какими-то продвинутыми методами рисовал, или, пардон, в paint'e?

Поза форумом

 

#27 2009-11-28 23:50:57

Слава
Олімпієць
Зареєстрований: 2005-10-15
Повідомлень: 68

Re: Обсуждение решений

guest1 написав:

NewIllusion напоминает какую-то схему метро smile
Какими-то продвинутыми методами рисовал, или, пардон, в paint'e?

Интересно сколько времени это займет нарисовать в paint???)))
А прога для графов -  специальная, довольно удобная - yEd Graph Editor


skype slava_812

Поза форумом

 

#28 2009-11-28 23:53:32

n1ce
Новий користувач
Зареєстрований: 2009-11-28
Повідомлень: 19

Re: Обсуждение решений

Лотто набрала 13 из 20.

Код:

int main()
{
    int n;
    scanf("%d",&n);
    filler();
    int ans;
    for (int i=0; i<10; i++)
    {
        ans=n*10+i;
        if (check(ans))
        {
            cout<<ans<<endl;
            return 0;
        }
    }
    for (int i=10; i<100; i++)
    {
        ans=n*100+i;
        if (check(ans))
        {
            cout<<ans<<endl;
            return 0;
        }
    }
    for (int i=100; i<1000; i++)
    {
        ans=n*1000+i;
        if (check(ans))
        {
            cout<<ans<<endl;
            return 0;
        }
    }
    return 0;
}

Ф-ция check проверяет на простоту правильно, только она длинная из-за использования быстрого алгоритма, который проверен на брутфорсе. В чем может быть проблема?

Відредаговано n1ce (2009-11-28 23:54:35)

Поза форумом

 

#29 2009-11-28 23:58:18

guest1
Новий користувач
Зареєстрований: 2006-12-19
Повідомлень: 309
Вебсайт

Re: Обсуждение решений

Слава написав:

А прога для графов -  специальная, довольно удобная - yEd Graph Editor

Ну, если энтузиазма хватит, то и в paint'e можно smile за название спасибо, посмотрю что за вещь.

n1ce, если я правильно понял, то
1) там может быть TL из-за того, что ты просматриваешь все цифры от 0 до 9 в конце вместо только 1, 3, 7, 9;
2) ты рассматриваешь 10..99, а надо 00..99. И соответственно не 100..999, а 000..999 и т. д.

Відредаговано guest1 (2009-11-29 00:01:08)

Поза форумом

 

#30 2009-11-28 23:59:57

n1ce
Новий користувач
Зареєстрований: 2009-11-28
Повідомлень: 19

Re: Обсуждение решений

guest1 написав:

А прога для графов -  специальная, довольно удобная - yEd Graph Editor

Ну, если энтузиазма хватит, то и в paint'e можно smile за название спасибо, посмотрю что за вещь.

n1ce, если я правильно понял, то
1) там может быть TL из-за того, что ты просматриваешь все цифры от 0 до 9 в конце вместо только 1, 3, 7, 9;
2) ты рассматриваешь 10..99, а надо 00..99. И соответственно не 100..999, а 000..999 и т. д.

Та если бы, но выдает WA.

Поза форумом

 

#31 2009-11-29 00:00:10

Слава
Олімпієць
Зареєстрований: 2005-10-15
Повідомлень: 68

Re: Обсуждение решений

n1ce написав:

Лотто набрала 13 из 20.
Ф-ция check проверяет на простоту правильно, только она длинная из-за использования быстрого алгоритма, который проверен на брутфорсе. В чем может быть проблема?

А если к числу нужно дописать с ведущими нулями? Например для 46587 ответом будет 4658701, а у тебя такие случаи не проверяются


skype slava_812

Поза форумом

 

#32 2009-11-29 00:00:29

guest1
Новий користувач
Зареєстрований: 2006-12-19
Повідомлень: 309
Вебсайт

Re: Обсуждение решений

Значит, вариант 2.

Поза форумом

 

#33 2009-11-29 00:01:03

n1ce
Новий користувач
Зареєстрований: 2009-11-28
Повідомлень: 19

Re: Обсуждение решений

Блин, протупил, епт) спасибо!

Поза форумом

 

#34 2009-11-29 00:05:20

Слава
Олімпієць
Зареєстрований: 2005-10-15
Повідомлень: 68

Re: Обсуждение решений

Radars: (20 из 20)

Код:

#include<iostream>
#include<math.h>
using namespace std;

int main()
{
    int a[100001],n,mn=100001,mx=-100001,i,k,d,p=200001,t;
    long long r;
    cin>>n;
    for(i=0;i<n;i++)
    {
        cin>>a[i];
        if(a[i]>mx)mx=a[i];
        if(a[i]<mn)mn=a[i];
    }
    d=(mn+mx);
    for(i=0;i<n;i++)
    {
        t=abs(d-2*a[i]);
        if(t<p){p=t;k=i;}
    }
    r=(long long)(mx-a[k])*(long long)(a[k]-mn);
    cout<<r<<endl;
    return 0;
}

skype slava_812

Поза форумом

 

#35 2009-11-29 00:12:39

Andrey
Олімпієць
Звідки: Киев, Украина
Зареєстрований: 2005-10-15
Повідомлень: 100

Re: Обсуждение решений

Мои Radar, Lazer набрали по 20, а в Lotto тоже не учел возможность добавления сначала 0я и набрал 13 =\

Поза форумом

 

#36 2009-11-29 00:21:29

LeonID
Новий користувач
Зареєстрований: 2008-12-09
Повідомлень: 160

Re: Обсуждение решений

Andrey написав:

Мои Radar, Lazer набрали по 20, а в Lotto тоже не учел возможность добавления сначала 0я и набрал 13 =\

Поторопился. А ведь времени было много. Только проверяй и перепроверяй.

Поза форумом

 

#37 2009-11-29 00:22:26

Andrey
Олімпієць
Звідки: Киев, Украина
Зареєстрований: 2005-10-15
Повідомлень: 100

Re: Обсуждение решений

LeonID написав:

Andrey написав:

Мои Radar, Lazer набрали по 20, а в Lotto тоже не учел возможность добавления сначала 0я и набрал 13 =\

Поторопился. А ведь времени было много. Только проверяй и перепроверяй.

Так я вообще не успел отправить) Думал сегодня порешаю. Я порешал и как раз закрыли отправку)

Відредаговано Andrey (2009-11-29 00:22:55)

Поза форумом

 

#38 2009-11-29 00:25:21

Присяжнюк А.В.
Новий користувач
Звідки: Бердичів СЗОШ 17
Зареєстрований: 2005-11-19
Повідомлень: 140
Вебсайт

Re: Обсуждение решений

Andrey написав:

Так я вообще не успел отправить) Думал сегодня порешаю. Я порешал и как раз закрыли отправку)

Особо не расстраивайтесь - в последующих турах задачи "стоят" в баллах больше и есть шанс все исправить и попасть на реал-тайм тур.
Так что еще далеко не все потеряно.


Права на ошибку не имеет тот, кто ничего не делает...

Поза форумом

 

#39 2009-11-29 00:26:36

LeonID
Новий користувач
Зареєстрований: 2008-12-09
Повідомлень: 160

Re: Обсуждение решений

Andrey написав:

LeonID написав:

Andrey написав:

Мои Radar, Lazer набрали по 20, а в Lotto тоже не учел возможность добавления сначала 0я и набрал 13 =\

Поторопился. А ведь времени было много. Только проверяй и перепроверяй.

Так я вообще не успел отправить) Думал сегодня порешаю. Я порешал и как раз закрыли отправку)

Так ведь вроде сегодня уже нельзя было отправлять решения. По регламенту.

Поза форумом

 

#40 2009-11-29 00:27:19

Слава
Олімпієць
Зареєстрований: 2005-10-15
Повідомлень: 68

Re: Обсуждение решений

2Присяжнюк А.В.: А будут ли потом эти задачи на e-olimp.com ???


skype slava_812

Поза форумом

 

#41 2009-11-29 00:28:02

Andrey
Олімпієць
Звідки: Киев, Украина
Зареєстрований: 2005-10-15
Повідомлень: 100

Re: Обсуждение решений

LeonID написав:

Andrey написав:

LeonID написав:


Поторопился. А ведь времени было много. Только проверяй и перепроверяй.

Так я вообще не успел отправить) Думал сегодня порешаю. Я порешал и как раз закрыли отправку)

Так ведь вроде сегодня уже нельзя было отправлять решения. По регламенту.

Ну до часов 6и активной светилась еще страница регистрации

Поза форумом

 

#42 2009-11-29 00:29:26

Слава
Олімпієць
Зареєстрований: 2005-10-15
Повідомлень: 68

Re: Обсуждение решений

Andrey написав:

LeonID написав:

Andrey написав:


Так я вообще не успел отправить) Думал сегодня порешаю. Я порешал и как раз закрыли отправку)

Так ведь вроде сегодня уже нельзя было отправлять решения. По регламенту.

Ну до часов 6и активной светилась еще страница регистрации

Регистрация будет доступна вплоть до конца третьего тура


skype slava_812

Поза форумом

 

#43 2009-11-29 00:31:50

Andrey
Олімпієць
Звідки: Киев, Украина
Зареєстрований: 2005-10-15
Повідомлень: 100

Re: Обсуждение решений

я хотел сказать "отсылки решений" roll

Поза форумом

 

#44 2009-11-29 00:38:28

Присяжнюк А.В.
Новий користувач
Звідки: Бердичів СЗОШ 17
Зареєстрований: 2005-11-19
Повідомлень: 140
Вебсайт

Re: Обсуждение решений

Слава написав:

2Присяжнюк А.В.: А будут ли потом эти задачи на e-olimp.com ???

Если Юрий Яковлевич даст добро - то почему бы и нет?
Мы только за, тем более, что работаем в поддержку друг друга, да и задачи у платформ разные. Тут - дополнительно отбирать на всеукраинскую, а на e-olimp -  тренировать.
Кроме того, они обязательно будут доступны здесь по окончанию в режиме он-лайн.


Права на ошибку не имеет тот, кто ничего не делает...

Поза форумом

 

#45 2009-11-29 01:04:26

pilya
Новий користувач
Зареєстрований: 2009-11-14
Повідомлень: 98

Re: Обсуждение решений

Слава написав:

Lotto: (20 из 20)

Код:

#include<iostream>
#include<math.h>
using namespace std;

bool prost(int a)
{
  if((a==1)||(a==0)) return false;
  int b=(int)(sqrt((double) a));
  for(int i=2;i<=b;i++)
      if(a%i==0)
          return false;
  return true;
}

int main2(int n)
{
    int l=1,s,r,i,k;
    while(true)
    {
        k=n;s=1;
        for(i=0;i<l;i++)s*=10;
        k*=s;
        for(i=0;i<s;i++)
        {
            r=k+i;
            if(prost(r))
                return r;
        }
        l++;
    }
}
int main()
{
    int n;
    cin>>n;
    cout<<main2(n)<<endl;
    return 0;
}

Обидно когда даже в первом туре допускается проверка на простоту таким не опимизированным методом. Я думаю жури следует задуматься. Программа как минимум выполняется раза в 2-а медленее чем у guest1.

Поза форумом

 

#46 2009-11-29 01:12:09

LeonID
Новий користувач
Зареєстрований: 2008-12-09
Повідомлень: 160

Re: Обсуждение решений

LeonID написав:

lazer(не самое оптимальное решение smile, но надеюсь правильное)

Код:

var
dx,dy,j,kilk,kilkprobitix,xk,yk,rk,koefficient:longint;
function perevirkaprobitosi(x,y,r:longint):boolean;
var
i,pochatok,kinec:longint;
xpromen,ypromen,nablizennja:extended;
begin
if abs(dx)>=abs(dy) then begin
if (dx>=0) and (dy>=0) then begin
if x-r<0 then pochatok:=0 else pochatok:=x-r;
if x+r<0 then kinec:=0 else kinec:=x+r;
  for i:=(pochatok-1) to (kinec+1) do begin
       xpromen:=i;
       if dx=0 then begin ypromen:=i;xpromen:=0;end else ypromen:=xpromen*(dy/dx);
                        if (sqr(xpromen-x)+sqr(ypromen-y))<(r*r) then begin
                        perevirkaprobitosi:=true;break;end else
                        perevirkaprobitosi:=false;
   end;
   end else
if (dx>=0) and (dy<=0) then begin
if x-r<0 then pochatok:=0 else pochatok:=x-r;
if x+r<0 then kinec:=0 else kinec:=x+r;
   for i:=(pochatok-1) to (kinec+1) do begin
       xpromen:=i;
       if dx=0 then begin ypromen:=-i;xpromen:=0;end else ypromen:=xpromen*(dy/dx);
                        if (sqr(xpromen-x)+sqr(ypromen-y))<(r*r) then begin
                        perevirkaprobitosi:=true;break;end else
                        perevirkaprobitosi:=false;
   end;
   end else
if (dx<=0) and (dy>=0) then begin
if x+r>0 then pochatok:=0 else pochatok:=x+r;
if x-r>0 then kinec:=0 else kinec:=x-r;
   for i:=(abs(pochatok)-1) to (abs(kinec)+1) do begin
       xpromen:=-i;
       if dx=0 then begin ypromen:=-i;xpromen:=0;end else ypromen:=xpromen*(dy/dx);
                        if (sqr(xpromen-x)+sqr(ypromen-y))<(r*r) then begin
                        perevirkaprobitosi:=true;break;end else
                        perevirkaprobitosi:=false;
   end;
   end else begin
   if x+r>0 then pochatok:=0 else pochatok:=x+r;
   if x-r>0 then kinec:=0 else kinec:=x-r;
   for i:=(abs(pochatok)-1) to (abs(kinec)+1) do begin
       xpromen:=-i;
       if dx=0 then begin ypromen:=i;xpromen:=0;end else ypromen:=xpromen*(dy/dx);
                        if (sqr(xpromen-x)+sqr(ypromen-y))<(r*r) then begin
                        perevirkaprobitosi:=true;break;end else
                        perevirkaprobitosi:=false;
   end;
   end;
   end else begin
   {------------------------------------------------------------------------}

if (dx>=0) and (dy>=0) then begin
if y-r<0 then pochatok:=0 else pochatok:=y-r;
if y+r<0 then kinec:=0 else kinec:=y+r;
  for i:=(pochatok-1) to (kinec+1) do begin
       ypromen:=i;
       if dy=0 then begin xpromen:=i;ypromen:=0;end else xpromen:=ypromen*(dx/dy);
                        if (sqr(xpromen-x)+sqr(ypromen-y))<(r*r) then begin
                        perevirkaprobitosi:=true;break;end else
                        perevirkaprobitosi:=false;
   end;
   end else
if (dx>=0) and (dy<=0) then begin
if y+r>0 then pochatok:=0 else pochatok:=y+r;
if y-r>0 then kinec:=0 else kinec:=y-r;
   for i:=abs(pochatok-1) to abs(kinec+10) do begin
       ypromen:=-i;
       if dy=0 then begin xpromen:=i;ypromen:=0;end else xpromen:=ypromen*(dx/dy);
                        if (sqr(xpromen-x)+sqr(ypromen-y))<(r*r) then begin
                        perevirkaprobitosi:=true;break;end else
                        perevirkaprobitosi:=false;
   end;
   end else
if (dx<=0) and (dy>=0) then begin
if y-r<0 then pochatok:=0 else pochatok:=y-r;
if y+r<0 then kinec:=0 else kinec:=y+r;
  for i:=(pochatok-1) to (kinec+1) do begin
       ypromen:=i;
       if dy=0 then begin xpromen:=i;ypromen:=0;end else xpromen:=ypromen*(dx/dy);
                        if (sqr(xpromen-x)+sqr(ypromen-y))<(r*r) then begin
                        perevirkaprobitosi:=true;break;end else
                        perevirkaprobitosi:=false;
   end;
   end else begin
   if y+r>0 then pochatok:=0 else pochatok:=y+r;
   if y-r>0 then kinec:=0 else kinec:=y-r;
   for i:=abs(pochatok-1) to abs(kinec+1) do begin
       ypromen:=-i;
       if dy=0 then begin xpromen:=-i;ypromen:=0;end else xpromen:=ypromen*(dx/dy);
                        if (sqr(xpromen-x)+sqr(ypromen-y))<(r*r) then begin
                        perevirkaprobitosi:=true;break;end else
                        perevirkaprobitosi:=false;
   end;
   end;

   {------------------------------------------------------------------------}
   end;
end;
begin
read(kilk);
read(dx,dy);
for j:=1 to kilk do begin
    read(xk,yk,rk);
    koefficient:=10000 div rk;
    xk:=xk*koefficient;yk:=yk*koefficient;rk:=rk*koefficient;
    if perevirkaprobitosi(xk,yk,rk) then inc(kilkprobitix);
    end;
writeln(kilkprobitix);
end.

15 балов. Некоторые тесты не прошли по времени, но если заменить в строке koefficient:=10000 div rk; число 10000 на 1000, задача берет 20 баллов. Обидно, да.

Поза форумом

 

#47 2009-11-29 08:03:51

Ilya Porublyov
журі
Зареєстрований: 2005-10-27
Повідомлень: 130

Re: Обсуждение решений

2 LeonID (попереднє повідомлення).

Такий підхід радує тим, що не опускаєте руки і намагаєтесь хоч якось все-таки розв'язати задачу. Але в усіх інших смислах не радує зовсім.

По-перше, "еталонний" розв'язок не містить перебору координат, а лише один-єдиний цикл перебору всіх кульок (звісно, не рахуючи цикла на введення вхідних даних). Рішення про те, пробита вона чи ні, приймається на основі (зокрема, але не тільки) обчислення відстані від точки (центру кульки) до прямої (продовження променю).

По-друге, чотири майже однакових, але все-таки різних не дуже маленьких шматочки програми -- то не є добре. Кожен раз, коли бачимо, що щось було не так і його треба справити, доводиться справляти його у чотирьох місцях. І тут дуже легко заплутатися: у двох дійсно справити, третій взагалі пропустити (випадково промахнувся переводячи курсор), а в четвертому поміняти, але не так як треба. І потім можна дуже довго шукати помилку...

pilya написав:

Обидно когда даже в первом туре допускается проверка на простоту таким не опимизированным методом. Я думаю жури следует задуматься. Программа как минимум выполняется раза в 2-а медленее чем у guest1.

Журі категорично не ставить за мету обов'язково відсікати розв'язки, швидкість яких відрізняється у два рази -- не лише на 1-му турі, а й на інших. Якби ми ставили за мету обов'язково відсікати розв'язки, удвічі повільніші за найкращий, вийшло б, що для кожної задачі необхідно індивідуально дослідити яку мову програмування краще використати і які повиставляти директиви/ключі компілятору. Щось мені підказує, що ні учасникам таке не_сподобалося б, ні журі не_відчуває такої потреби.

А от асимптотично неефективні розв'язки, наприклад, перевірка простоти циклом до самого числа, а не до кореня

Код:

dn := 0;
for p:=1 to i do
  if i mod p = 0 then
    dn := dn + 1;
if dn=2 then ...{просте}...

як правило набирають не повні бали навіть у першому турі.

Це звісно не означає, ніби робити дрібні оптимізації (які пришвидшують не асимптотично, а на скількись-там відсотків) зовсім не треба. Можливо, вони й вплинуть на те, чи вкладеться програма в обмеження часу (особливо якщо велика кількість таких дрібних оптимізацій сумарно дає пришвидшення скажімо у 5 разів). А можливо й ні (особливо, якщо йдеться не про 2 рази, а лише про 20--50%%). Конкретно при коефіцієнті 2... тяжко сказати, від чого більше тут залежить -- від свідомої волі журі чи від випадку.

Відредаговано Ilya Porublyov (2009-11-29 08:29:57)

Поза форумом

 

#48 2009-11-29 10:06:01

pilya
Новий користувач
Зареєстрований: 2009-11-14
Повідомлень: 98

Re: Обсуждение решений

Ilya Porublyov написав:

Журі категорично не ставить за мету обов'язково відсікати розв'язки, швидкість яких відрізняється у два рази -- не лише на 1-му турі, а й на інших.

Спасибо за ответ возможно это поможет не очень заморачиваться во втором туре smile.
И когда же наконец появятся задачи второго тура? и статистика чтот замолчала? Вчера до 24:00 было проверено аж три задачи, а за ночь ни одной.

Поза форумом

 

#49 2009-11-29 10:08:20

Loginf
Новий користувач
Зареєстрований: 2009-11-25
Повідомлень: 37

Re: Обсуждение решений

pilya написав:

И когда же наконец появятся задачи второго тура? и статистика чтот замолчала? Вчера до 24:00 было проверено аж три задачи, а за ночь ни одной.

Жюри ночью спали))

Відредаговано Loginf (2009-11-29 10:08:42)

Поза форумом

 

#50 2009-11-29 10:13:31

alexkasycky
Новий користувач
Звідки: Киев
Зареєстрований: 2009-11-29
Повідомлень: 30

Re: Обсуждение решений

По поводу ТЛ - дело запутанное, всегда так было, и всегда будет.
У меня претензии к тестам по задаче Radars:

Код:

#include<algorithm>
#include<iostream>
using namespace std;

int N;
int A[100000];

int main(){
    cin>>N;
    for(int i = 0; i < N ; i++)
        cin>>A[i];
    int L = *min_element(A,A+N);
    int R = *max_element(A,A+N);
    int M0 = (L+R)/2;// - очевидный баг!
    int M = L;
    for(int i = 0 ; i < N ; i++)
        if( abs(M0-A[i]) < abs(M0-M) )
            M = A[i];
    cout<< ((long long)(R-M))*(M-L) <<endl;
    return 0;
}

- вот это решение проходит все тесты. Придумать тест на котором оно валится очень просто. К примеру 3(кол-во чисел)  1 3 4.
Баг, имхо, очень ожидаемый и популярный :) и то что нету теста "на него" меня огорчает...


это тот же я что и alex_kasycky, но тот аккаунт не работает...

Поза форумом

 

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

Powered by Likt
© Copyright 2002–2009 Likt