UVa OJ Board

:evil: I have been trying to debug my actually correct source code because of your incorrect output. Why do you post incorrect examples ?! Be more careful next time, because people actually read this stuff!! My AC Output is: -0.070885 0.393284 0.074244 -0.466908 0.106229 0.190366 0.132556 -0.007342 ...

So the formula A(i, j) = A(i, j-1) + A(i-j, j) works both for no of ways of making $i with coins of maximum value $j and no of ways of making $i with maximum j coins. Here are two different interpretation. For the first A(i, j) = A(i, j-1) + A(i-j, j) so A(i, j) is either the no. of ways to of makin...

I got ac, but my source code works for that kind of tests.
I'm sorry, I guess the cities could be numbered in a non-compact manner. (I misunderstood your question)

Sorry, that wouldnt work for negative numbers
Still, i got ac using double data type and an 1e-7 epsilon.

This is easier:
[c]
scanf("%d.%d", &a, &b);
x = (long long) (a * 1000 + b);
[/c]

Well, after i got ac, i tried to optimize something and i got TLE. I tried the program which got ac and it got TLE and i can't manage to make it work in time (even with only 1 miller test).
This is weird

Uhm.. yeah

I got AC with '0 rings'
I guess they changed the data..
[c]void print()
{
int i, max = 0;
for (i = 0; i < N; i++)
if (T == i && Nr > max)
max = Nr;
printf("The largest component contains %d ring", max);
if (max != 1) printf("s");
printf(".\n");
}
[/c]

I worked on the helper formulas given in the task and i came up with the following formula:

Sn = ((N-1)*N*(N+1)*(N+2) + 2*N*(N+1)) / 4
which is actually an uglier form of your formula

I got AC using big numbers.

In my solution, I use two lists for every street/avenue, one for each direction. For example s[1][0] tells me what should i change if i want s1 to go right, and s[1][1] to go left. For a pair s1,a1 - s2, a2, there are two possible routes. If the street/ave of one route will be chosen to be oriented ...

Well, i tried to solve the problem all day and finally (after a lot of attempts) i got ac. The problem is that UVA's new TL of 10 secs is very tight. (my time was 9.860) To speed-up the primality tests, I use an eratostene's sieve for numbers up to 50010000, and Miller-Rabin for larger numbers. Mill...

I like your idea, but there also is an algorithm (10x10)^3 precalc, O(10x10) solution, using Gauss-Jordan reduction mod 2. (XOR) You can create a system of linear equations mod 2. The matrix would be 100x100. Every line coresponds to an i,j in the configuration. For line 0, (the upper-left corner), ...