138

Dominik Michniewski · Post by **Dominik Michniewski** » Wed Jan 29, 2003 8:56 am

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 · Post by **nghiank** » Thu Jan 30, 2003 1:26 pm

brentgood · Post by **brentgood** » Tue Jun 17, 2003 7:21 am

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

Observer · Post by **Observer** » Tue Jun 17, 2003 7:34 am

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.

Hisoka · Post by **Hisoka** » Tue Jun 17, 2003 9:09 am

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 · Tue Jun 17, 2003 12:15 pm

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

ickychina · Post by **ickychina** » Tue Jun 17, 2003 4:58 pm

Rav · Post by **Rav** » Wed Jul 23, 2003 7:52 pm

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]

Zhao Le · Post by **Zhao Le** » Thu Jul 24, 2003 1:59 am

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.

Rav · Post by **Rav** » Thu Jul 24, 2003 7:26 am

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

Rav · Post by **Rav** » Thu Jul 24, 2003 7:33 am

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]

anupam · Post by **anupam** » Thu Jul 24, 2003 8:17 am

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.

Zhao Le · Post by **Zhao Le** » Thu Jul 24, 2003 4:32 pm

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.

bugzpodder · Post by **bugzpodder** » Thu Jul 24, 2003 8:22 pm

This is just an application of Pell's equation. you require no precalculation and you can generate the answers immediately

OJ Board

138 - Street Numbers

138:Street numbers

I have tested your code.