138 - Street Numbers

All about problems in Volume 1. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
paulhryu
New poster
Posts: 45
Joined: Sat Jan 26, 2002 2:00 am
Contact:

Post by paulhryu » Sat Feb 02, 2002 9:48 pm

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

Post by Even » Sun Feb 03, 2002 8:52 am

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:

Post by paulhryu » Sun Feb 03, 2002 9:47 pm

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:

Post by paulhryu » Mon Feb 04, 2002 12:05 am

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?

Post by oker » Tue Apr 09, 2002 1:43 pm

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?

Post by arnsfelt » Tue Apr 09, 2002 2:12 pm

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?

Post by oker » Tue Apr 09, 2002 2:22 pm

I cannot find one.Can u help me?

C8H10N4O2
Experienced poster
Posts: 137
Joined: Wed Feb 27, 2002 2:00 am
Location: Pasadena, CA

Post by C8H10N4O2 » Sun Apr 14, 2002 6:46 pm

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:

Post by Stefan Pochmann » Mon Apr 15, 2002 3:55 am

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

Post by oker » Mon Apr 15, 2002 11:22 am

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:

Post by Stefan Pochmann » Tue Apr 16, 2002 2:21 am

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

Post by oker » Tue Apr 16, 2002 7:24 am

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:

Post by Stefan Pochmann » Tue Apr 16, 2002 7:39 am

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

Post by oker » Tue Apr 16, 2002 9:13 am

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

Stefan Pochmann
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:

Post by Stefan Pochmann » Wed Apr 17, 2002 2:15 am

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

Post Reply

Return to “Volume 1 (100-199)”