## 138 - Street Numbers

Moderator: Board moderators

paulhryu
New poster
Posts: 45
Joined: Sat Jan 26, 2002 2:00 am
Contact:
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
Learning poster
Posts: 75
Joined: Thu Nov 22, 2001 2:00 am
Location: Taiwan
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
New poster
Posts: 45
Joined: Sat Jan 26, 2002 2:00 am
Contact:
But I do divide, see, the (>> 1) divides by 2, or technically it does a bitwise shift, but why doesn't it work?

paulhryu
New poster
Posts: 45
Joined: Sat Jan 26, 2002 2:00 am
Contact:
never mind, i got it

oker
New poster
Posts: 16
Joined: Tue Apr 09, 2002 1:23 pm

### 138 Number Street - How to reduce the running time?

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
New poster
Posts: 44
Joined: Wed Oct 17, 2001 2:00 am
Location: Denmark
Contact:

### Re: 138 Number Street - How to reduce the running time?

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

Kristoffer Hansen

oker
New poster
Posts: 16
Joined: Tue Apr 09, 2002 1:23 pm

### I cannot find one.Can u help me?

I cannot find one.Can u help me?

C8H10N4O2
Experienced poster
Posts: 137
Joined: Wed Feb 27, 2002 2:00 am
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
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:
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
New poster
Posts: 16
Joined: Tue Apr 09, 2002 1:23 pm
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
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:
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
New poster
Posts: 16
Joined: Tue Apr 09, 2002 1:23 pm
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
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:
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
New poster
Posts: 16
Joined: Tue Apr 09, 2002 1:23 pm