ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1052. Охота на зайцев

Any tricks in this problem?
Послано zhangmuyang 2 янв 2002 14:00
It seems that everything in my program is OK, but I still got
the "Wrong Answer". I wonder if someone can tell me if there is some
tricks in the program that I had neglected.
Re: Any tricks in this problem?
Послано Miguel Angel 3 янв 2002 11:50
I think there's no trick on this problem. The solution as you may
know is taking 2 points, do the lineal equation and try for all the
points if match in the line. Well, for this problem i saw the fact
that you can use integers without trying with floating point values
(how in city blocks) maybe a fact of rounding cause that you are not
taking some points. Hope this help you:
dy = y[j]-y[i];
dx = x[j]-x[i];
mx = 0;
    for (k=0; k<N; k++)
    if (y[k]*dx==dy*(x[k]-x[i])+dx*y[i]) ++mx;
I don't think your solution is efficient enough.Yours are O(n^3),but I have a O(n^2) one.You see that my program is the fastest of all.hehe..
Послано Huang Yizheng 3 янв 2002 12:55
Re: Any tricks in this problem?
Послано zhangmuyang 4 янв 2002 12:10
I used 'Extended' in Pascal(equals to 'long doulbe' in C++);
Can it be OK?
Re: Any tricks in this problem?
Послано zhangmuyang 4 янв 2002 12:10
I used 'Extended' in Pascal(equals to 'long double' in C++);
Can it be OK?
Well, not always we can have the best solution, but in the problem "Trash" I do(check time and memory), later i send to you :)
Послано Miguel Angel 5 янв 2002 11:20
>
Re: Any tricks in this problem?
Послано Molochiy Ivan[ Lviv NU ] 9 мар 2007 20:15
Can rabbits be sutuated on diagonal?

//Sorry for me English
Re: I don't think your solution is efficient enough.Yours are O(n^3),but I have a O(n^2) one.You see that my program is the fastest of all.hehe..
Послано svr 9 мар 2007 20:32
Value N=200 allow use O(N^3) algo.
Therefore better more simple and verified algorithm.
But there is 1422("svetlatcki") with N=2000 and n=3
which the same but need O(n^2lg(n)).
After 1052 try 1422 and question will be understood
at hole.

Edited by author 09.03.2007 20:39

Edited by author 09.03.2007 20:42
Re: I don't think your solution is efficient enough.Yours are O(n^3),but I have a O(n^2) one.You see that my program is the fastest of all.hehe..
Послано LADO ( TBILISI SU ) 16 мар 2007 13:14
Huang Yizheng писал(a) 3 января 2002 12:55
Huang Yizheng писал(a) 3 января 2002 12:55
Huang Yizheng писал(a) 3 января 2002 12:55
Huang Yizheng писал(a) 3 января 2002 12:55
Huang Yizheng писал(a) 3 января 2002 12:55
Huang Yizheng писал(a) 3 января 2002 12:55
Huang Yizheng писал(a) 3 января 2002 12:55
Huang Yizheng писал(a) 3 января 2002 12:55
Huang Yizheng писал(a) 3 января 2002 12:55
Re: I don't think your solution is efficient enough.Yours are O(n^3),but I have a O(n^2) one.You see that my program is the fastest of all.hehe..
Послано Alias (Alexander Prudaev) 16 мар 2007 22:18
1422 can be done with O(n^2)