| ENG RUS | Timus Online Judge |
Discussion of Problem 1331. VladislavaValeev Konstantin KRBO-04-19 Time limit for Phyton? // Problem 1331. Vladislava 4 Mar 2021 14:42 ограничение по времени для Питона не выполняется... maksay WA 13..Is it a precision problem? [2] // Problem 1331. Vladislava 22 Oct 2008 17:55 I get WA 13 again and again and I can not find a mistake. My main logic looks like this: for(j=0;j<n;j++) {l=(x[j]-X)*(x[j]-X)+(y[j]-Y)*(y[j]-Y)+(z[j]-Z)*(z[j]-Z); if (l-D<1e-10) D=l;} printf("%0.6f\n",acos((2-D)/2.0)*r); I believe it is correct..So can anybody help me with finding a bug, please? Does anyone have a same problem? Giorgi Giglemiani [Freeuni] Re: WA 13..Is it a precision problem? // Problem 1331. Vladislava 16 Oct 2013 15:47 I had exactly this kind of problem. WA13. then I wrote: double tmp= (2 - minL)/2.0; tmp-=0.00000000001; if (tmp<-1) tmp=-1; return r*Math.acos(tmp); and AC. It is problem with precision, of course. Ag'abek Re: WA 13..Is it a precision problem? // Problem 1331. Vladislava 4 Dec 2015 00:32 What is D ? Ade [FDU] acos(min(1, angle)) // Problem 1331. Vladislava 6 Dec 2014 13:46 vano_B1 Give me some test,please. [1] // Problem 1331. Vladislava 10 Jun 2005 01:14 Thanks. I find my mistake. Edited by author 10.06.2005 01:33 DarkDaiver Re: Give me some test,please. // Problem 1331. Vladislava 11 Jun 2009 22:01 Could anybody give my some difficult sample? I wanna check not trevial source data Sandro (USU) Problem 1331 "Vladislava" has been rejudged (+) [5] // Problem 1331. Vladislava 8 Apr 2007 01:12 61 submits lost AC verdict (many because of tricky 12 test). Try to find a bug in your source code. Good luck! P.S. Thanks to Alias (Alexander Prudaev) for idea of new tests. Alias (Alexander Prudaev) Re: Problem 1331 "Vladislava" has been rejudged (+) [4] // Problem 1331. Vladislava 8 Apr 2007 11:13 I have get AC again, but problem with test#3 is keep open -0.00 != 0.00 Edited by author 08.04.2007 11:42 Vladimir Yakovlev (USU) Re: Problem 1331 "Vladislava" has been rejudged (+) [3] // Problem 1331. Vladislava 8 Apr 2007 13:00 Problem with "-0.00" has been resolved yesterday. But your WA3-program outputs "1.#R". Edited by author 08.04.2007 13:01 Alias (Alexander Prudaev) Re: Problem 1331 "Vladislava" has been rejudged (+) [2] // Problem 1331. Vladislava 8 Apr 2007 13:55 I have send my program on your e-mail Alias (Alexander Prudaev) Re: Problem 1331 "Vladislava" has been rejudged (+) [1] // Problem 1331. Vladislava 8 Apr 2007 14:00 what is mean ? 1.#J 1.#R ??? Denis Koshman Re: Problem 1331 "Vladislava" has been rejudged (+) // Problem 1331. Vladislava 19 Aug 2008 04:21 Can be result of sqrt(-1) or acos(5), etc... Dart MirzMan C++ Edition (Mirzoyan Alexey, Rybinsk SAAT) some hint(+) [1] // Problem 1331. Vladislava 8 Apr 2007 21:56 Notice, that scalar product of two normalized vectors can be more than 1 on the module. Заметьте, что скалярное произведение двух нормализованных векторов по модулю может быть больше 1. Good luck! Dart MirzMan C++ Edition (Mirzoyan Alexey, Rybinsk SAAT) Re: some hint(+) // Problem 1331. Vladislava 16 Apr 2008 18:31 omg! i've read my first message and have terrified! some new hint: it's the problem with precision =) Dmitry 'Diman_YES' Kovalioff AC, but... "How soon is now?" How small is R? :) (+) [2] // Problem 1331. Vladislava 8 Apr 2007 20:41 Give me limitations for R, wi, li, Wi and Li. I do not know how small they are. So if R = 0.00000000000000001, this test is relly "tricky", I understand. Mischief managed :) P.S. To get AC after rejudge you should avoid floating point division in your program. Just simplify your formula. Samsonov Alex [USU] Re: AC, but... "How soon is now?" How small is R? :) (+) [1] // Problem 1331. Vladislava 8 Apr 2007 23:44 No, I use more than one floating point division and square roots in my program and I managed to get AC. My only bug was with the test, where points lie in the opposite to each other. [SPbSU ITMO] WiNGeR Re: AC, but... "How soon is now?" How small is R? :) (+) // Problem 1331. Vladislava 9 Apr 2007 04:23 There are no "bad" and "unpity" tests in this problem. And simple solution with floats can be AC'ed just after a bit of thinking ;) Edited by author 09.04.2007 04:47 Alias (Alexander Prudaev) [censored] checkers! AC at last! -0 != 0 [5] // Problem 1331. Vladislava 6 Apr 2007 22:35 if program writes -0, your [censored] checker says WA#3 inspite of accuracy in 2 digits. abs(-0-0) < 0.001 ! Edited by moderator 06.04.2007 22:54 Dmitry 'Diman_YES' Kovalioff Warning for you (+) [4] // Problem 1331. Vladislava 6 Apr 2007 22:54 I am tired of you who offends Timus Online Judge again and again. If you continue writing your posts to this board such a way, I will just remove them completely. Edited by author 06.04.2007 22:55 Alias (Alexander Prudaev) Re: Warning for you (+) [3] // Problem 1331. Vladislava 6 Apr 2007 23:28 After your edit, observers could have an impression that I have used an abusive word. It's not true, it was word "stupid" Sandro (USU) Checker is correct. In the 3rd test your output was -1.#J and 1.#R. (-) [2] // Problem 1331. Vladislava 7 Apr 2007 01:18 Alias (Alexander Prudaev) Re: Checker is correct. In the 3rd test your output was -1.#J and 1.#R. (-) [1] // Problem 1331. Vladislava 7 Apr 2007 22:05 you are wrong there is fragment of my program : double Norm(double x) { // if (x>0.001) return x; // else // return 0; } ... printf("%.2lf\n",Norm(abs(...))); ... with these commets program gets WA#3 without - AC if you want, i can send you my program entirely Edited by author 07.04.2007 22:15 Sandro (USU) Checker is really correct. (+) // Problem 1331. Vladislava 8 Apr 2007 00:56 Your WA and AC solution have are wrong both but tests are weak. You have WA after rejudge. Maigo Akisame (maigoakisame@yahoo.com.cn) How to avoid TLE?(-) [10] // Problem 1331. Vladislava 20 Oct 2004 15:09 Dmitry 'Diman_YES' Kovalioff Use double instead of extended (-) [4] // Problem 1331. Vladislava 20 Oct 2004 16:46 Maigo Akisame (maigoakisame@yahoo.com.cn) But I use real everywhere and do as much pre-calculation as possible. It's still TLE on test #4. [3] // Problem 1331. Vladislava 21 Oct 2004 04:45 program ural1331; const maxm=5000; zero=1e-6; var w,l,x,y,z:array[1..maxm]of real; n,m,i,j:word; r,ww,ll,xx,yy,zz,ans:real; procedure calcoord(var w,l,x,y,z:real); begin w:=w*pi/180; l:=l*pi/180; x:=cos(w)*cos(l); y:=cos(w)*sin(l); z:=sin(w); end; function min(a,b:real):real; begin if a<b then min:=a else min:=b; end; function arcsin(s:real):real; begin if s>1-zero then arcsin:=pi/2 else arcsin:=arctan(s/sqrt(1-s*s)); end; begin read(n,m,r); for i:=1 to m do begin read(w[i],l[i]); calcoord(w[i],l[i],x[i],y[i],z[i]); end; for i:=1 to n do begin read(ww,ll); calcoord(ww,ll,xx,yy,zz); ans:=1e38; for j:=1 to m do ans:=min(ans,sqr(xx-x[j])+sqr(yy-y[j])+sqr(zz-z[j])); writeln(arcsin(sqrt(ans)/2)*2*r:0:2); end; end. Dmitry 'Diman_YES' Kovalioff There are a lot of calculations in your program - optimize it (-) // Problem 1331. Vladislava 21 Oct 2004 22:25 Michael Rybak (accepted@ukr.net) Calling "min" function slows your program (-) [1] // Problem 1331. Vladislava 25 Oct 2004 23:02 Edited by author 26.10.2004 00:27 Maigo Akisame (maigoakisame@yahoo.com.cn) Thanks. I use dot product this time and deleted the min/max function. Ac in 0.671s. // Problem 1331. Vladislava 26 Oct 2004 04:39 Korduban [Kiev] Use octtree structure (+) [4] // Problem 1331. Vladislava 7 Feb 2005 23:01 subj. My program get AC in 0.302 (without optimizations). I think it's possible to reduce time to 0.150 sec http://acm.timus.ru/status.aspx?space=1&pos=737505 Edited by author 07.02.2005 23:03 Ariel Strange! My brute force got AC in 0.39. And what is it "octtree structure" (-) [3] // Problem 1331. Vladislava 8 Feb 2005 00:11 Korduban [Kiev] Could you mail your AC code to dkorduban [at] ukr.net? (-) // Problem 1331. Vladislava 8 Feb 2005 15:56 Korduban [Kiev] Accepted in 0.171 (+) [1] // Problem 1331. Vladislava 9 Feb 2005 17:41 svr Re: Accepted in 0.171 (+) // Problem 1331. Vladislava 20 Nov 2006 14:32 Middle time of speed can be taken by using simple qsort of points by key=max(y[i],i=1,..3) and then log-time search of pozition of point x[k] under consideration in sorted array with cutting off parts of array y which far enough from the pozition. Petr Dot product...Help please [5] // Problem 1331. Vladislava 1 Jul 2006 20:31 I use it in my prog, but it gets TLE4. Help please. Here is my sol [code deleted] Edited by moderator 02.07.2006 13:25 Petr ? [4] // Problem 1331. Vladislava 6 Jul 2006 14:27 2moderators: Why some people can print their solution-cod on forums, but some can't? What it depend on? Number of solved problems? Nickname(for example if I'll write my e-mail in brackets after my name it will be more respectful...)? Dmitry 'Diman_YES' Kovalioff You misunderstood something (+) [3] // Problem 1331. Vladislava 6 Jul 2006 15:00 Noone is allowed to post any code here in accord with the fourth rule of Timus Online Judge Webboard ("Messages should NOT contain source code..."). Despite the rank and respect rate. Even I cannot :) But there are some old topics which contain source code - the moderators just have no time to delete them all. Petr . [2] // Problem 1331. Vladislava 6 Jul 2006 15:53 THX for explanation. But I misunderstood sth also. Some people put at the end of their's report's headline '(+)' or '(-)'. What it's meen? Dmitry 'Diman_YES' Kovalioff Well, it is just a style of posting messages (+) [1] // Problem 1331. Vladislava 6 Jul 2006 16:07 '(-)' means the body of the message is empty, because everything is said directly in the subject. If my message is short enough to fit the subject, I just warn the reader that there is nothing more in the body... '(+)' means I want to say something else in the body. Petr Thx(-) // Problem 1331. Vladislava 6 Jul 2006 16:27 UXMRI: Sergey Baskakov, Raphail Akhmedisheff and Denis Nikonorov Hey, Guys How Can You Make It So Quick? [1] // Problem 1331. Vladislava 31 Dec 2005 22:28 I've implemented an octtree (I used http://www.nist.gov/dads/HTML/octree.html as a reference on this data structure, it's easy to understand. Just try it!) I've got AC, but I cann't make it run quicker, than 0.4 sec. If you need my source code to help me, or have anything else to tell me, feel free to e-mail to urrel AT rambler DOT ru. UXMRI: Sergey Baskakov, Raphail Akhmedisheff and Denis Nikonorov I think, I've got it... // Problem 1331. Vladislava 1 Jan 2006 00:43 Well, there has been a way to optimize the logic of my algo, that wasn't evident for me at first... Here is the result (0.109 sec): http://acm.timus.ru/rating.aspx?space=1&num=1331 http://acm.timus.ru/status.aspx?space=1&pos=1004143 Happy New Year to everybody (Right now it is 31 dec 2004, 22:45 here, is Astrakhan). Be happy, Don't worry! Good luck in solving problems, Rafail Ahmadisheff. Dark Help! How to do it faster??? (TLE test#3) [1] // Problem 1331. Vladislava 3 Jun 2005 21:12 #include <stdio.h> #include <math.h> const double PI = 3.141592653; int n,m,i,i2; double radius; double stp[5000],dtp[5000]; double sa,da,mindist,tmp; double dist(double s1, double d1, double s2, double d2) { double x1,y1,x2,y2,z1,z2,s,d; s = s1*PI/180.0; d = d1*PI/180.0; x1 = cos(s)*cos(d); y1 = cos(s)*sin(d); z1 = sin(s); s = s2*PI/180.0; d = d2*PI/180.0; x2 = cos(s)*cos(d); y2 = cos(s)*sin(d); z2 = sin(s); double a,b,c,alp; a = 1; b = 1; c = sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2) + (z1-z2)*(z1-z2)); alp = acos((a*a + b*b - c*c)/(2*a*b)); return alp; } int main() { // freopen("input.txt","r",stdin); // freopen("output.txt","w",stdout); scanf("%d %d",&n,&m); scanf("%lf",&radius); for (i = 0; i<m; i++) { scanf("%lf %lf",&stp[i], &dtp[i]); } for (i = 0; i<n; i++) { scanf("%lf %lf",&sa, &da); mindist=9999999; for (i2 = 0; i2<m; i2++) { tmp = dist(sa,da,stp[i2],dtp[i2]); if (tmp<mindist) mindist = tmp; } printf("%.2lf\n",mindist*radius); } return 0; } Фоминых Федор Re: Help! How to do it faster??? (TLE test#3) // Problem 1331. Vladislava 2 Jul 2005 20:36 ACcepted!!! time : 0.39 memory : 386 КБ http://acm.timus.ru/status.aspx?space=1&pos=870473 Edited by author 02.07.2005 20:36 Edited by author 02.07.2005 20:37 Neumann something surprise...... // Problem 1331. Vladislava 4 Mar 2005 22:17 some of my code: { now:=sqr(x1[i]-x)+sqr(y1[i]-y)+sqr(z1[i]-z); if now-ans<zero then ans:=now; } If I make zero=-1e-6,WA.But if make zero=0 or zero=-1e-10 it got AC... If it is about precision, why zero=0 OK? Edited by author 04.03.2005 22:20
|