|
|
| Show all threads Hide all threads Show all messages Hide all messages | | How to solve it in less one second | 8848mzy | 1504. Good Manners | 15 Apr 2024 20:02 | 3 | Voroni diagrams perhaps (O(N*log(N)) I have AC 0.046s, O(K^3) with very simple approach | | Changes for 1504 "Good Manners" (+) | Vladimir Yakovlev (USU) | 1504. Good Manners | 5 Jan 2012 13:32 | 6 | Problem statement was updated:
• "All the pieces have distinct coordinates and lie on a table"
• "Coordinates should be precise up to 7 digits"
New tests have been added.
Timelimit was decreased to 3 seconds.
Submissions made after contest have been rejudged.
This problem suppose O(N^2) solution now. I think there is an O(NlogN) solution But how??? I solved this problem using quadro trees. My solution is about O(N^2*log(N)). What is O(N^2) or O(Nlog(N)) algo? Diagram of Voronoy - is O(n*log(n)) O(n^3) is also acceptable, but it seems to be O(n^2)
Edited by author 06.01.2012 03:13 | | Problem G: precisions | Sabbir Yousuf Sanny | 1504. Good Manners | 10 Nov 2011 11:21 | 3 | How many digits after the decimal point should we output? sanny vi, i have printed with %lf | | WA4 | Cat36 | 1504. Good Manners | 17 May 2011 14:19 | 2 | WA4 Cat36 11 May 2009 08:20 Re: WA4 Marshall Mathers 17 May 2011 14:19 | | I get Wrong Answer at #28 | xiaomengxian | 1504. Good Manners | 15 Mar 2007 12:03 | 2 | My algorithm is to consider every cake A from big to small to check whether Vovan can get. If Vovan wants to get cake A rather than B, he position must be in a certain arc in the cirlce, and the common part of these arcs is the available position. If the common part exists, then there is a solution that Vovan can get cake A.
I've checked my program for many times, but I don't know why I get Wrong Answer at #28. Please help me~
Edited by author 15.03.2007 11:59 I get Accepted.... I got WA because of the precision problem... | | To Authors! The tests are very simple!!! | Ostap Korkuna (LNU) | 1504. Good Manners | 6 Nov 2006 19:22 | 4 | I think the tests for this problem are very simple!!!
Here is the solution, which gets AC: I just divide the [-R; R] into 10 (!!!! only 10 !!!!!) parts and for every X from those 10 (!!!) values I calculate two corresponding Y => I get 20 points => calculate the nearest piece for every point and output the one with the biggest piece.
Isn't it to simple??? i did what you said, but got WA,
i also divided the interval into 100 parts
also getting WA
could you explain clearly I think, now the above solution is incorrect... Of course this solution gets WA now. Admins added new tests... | | To admins: Interesting... | Vasyl Biletskyy (Lviv NU) | 1504. Good Manners | 30 Oct 2006 23:16 | 2 | Interesting why this code gets Crash(2) if it is said that k <= 1000 ????
#include <stdio.h>
int main()
{
int k, r;
scanf("%d%d", &r, &k);
if(k > 1000)
throw 0;
else
printf("6 8\n");
return 0;
} Sorry, I've found my mistake - R is not integer.
BUT it is not clear from problem statement... | | Can you tell me why ? | N.M.Hieu ( DHSP ) | 1504. Good Manners | 29 Oct 2006 17:34 | 2 | I saw in the best solutions that there were some programs worked longer than 0.25s . Why could they get AC ? |
|
|
|
