| ENG RUS | Timus Online Judge |
Обсуждение задачи 1052. Охота на зайцевza-Nuker[2006] Could anyone help me please, WA on test #4 ? [1] // Задача 1052. Охота на зайцев 13 апр 2006 14:38 Hi, all. My program is generating all possible lines [ so they are only less or equal to C(n,2) lines were kept ]. I keep 'M' and 'C' of every line, sort them and then count the most appeared lines. When I count the most appeared lines, I multiplied it by 2, take sqrt and ceil it up. Like this : ans = (int) ceil(sqrt(2.0* max)); Above is from C(n,2) = maxline I use the formular c = (x1 y2 - x2 y1) / x1-x2 After I received WA#4 the first time, I changed all my code to keep M and C in fraction [ didn't divide it but keep 2 values ] to avoid error from floating point. I still get WA on test #4. Could anyone give me test case #4 to me, or some of test cases which might help me please? Thank you all in advance and sorry for my poor English ;-) Madhav Re: Could anyone help me please, WA on test #4 ? // Задача 1052. Охота на зайцев 15 июн 2008 14:57 don't try to use the concept of slope.Try to use the idea that if 3 points are collinear the area of triangle formed by those points is 0.Then u can avoid fractions.Note even that double values cannot be compared exactly which lead to WA.So try use the above idea mj256 How to solve this problem with an O(n^2) algo [1] // Задача 1052. Охота на зайцев 31 июл 2007 17:56 Metalmax Re: How to solve this problem with an O(n^2) algo // Задача 1052. Охота на зайцев 29 окт 2007 15:48 Well actually, if you know the O(n^2*logn) algorithm is simple -- using hash function which tells you for A,B and C of the line equation how many rabbits are before and just add. whutes multiple rabbits on same location? [1] // Задача 1052. Охота на зайцев 28 окт 2006 04:01 Is it possible that several rabbits sitting on top of each other at exactly the same location? Vitaliy_Ivashchenko Re: multiple rabbits on same location? // Задача 1052. Охота на зайцев 1 сен 2007 21:01 No two rabbits sit at one point zhangmuyang Any tricks in this problem? [9] // Задача 1052. Охота на зайцев 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. Miguel Angel Re: Any tricks in this problem? [7] // Задача 1052. Охота на зайцев 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; Huang Yizheng 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.. [4] // Задача 1052. Охота на зайцев 3 янв 2002 12:55 Miguel Angel 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 :) // Задача 1052. Охота на зайцев 5 янв 2002 11:20 > svr 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.. [1] // Задача 1052. Охота на зайцев 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 Alias (Alexander Prudaev) 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.. // Задача 1052. Охота на зайцев 16 мар 2007 22:18 1422 can be done with O(n^2) LADO ( TBILISI SU ) 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.. // Задача 1052. Охота на зайцев 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 zhangmuyang Re: Any tricks in this problem? // Задача 1052. Охота на зайцев 4 янв 2002 12:10 I used 'Extended' in Pascal(equals to 'long doulbe' in C++); Can it be OK? zhangmuyang Re: Any tricks in this problem? // Задача 1052. Охота на зайцев 4 янв 2002 12:10 I used 'Extended' in Pascal(equals to 'long double' in C++); Can it be OK? Molochiy Ivan[ Lviv NU ] Re: Any tricks in this problem? // Задача 1052. Охота на зайцев 9 мар 2007 20:15 Can rabbits be sutuated on diagonal? //Sorry for me English Ig Please,Give me test #1 // Задача 1052. Охота на зайцев 21 окт 2006 10:00 longzeling88 Why wrong answer 3??????? WHY? Y? [4] // Задача 1052. Охота на зайцев 15 сен 2004 15:22 This is my program in Pascal: [code deleted] Edited by moderator 06.07.2006 15:01 Gheorghe Stefan Re: Why wrong answer 3??????? WHY? Y? [2] // Задача 1052. Охота на зайцев 15 сен 2004 19:15 here it's test 3 (I don't know what is that last 0, but so it is. It should not matter): 16 15 15 16 17 17 19 18 21 19 23 75 19 16 62 13 69 10 76 7 83 4 90 1 97 -2 104 -5 111 -8 118 -11 125 The answer is: 10 (last 10 points of the input) Neo Nomaly Re: Why wrong answer 3??????? WHY? Y? [1] // Задача 1052. Охота на зайцев 2 мар 2005 15:37 What points are coliniar? Akshin Salimov Re: Why wrong answer 3??????? WHY? Y? // Задача 1052. Охота на зайцев 11 апр 2005 02:19 The points called coliniar if they lie on one line. For example (1,1) (2,2) (3,3) are coliniar. Edited by author 11.04.2005 02:22 Sasko Vuckov Re: Why wrong answer 3??????? WHY? Y? // Задача 1052. Охота на зайцев 6 июл 2006 04:09 try this: if you have: ------------ r:= y - k*x -n; if (result = 0) then on_line:= true else on_line := false; change it with: ------------ r := abs(y - k*x -n); if (result < 0.0000000001) then on_line:= true else on_line := false; prof Strange Compiler // Задача 1052. Охота на зайцев 7 авг 2005 23:30 I sent this task two times, but i was wondered. First time i got CE(LINK : fatal error LNK1104: cannot open file 'TEMPFILE') But when I sent it again I got AC. Inw Is this problem can solve using runtime less than n^3? // Задача 1052. Охота на зайцев 29 июл 2005 19:36 DOOM3er Give me some test // Задача 1052. Охота на зайцев 27 сен 2004 15:01 I got WA. PLZ give me some test. Bedny Yuri (bedny@rain.ifmo.ru) What's the problem with Extended? // Задача 1052. Охота на зайцев 21 фев 2002 02:34 Thist of all I sorry for my bad English. Please, help me to solve this problem! I don't understand why I get Crash(Access_Violation), then I use Extended type. And then I use Real Type, my program gets WA. The time of my program's work T~O(N^2), but it works very slow more than 1.7 second on WA test. Please, help me to know good alghorithm. Thanks. Igor hm... [1] // Задача 1052. Охота на зайцев 22 ноя 2001 21:24 Does the good hunter has to stand at the (0;0) point or wherever he's at the point he wants by the helicopter? Vladimir Milenov Vasilev Re: hm... // Задача 1052. Охота на зайцев 22 ноя 2001 22:25 The good hunter could stay at any point. Just find the biggest number of points, lying on one and same line - it doesn't need to be the line with equation y=x. Sasko Vuckov what should I output for n=1 or something else [1] // Задача 1052. Охота на зайцев 3 окт 2001 23:31 I generate all lines posible, and then count the rabbits on it. I get WA, so what should I output for n=1 or something else?????? Marat Bakirov Re: what should I output for n=1 or something else // Задача 1052. Охота на зайцев 6 окт 2001 04:05 Well, the problem text says : An input contains an integer N (2<=N<=200) So your question has no sense. N is NEVER EQUAL to 1.
|