OJ Board

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?

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

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

never mind, i got it

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?

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

Kristoffer Hansen

I cannot find one.Can u help me?

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: and then use a Dynamic Programming-esque lookup table to precalc the values, you should be fine.

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.

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!

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!

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

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

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

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