| Show all threads Hide all threads Show all messages Hide all messages |
| Help me please!!! WA on test 3... | Alex[LSD] | 1312. Tray | 28 Aug 2008 15:00 | 7 |
Is it forbidden to post WRONG programs here?
Anyways my idea is :
If there exists a solution then there exists a solution where two circles are in the corners of the rectangle. It is obvious because there is always the rightmost and the leftmost circle and we can drag them all the way to the corner.
So what I do is: I take every pair of circles, try to put each of them in every corner (16 variants for a pair of circles). Then I "erase" all the area, where the center of the 3rd circle can not be located. Firstly, the last circle (I mean it's center) has to be located inside a rectangle (W-2R)x(H-2R) whre R - is the radius. We also must exclude two circles with radii R1+R and R2+R where R1 and R2 are the radii of the already existing circles.
I store all the intersections of the 2 circles with the 4 lines (sides of the rectangle) and check all these points if they are possible positions for the last circle's center.
Please tell me where am I wrong, or give me some critical test data.
Thanks in advance.
alex[LSD], a dumb russian programmer. The correct algo is much more complicated, and I don't want to explain it here - everyone who wants to solve this problem should manage it himself.
First try my favorite test (I am not sure your program fails on it, I just like this test):
1000000 1000000 250001 250001 278000
There IS a solution :) Thanks, your test was really helpful. The algo is wrong, but not completely. My assumption about 2 corners was wrong, but the idea with rectangle and circles was pretty good. It just needed a recursive approach. I was amased that your original algorithm was exactly the same as me and I also got WA on test 3! I also failed in the testdata 1000000 1000000 250001 250001 278000! Amazing!
Now I get AC and I want to say something.
You said there are two "corner-center" points on the rectangle.The fact is that there is only one!!! (I can prove , but not very strict with one part,though it seems obvious) 1000000 1000000 250001 250001 278000 is just the counterexample of "two points". Use only one corner and then deal with two groups of intersections,you will get it!! 1000000 1000000 250001 250001 278000 work, but 3 WA, give something interesting tests, please Previouce people sad that AC algorithm much more complicated.
But really AC algorithm much more simple, pure geometric and without otimization.
One circle in corner and others have two opportunities:
to be in another corner or to be adjacent to first circle
and one of the sides of rectangle.
Thus their centers determined. After we make verification:compare distance between centers and value
R2+R3-eps. If first value greater than second- OK.
This is only verification wich made with eps.
Other verifications of placement should better make
in __int64.
Edited by author 13.09.2007 12:27 To svr. I've got AC with doubles and my default precision of 1e-8. No int64 at all.
To all: I had WA3 because of wrong code for circle removal (it remained marked as used). Try to shuffle numbers in the first test and see if something strange happens or not. |
| Also WA13. What to do? Some tricky tests? (-) | AlMag | 1611. Decimation | 28 Aug 2008 11:51 | 1 |
|
| Answer | Sid | 1340. Cucaracha | 27 Aug 2008 22:15 | 4 |
Are you sure there isn't 3rd case when initial path is a piece of line? Especially when crumb is closer to back side of the right circle. line+arc is never necessary. At least on given tests. |
| How can cockroach reach the crump... | Sid | 1340. Cucaracha | 27 Aug 2008 11:46 | 4 |
How can cockroach reach the crump if it in circle he starting running along (I mean circle which center is closer to crumb). Can he go stright ahead and then go along the circle or he has to go along other circle firstly???
I' ve tried both variants.. but i have WA#13. I've tried lots of variants of my solution... But if the optimal solution in this case is spiral, it gonna fail... BTW, here is approximately this very test after my normalization:
0 0 90 94.85
4.5 10.07
My answer is 605.5647, but it seems to be wrong
P.S. My geometry has always been unbeatable, so one day I will solve this problem ;) It is realy wrong
Right one is 604.4120
Edited by author 27.08.2008 22:14 |
| What mean... | Dembel {AESC USU} | 1340. Cucaracha | 27 Aug 2008 11:44 | 2 |
What mean "the minimal turning radius of the cockroach"?
Edited by author 22.12.2006 19:29 It means that no arc on a cocroach path can have radius less than R. Lines are considered as arcs of infinite radius and sharp turns are considered as arcs of 0 radius. |
| complexity | UdH-WiNGeR | 1464. Light | 27 Aug 2008 09:45 | 3 |
My solution is O(n*log n) and i wonder if there is a linear? My solution is O(n*log(n)) too... I have an idea for linear-time solution, but I didn't implement it. Walk in coutner-clockwise order. While the lamp is in positive half-plane (i.e. we face inner side of a segment), add it. Once we face outer side (i.e. lamp is in negative half-plane), we cast darkness backwards in clockwise order from i+1'th vertex of outer side. Also, there will be no light until we reach its i'th angle. So, "forwards darkness" is skipped as long as we walk counter-clockwise forwads and "backwards darkness" pointer only deceases (walks only clockwise). |
| look this | 连连 | 1057. Amount of Degrees | 27 Aug 2008 06:28 | 6 |
I input test data: 100 200 3 3
Is the example right?
100 = 3^ 4 + 2 * (3^2) + 1
109 = 3^4 + 3^3 + 3^0
117 = 3^4 + 3^2 + 3^1
141 = 3 ^4 + 2* (3^3) + 2 * 3
which model is right ? or all right ?
Edited by author 07.08.2008 08:27 The models of 100 and 141 are wrong.
The other two ones are right. the sum of exactly three integer degrees of number 3,
why are models of 100 and 141 wrong?
who can tell me why ?
Edited by author 09.08.2008 22:57
Edited by author 09.08.2008 22:57 because the problem told us to do so 100 = 3^4 + 2 * (3^2) + 1
141 = 3^4 + 2 * (3^3) + 2 * 3
This ones are incorrect because
when you miltiply one of the degree by 2 It becomes
100 = 3^4 + 3^2 + 3^2 + 1
141 = 3^4 + 3^3 + 3^3 + 3 + 3
so, it's sums of 4 and 5 degees, not 3. Besides, it are to be different.
Edited by author 26.08.2008 13:13 thanks a lot, the qustions perplex me a long time, thank you |
| Can this problem be solved WITHOUT long arithmetics? (-) | elmariachi1414 (TNU) | 1407. One-two, One-two | 27 Aug 2008 01:36 | 1 |
|
| Problem in Java | Rizwan Ahmed | 1001. Reverse Root | 26 Aug 2008 21:37 | 4 |
I don't know that where to end Input Stream? My source code is below.
import java.util.Scanner;
import java.io.PrintWriter;
public class Program
{
public static void main(String args[]) throws Exception
{
Scanner in = new Scanner(System.in);
PrintWriter out = new PrintWriter
(System.out);
double numbers[] = new double[100000];
int i =0;
double result = 0.0;
while(in.hasNext())
{
numbers[i++] = in.nextDouble();
}
i = i -1;
while(i >= 0)
{
result = Math.sqrt(numbers[i]);
out.println(result);
i = i-1;
}
out.flush();
}
}
The first while loop is executing infinite time.
Problem no in Java.you write code correct but.Java have Thread class and it's to crawl all over code.
Edited by author 14.08.2008 14:42
Edited by author 14.08.2008 14:46 If no decides write form
Edited by author 14.08.2008 21:52 Thread? This is no working: (Потоки? Это всеравно не работает)
import java.util.*;
import java.io.*;
public class BaseClass extends Thread{
public static Scanner in;
private static void next() throws IOException{
if(in.hasNext()){
double t=in.nextDouble();
next();
double n=(double) Math.sqrt(t);
System.out.printf("%.4f\n", new Float(n));
}
}
public void run(){
in=new Scanner(System.in);
try {
next();
} catch (IOException e) {
e.printStackTrace();
}
}
public static void main(String[] args) throws Exception{
BaseClass t=new BaseClass();
t.start();
}
}
But, if i reading data from file (in=new Scanner(new FileInputStream("in.txt"));) - this working.(но когда я читаю из файла, программа работеат отлично) |
| Why WA#8 | Ivanidze | 1484. Film Rating | 26 Aug 2008 16:34 | 9 |
I use formula, i use binary search, i use linear search, and always got WA#8. search cin>>x>>y>>n; double X=(int)((x+0.05)*n); double Y=y+0.05; while (X/n>=x+0.05) X--; int ans=0; while (((double)(ans+X)/(ans+n))>=y+0.05 )ans++; cout<<ans; i'm going crazy: why it's not work?? Edited by author 08.10.2006 00:50Ha-ha!
I've solved it!!!!
I think that you don't need to use binary search because of your formula is almost right, but it's ALMOST...
I've had WA #8 too.. and I find out that's wrong in my solution in this test. I use only mathematic formulas.
If you buy me beer in Rybinsk I told you what's wrong... But now... ;) i'm waitin' for some beer... I buy you beer in any case in Rybinsk. Give me test case where are i'm wrong. If x=10.0 then we shouldn't increase it right? Ivan, I think that Georgy Kerensky is right!
when x is 10.0 then your double X must be equal to (int)(x*n) because of there is simple average 10.05 can't be!
Also, I think that this inequality [ (ans+X)/(ans+n))>=y+0.05 ] you must solve in integer numbers...
When I write in this way I'd got WA in different tests. But when this condition became to integer comparison I've got Accepted program...
Here some test cases for testing your decision:
10 1 1000000 -> 179000001
10 1 1 -> 180 (not 179!)
10 7.7 123456 -> 41153
also try to testing your program in different tests from this forume... i've got AC!!! all problem in small bug whith precision. We cannot use :
while (((ans+X)/(ans+n))>=y+0.05 )ans++;
but we can use:
while (((ans+X)/(ans+n))>=y+0.0499999999999 )ans++;
and
if (x!=10.0){
X=(int)((x+0.05)*n);
while (X/n>=x+0.049999999999) X--;
}
else
{
X=x*n;
} Thanks man! At last I got AC. I just rewrited the same idea by searching X in your terms, 'cause I am writing in pascal and this ancient tool doesn't know how to use Trunc or division:( unfortunately, for example while division instead of 179.00000 it gets 178.999898989 and so on with such things and in watch writes 179, and trunc gives 178 so it is very very interesting:)
alright thanks friends again
Maxim, thank you for you tests! :)
To all:
The problem can be solved without any search and without any floating-point arithmetics (but with int64 for safety). Just use these geneal rules for integer fractions:
b>0:
floor(a/b) = a>=0 ? a/b : -ceil(-a,b)
ceil(a/b) = a>=0 ? (a+b-1)/b : -floor(-a, b)
a>=0, b>0:
round(a/b) = a/b + ((a%b)*2>=b ? 1 : 0)
here / is integer division. % is remainder. X?A:B evaluates to 'A' if 'X' is true, evaluates to 'B' otherwise
max x: x <= a/b ------> x = floor(a/b)
max x: x < a/b ------> x = floor((a-1)/b)
min x: x >= a/b ------> x = ceil(a/b)
min x: x > a/b ------> x = ceil((a+1)/b)
E.g. to find maximal initial nominator in general case we have to solve the inequality: A/N < (X*100+5)/100, A->MAX
Edited by author 26.08.2008 16:48 |
| must be 90 | MSU_Sigma | 1484. Film Rating | 26 Aug 2008 16:14 | 3 |
max balls for 9.5 by 12 mans - 114, so (114 + p)/(12+p)>=2 => p >= 90 You the fool do not consider under the formula the blockhead It should not be <=2, it should be <2.05
Edited by author 26.08.2008 16:14 |
| Anyone can help me! | nimda | 1041. Nikifor | 26 Aug 2008 15:01 | 2 |
I got WA on test 3
!
Some one can send me a testdata.
thx!
Email:31898890@qq.com Output 0 if number of vectors purchased is <n |
| TLE on test case 8 | tryit1 | 1318. Logarithm | 26 Aug 2008 12:36 | 1 |
my algo was store double for table[4]=log10{ 2^96,2^64,2^32,0}
in table.
arr[i][4],arr[j][4]
i from 1 to n
j from i+1 to n
k from 0 to 4
{
a=arr[i][k],barr[j][k]
if(!a)
sum+= floor( log10(a) + table[k]),break;
}
This gets TLE on case 8 can someone tell me better algorithm or test cases. |
| Please help me!!! | WinAsAlways | 1230. Introspective Program | 26 Aug 2008 12:04 | 2 |
thanx a lot
Edited by author 19.04.2010 08:32 It failed because the invalid definition of B.
You can't use a " between a pair of ", but only between a pair of '.
So you can change it to : B='"'.
But this cause another bug, for you must output triple B in A.
So, try to add a new variable C, C="'",
and change the program a bit, and you will get AC.
Good luck~ |
| Help!!!! | Rudolf | 1478. Spy Satellites | 26 Aug 2008 04:57 | 2 |
The answer for test
4
1 1
1 4
1 7
1 8
will be
1111
or
1011
??????????? 1011
Distance must be strictly less |
| sad | pisyn | 1091. Tmutarakan Exams | 26 Aug 2008 00:23 | 1 |
sad pisyn 26 Aug 2008 00:23 svd
Edited by author 26.08.2008 17:51 |
| No subject | Denis Koshman | 1419. Maps of the Island Worlds | 25 Aug 2008 23:28 | 1 |
Edited by author 25.08.2008 23:29 |
| Can someone explain? I don't understand the notion of aliquot. | xerxe | 1046. Geometrical Dreams | 25 Aug 2008 21:45 | 2 |
Actually, the whole second paragraph doesn't make sense for me, as I don't know what aliquot means(in this context).
[quote]The set of angles ai satisfies a condition that the sum of angles in any of its nonempty subsets is not aliquot to 360 degrees.[/quote]
I search for the word aliquot, and found something like "part of something" and "divisor". But I'm not sure how these would make sense here. Any clarifications are welcome.
Thanks X is "aliqot Y" if there exists such ineger K satisfying equation X = K * Y, I suppose |
| need help! | Dmitry "Logam" Kobelev [TSOGU] | 1231. Turing: One, Two, Three, … | 25 Aug 2008 21:25 | 3 |
need help! Dmitry "Logam" Kobelev [TSOGU] 18 Jul 2008 13:55 Besides bugs, I had WA1 because I forgot to put number of rows in the output :) Unfortunetely, it's not the case( |
| Hint | Denis Koshman | 1269. Obscene Words Filter | 25 Aug 2008 19:59 | 1 |
Hint Denis Koshman 25 Aug 2008 19:59 KMP prefix function can be applied to character trees too. |
