138  Street Numbers
Moderator: Board moderators

 Guru
 Posts: 834
 Joined: Wed May 29, 2002 4:11 pm
 Location: Wroclaw, Poland
 Contact:
138:Street numbers
Did anyone use D.P. to solve this problem?
Well...
As you may know, the output consists of a few lines only, so most people use "precalc" (aka hardcode) .
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 8DIGIT no.
As you may know, the output consists of a few lines only, so most people use "precalc" (aka hardcode) .
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 8DIGIT 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
Date: December 31st, 2011 (Saturday)
Time: 12:00  16:00 (UTC)
URL: http://uva.onlinejudge.org
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....
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....

 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
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)
Born from ashes  restarting counter of problems (800+ solved problems)
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]
[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
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.
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.
But WA makes me thinks hard.
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]
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
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.
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"
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.
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.
But WA makes me thinks hard.

 Experienced poster
 Posts: 147
 Joined: Fri Jun 13, 2003 10:46 pm