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

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

Лотто набрала 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)

guest1 написав:

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

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

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

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

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

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;
}

Andrey написав:

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

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

Andrey написав:

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

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

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

Andrey написав:

LeonID написав:

Andrey написав:

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

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

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

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

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

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

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

LeonID написав:

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

Код:

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 баллов. Обидно, да.

Ilya Porublyov написав:

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

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

По поводу ТЛ - дело запутанное, всегда так было, и всегда будет.
У меня претензии к тестам по задаче 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.
Баг, имхо, очень ожидаемый и популярный :) и то что нету теста "на него" меня огорчает...