138 - Street Numbers

[paulhryu]

My code is as follows:

// @BEGIN_OF_SOURCE_CODE

/* @JUDGE_ID: 17243NT 138 C++ "m^2 = n (n + 1) / 2" */

// Send to judge@uva.es

#include <stdio.h>
#include <math.h>

int main() {
int i = 0, m, n, tri;

for(n = 2; i < 10; n++) {
tri = (n * (n + 1)) >> 1;
m = sqrt(tri);
if(m * m == tri) {
printf("%10d%10dn", m, n);
i++;
}
}

return 0;
}

// @END_OF_SOURCE_CODE

I get:
6 8
35 49
204 288
1189 1681
6930 9800
256 131072
7742 131528
11707 132113
19813 134033
25162 135816

Is this wrong?

[Even]

you forget to divide 2...tri = n*(n+1)/2

and your method will cause TL...

and the last n will large than 60,00,000...

[paulhryu]

But I do divide, see, the (>> 1) divides by 2, or technically it does a bitwise shift, but why doesn't it work?

[paulhryu]

never mind, i got it

[oker]

I know the problem in fact is x^2+x=2y^2, but my program runs too slow. (I tried every x as 1,2,.....)

And I use "int64" in Free Pascal. Does it work on the judge system?

[arnsfelt]

Try to find an explicit solution to your diophantine equation.
It can be done in this case.

Kristoffer Hansen

[oker]

I cannot find one.Can u help me?

[C8H10N4O2]

If this were a math class, Diophantine equations would be the way to go. However, you are trying to solve a computing problem. When you brute force the Diophantine equation, you turn an elegant solution into a VERY VERY ugly one. Instead, try brute forcing the problem.

The problem asks a very simple thing. Add the left and the right house numbers. So, just do that:o) Why make it more complicated?

If you use the arithmetic progression formula:

Code: Select all

S=(A+B)*N/2;
where
S=sum of progression
A=first term
B=last term
N=number of terms

and then use a Dynamic Programming-esque lookup table to precalc the values, you should be fine.

[Stefan Pochmann]

oker: You can make it slightly faster by trying all y instead of all x. And 32 bit are enough. And how do you determine the y values?

And could someone who solved it please resubmit it? For some reason, my solutions don't get accepted anymore and I don't know why.

[oker]

I don't think it is enough by trying y either. I saw someone sloved it in math may -- just create a list of numbers: A(1)=0 , A(2)=1, and then A(n)=6*A(n-1)-A(n-2), and A(3)~A(12) are the first ten y's. This is extramely fast! But working out the formula was too hard!

[Stefan Pochmann]

Well, I don't know about Pascal, but in C++ it *is* enough. Runs in about 0.7 seconds. Unfortunately, I can't get it accepted anymore. Please could anybody resubmit his/her solution to see if it's only me? I get "Wrong Answer" even for my precalculated printf-solution that worked before!

[oker]

I have a correct output here, you can compare it with the output which your program makes:
6 8
35 49
204 288
1189 1681
6930 9800
40391 57121
235416 332928
1372105 1940449
7997214 11309768
46611179 65918160

(The output format is not as the problem demands.)

[Stefan Pochmann]

Very strange. I started my output with "1 1". I wonder how I could get that accepted (maybe I changed it afterwards?). Thanks a lot. Took 4.670 seconds now, though...

[oker]

Will you please show me your program? Thanks a lot!

[Stefan Pochmann]

Since I don't like to post full solutions here, I'll send it to you as a private message.