Search found 12 matches

by scythe
Tue Jul 15, 2003 8:15 am
Forum: Volume 105 (10500-10599)
Topic: 10524 - Matrix Reloaded
Replies: 41
Views: 4422

: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 ...
by scythe
Fri Oct 11, 2002 10:03 pm
Forum: Volume 103 (10300-10399)
Topic: 10313 - Pay the Price
Replies: 42
Views: 19373

Explanation

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...
by scythe
Wed Oct 09, 2002 5:09 pm
Forum: Volume 103 (10300-10399)
Topic: 10308 - Roads in the North
Replies: 30
Views: 9696

Ah, could be right

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)
by scythe
Wed Oct 09, 2002 5:06 pm
Forum: Volume 103 (10300-10399)
Topic: 10310 - Dog and Gopher
Replies: 47
Views: 17323

Sorry

Sorry, that wouldnt work for negative numbers
Still, i got ac using double data type and an 1e-7 epsilon.
by scythe
Tue Oct 08, 2002 5:07 pm
Forum: Volume 103 (10300-10399)
Topic: 10310 - Dog and Gopher
Replies: 47
Views: 17323

Re:

This is easier:
[c]
scanf("%d.%d", &a, &b);
x = (long long) (a * 1000 + b);
[/c]
by scythe
Tue Oct 08, 2002 7:31 am
Forum: Volume 103 (10300-10399)
Topic: 10311 - Goldbach and Euler
Replies: 98
Views: 23030

This problem is hell

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 :o
by scythe
Mon Oct 07, 2002 9:34 pm
Forum: Volume 103 (10300-10399)
Topic: 10308 - Roads in the North
Replies: 30
Views: 9696

Re:

Uhm.. yeah
by scythe
Mon Oct 07, 2002 9:30 pm
Forum: Volume 103 (10300-10399)
Topic: 10301 - Rings and Glue
Replies: 50
Views: 16260

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]
by scythe
Mon Oct 07, 2002 9:22 pm
Forum: Volume 103 (10300-10399)
Topic: 10302 - Summation of Polynomials
Replies: 29
Views: 15149

Formula using the question hints

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 :oops:

I got AC using big numbers.
by scythe
Mon Oct 07, 2002 9:06 pm
Forum: Volume 103 (10300-10399)
Topic: 10319 - Manhattan
Replies: 9
Views: 5728

Exponential solution worked in 0.01

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 ...
by scythe
Mon Oct 07, 2002 8:50 pm
Forum: Volume 103 (10300-10399)
Topic: 10311 - Goldbach and Euler
Replies: 98
Views: 23030

10 secs limit - a kiler

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...
by scythe
Mon Oct 07, 2002 12:30 pm
Forum: Volume 103 (10300-10399)
Topic: 10309 - Turn the Lights Off
Replies: 19
Views: 8795

Polynomial time algorithm

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), ...

Go to advanced search