OJ Board

I have a simple recursive algorithm that brute-forces, trying to put each job either on machine1 or machine2. Since there are k jobs, this is O(2^k). I have the "optimization" of eliminating the job choice if either machine was previously in the required mode, which reduces the runtime to O(2^(m+n ...

Here's mine. I think the input does not follow the description 100%, so make sure you follow Brian's advice.
Input
1 1
9
9
1 2
5
3 6
1 3
9
1 9 0
1 4
9
7 3 3 2
2 4
6 6
5 3 5 3
10 17
0 1 2 3 4 5 6 7 8 9
7 7 7 5 5 3 3 3 3 3 2 2 2 2 2 2 2
1000
1000
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 ...

You are a genius! I modified my program the way you suggested and now I get Accepted. I wonder what the judges input really looks like. Should I mention it to the administrators in case other people are getting tripped up? Thanks again!
Jason Winokur

I think my code handles any integers for N and M. Should I terminate the program if either N or M is outside the [1..1000] range? Do I have to parse N and M as if they could contain commas, e.g. "1,000 1,000"? The problem description says that the input will end with a line containing two zeros. I ...

Thanks for the reply, but it still throws an exception parsing the input. Any other suggestions?

I am struggling to get my programming to read the input for this seemingly simple problem. Here is my Java code that throws an Exception while only trying to read the input. Are there any tricks to reading the input? Any insights would be much appreciated.


import java.io.*;
import java.util ...

That makes sense. Is it a good practice to add 1e-9 to every problem that requires a decimal answer? Thanks.

Thanks for the suggestion above to add 1e-9 to my answer before rounding to two decimal places. With that one change, I got AC instead of the many WA's I was getting. Why do we need to add 1e-9 and how did you figure that out?

Similar to what one & only pointed out, we can take advantage of cubic quadruples similar to pythagorean triples. The best quadruple that I have found is:

3 4 5 = 6 (exponents have been omitted for clarity)

This yields other quadrupals:
6 8 10 = 12
12 16 20 = 24
24 32 40 = 48
and so on, doubling ...

I have been getting WA and could use some test cases that help me debug my code. What should be the output for this:

76 93 23 8
737.8724003868243 318.3671073461939
807.7005524303653 616.132715881538
244.58125764410897 922.0838058729886
479.35074556549574 799.422385935254
581.4330401775208 890 ...

I have been testing my program, which uses dynamic programming, with the program above. My program is much slower but I get the same answers for hundreds of randomly generated input tests. Time is not the problem, since I have been getting Wrong Answer. Can somebody post some possibly tricky inputs.

Thanks for your help omega. Apparently, they want the smaller arc and chord length given an angle between satellites. They should have said so.

I am suprised that no one has atleast talked about this problem. I will be the first, since I had trouble with it and found no solice on this board. The algorithm I used is by no means the only algorithm or even the best, but I will try to give hints as to my approach. I got accepted after four ...

Why does that work? Why do we only need the remainder?

A little more help please.
My program gets the same answers for that input, but still WA.
Are there any other tricks or special input? Thanks.