|
|
| Show all threads Hide all threads Show all messages Hide all messages | | WA on test № 7 | Vasily Slesarev | 1492. Vasya's Dad 2 | 22 Dec 2018 04:18 | 2 | I have no ideas...
Please, give me some tests! If you get WA on case 7, it's probably because you have three neighboring points in your answer to be on the same line. | | Did anybody have troubles with test#5 ? | Kraev Alexey | 1492. Vasya's Dad 2 | 5 Feb 2013 20:24 | 19 | Consider test:
3
-15000 0
-14999 0
15000 1
is the output
Yes
-15000.000000 0.500000
-14999.000000 0.499983
14999.000000 0.499983
15000.000000 0.500000
-15000.000000 -0.500000
-14999.000000 -0.499983
14999.000000 0.499983
15000.000000 0.500000
correct ?
I mean if we output only 4 digits it turns into
Yes
-15000.0000 0.5000
-14999.0000 0.5000
14999.0000 0.5000
15000.0000 0.5000
-15000.0000 -0.5000
-14999.0000 -0.5000
14999.0000 0.5000
15000.0000 0.5000 Yes. Both outputs are correct. Really mysterious test...
I can't find error in my program too... Oh! What's a bug! The following test helped me to fix it:
Sample input:
7
-5 2
-4 1
-3 -1
-2 -4
-1 -6
0 -7
5 0
Sample output:
Yes
-5 1.0
-4 -0.2
-3 -1.9
-2 -4.1
-1 -5.8
0 -7.0
1 -5.8
2 -4.1
3 -1.9
4 -0.2
5 1.0
-5 1.0
-4 1.2
-3 0.9
-2 0.1
-1 -0.2
1 0.2
2 -0.1
3 -0.9
4 -1.2
5 -1.0 My program passes this test but still wa5 Friens!. I had no problems with 1492 because used module of fracrion numbers(1274) or in other word used exact arithmetics. Dont use rouunding , epsilon but just exact type. Then troubles owing to too complicated cod. Problem 1492 is for youngsters. Bounds 15000 are very small and may be worked with by using array F[30000] of fractions. For founding corner point x2 it may be used simplest idea of sliding triple (x-1,y1),(x,y2),(x+1,y) with checking y2*2==y1+y2 I used real arithmetics, and got AC. My be, it is overflow when use exact arithmetics? In any case, problem can be accepted in both cases.
Edited by author 22.06.2007 14:05 In our case we form fraction value
F(t)=y[i]+(t-x[i])*(y[i+1]-y[i])/(x[i+1]-x[i])
for t in [x[i];x[i+1]] and after that form
F1[t]=(F[t]+F[-t])/2 and F2[t]=(F[t]-F[-t])/2
t in [x[0],-x[0]].
Denumenator and numenator dosn't more than 30000*30000=
900000000 . By using __int64 as fraction components
we will in safety from overflow It is not the truth. It is possible to do it without exact arithmetics. The author's decision works without it. Wu mustn't repeat author solution. But when we use exact arithmetic we can formulate a problem as some statement on finite set and answer will definite and under control I have trouble)) I use exact arithmetics and get AC.
Me help test:
5
-3 4
-1 3
0 2
1 1
3 0
Yes
-3.0000 2.0000
3.0000 2.0000
-3.0000 2.0000
-1.0000 1.0000
1.0000 -1.0000
3.0000 -2.0000 Thanks, helped me to find a bug :) I wrote 0 if original function does not cross (0;0). Also I had some problems inside finding mid-point, including X=0 case.
Edited by author 19.08.2008 19:46 Solved without exact arithmetic or eps.
Just replace all divisions by multiplications :)
Edited by author 05.02.2013 20:25 I used cpp double and eps=1e-9 and got WA5. When i changed eps to 1e-6 i got AC. Maybe it'll helps you. I used pascal extended and eps=1e-6 and got WA 12. When I changed eps to 1e-9 I got AC... How strange... My eps in cpp double is 1e-9 - AC | | Hint | hoan | 1492. Vasya's Dad 2 | 15 Jan 2011 18:12 | 1 | Hint hoan 15 Jan 2011 18:12 Use eps= 1e-9.first i don't use eps and get WA#3.
this test help me:
input:
3
-15000 0
-14999 0
15000 1
output:
Yes
-15000.0000 0.5000
-14999.0000 0.5000
14999.0000 0.5000
15000.0000 0.5000
-15000.0000 -0.5000
-14999.0000 -0.5000
14999.0000 0.5000
15000.0000 0.5000
thank's to AlexF[USTU] about this note.
hope can help you. | | WA3 | r1d1 | 1492. Vasya's Dad 2 | 9 Jul 2010 08:32 | 1 | WA3 r1d1 9 Jul 2010 08:32 | | Very nice problem. (-) | Ilya Razenshteyn | 1492. Vasya's Dad 2 | 14 Jun 2007 23:22 | 4 | My respect to the author. It was interesting to solve it. Thanks :) Great thanks to the author! The problem is really nice) | | What output... | Kurpilyansky Eugene (USU) | 1492. Vasya's Dad 2 | 21 Jan 2007 19:18 | 3 | input
3
-1 0
0 0
1 0
what output?
Edited by author 24.12.2006 15:24 I got AC!!! Kurpilyansky Eugene (USU) 24 Dec 2006 15:10 output
Yes
-1.0000 0.0000
1.0000 0.0000
-1.0000 0.0000
1.0000 0.0000
Edited by author 24.12.2006 15:24 "...no three successive vertices belong to the same line..." | | Is it possible to add some tests? | Fyodor Menshikov | 1492. Vasya's Dad 2 | 3 Jan 2007 02:01 | 2 | My accepted program would fail on the following test:
4
-15000 -1
0 0
14999 1
15000 1
I think the test set does not contain test case with such smooth change of line inclination angle. Test is added. Thank you. | | Clarification (-) | Fedor Fominykh | 1492. Vasya's Dad 2 | 3 Nov 2006 07:40 | 1 | "Then output the coordinates of the breakpoints of the function. Each coordinate must contain at least four fractional digits" means it is needed to output coordinates of the breakpoints (i.e. if we use exact value of coordinates then there is no three successive vertices belong to the same line) and all coordinates must contain at least four fractional digits. |
|
|
|
