## 138 - Street Numbers

Moderator: Board moderators

nghiank
New poster
Posts: 31
Joined: Wed Nov 20, 2002 3:10 pm
Contact:
test
Last edited by nghiank on Sun Apr 22, 2007 3:36 pm, edited 1 time in total.

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
If you try to optimize this method (I made that, but I cannot remember how exactly ...) you can got Accepted in less than 0.5 sec on OJ. I got time 0.36 sec ....

Regards
Dominik

nghiank
New poster
Posts: 31
Joined: Wed Nov 20, 2002 3:10 pm
Contact:
test

brentgood
New poster
Posts: 1
Joined: Tue Jun 17, 2003 7:14 am

### 138:Street numbers

Did anyone use D.P. to solve this problem?

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
Well...

As you may know, the output consists of a few lines only, so most people use "precalc" (aka hard-code) .

Of course, there are many other ways to solve this problem, e.g. seeing the pattern .
I applied brute force + a little bound and got accepted in less than 0.1 sec!

P.S. For your interest, the 10th line contains TWO 8-DIGIT no.
Last edited by Observer on Tue Jun 17, 2003 9:25 am, edited 2 times in total.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

Hisoka
Experienced poster
Posts: 120
Joined: Wed Mar 05, 2003 10:40 am
Location: Indonesia
I solve this problem with brute force. but I do something for optimize my brute force. I search begin at 1, after this if I got a answer, I multiply that with 4 to start search next answer again. with this way I got AC, without precalc.

I got that from my observation, with my first code when that code give me answer more than 1 minute. and in my computer, I cannot see 10th answer when I solve this problem.

bye....

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
in fact, to speed up more your code (I use the same way) you can use factor 5 (or 5,8 I don't remember correct).

Best regards
DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

ickychina
New poster
Posts: 1
Joined: Wed Jun 11, 2003 5:24 am
Last edited by ickychina on Sun Sep 21, 2003 4:37 pm, edited 1 time in total.

Rav
New poster
Posts: 27
Joined: Sat Jun 14, 2003 1:00 pm
Location: Polska Wroc&#322;aw
could someone tells me why OJ gives WA for this code ?
[cpp]
#include <stdio.h>
#include <math.h>

int main()
{
int ilosc;
long int l1,il2;
long double pier,l2;
l2=2;
ilosc=0;
while (ilosc<10)
{
pier=sqrt(l2/2*(l2+1));
l1=(long int)(pier);
if (l1==pier)
{
il2=(long int)(l2);
printf("%10Ld%10Ld\n",l1,il2);
++ilosc;
}
++l2;
}
}
[/cpp]
Rafał Sokołowski

Zhao Le
Learning poster
Posts: 80
Joined: Mon May 05, 2003 4:09 am
Location: Shanghai,China

### I have tested your code.

I have compared your output with my AC output.

All output is right.

So I submit, but the result is not WA, but TLE, so you'd better think

it over again, find the quicker soultion.

Good Luck.
AC makes me feels good,
But WA makes me thinks hard.

Rav
New poster
Posts: 27
Joined: Sat Jun 14, 2003 1:00 pm
Location: Polska Wroc&#322;aw
ok thanks
if output is good then i can speed it up(not just by sending table). but when i send it first time it was TE (i tetsed on my computer was 10-11s) then i send socend time and get WA. whanever thanks. i will be have AC soon.
Best Regards
Rafał Sokołowski

Rav
New poster
Posts: 27
Joined: Sat Jun 14, 2003 1:00 pm
Location: Polska Wroc&#322;aw
after speeding up(only in if i do l2*=4; that what hisoka said )i sended this aggain and got WA. strang
1744233 2003/07/24 05:24:21.109 Wrong Answer 0:07.117 396 32286 C++ 138 - Street Numbers

there is mys econd code:
[cpp]

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

using namespace std;

int main()
{
int ilosc;
long int l1,il2;
long double pier,l2;
l2=2;
ilosc=0;
while (ilosc<10)
{
pier=sqrt(l2/2*(l2+1));
l1=(long int)(pier);
if (l1==pier)
{
il2=(long int)(l2);
printf("%10Ld%10Ld\n",l1,il2);
++ilosc;
l2*=4;
}
++l2;
}
}
[/cpp]
Rafał Sokołowski

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:
i think, as far as i remember this is a problem where one goes from 1 to a house and from the last house to that house ...
if yes, then, just pregenerate the values or you can derive a formula that can be used very easyly.
i got ac in 0.00 s in both the process.
if not, then sorry.
"Everything should be made simple, but not always simpler"

Zhao Le
Learning poster
Posts: 80
Joined: Mon May 05, 2003 4:09 am
Location: Shanghai,China

### 138

I don't know really, but seems all is right compared with my output.

I sumbitted it to the online judge, suprised to see WA.

I cannot help anymore.
AC makes me feels good,
But WA makes me thinks hard.

bugzpodder
Experienced poster
Posts: 147
Joined: Fri Jun 13, 2003 10:46 pm
This is just an application of Pell's equation. you require no precalculation and you can generate the answers immediately