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

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

Post by nghiank » Wed Jan 29, 2003 8:29 am

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:

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
New poster
Posts: 31
Joined: Wed Nov 20, 2002 3:10 pm
Contact:

Post by nghiank » Thu Jan 30, 2003 1:26 pm

test

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

138:Street numbers

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

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

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

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) :P :P .

Of course, there are many other ways to solve this problem, e.g. seeing the pattern :roll: :roll: .
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

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. :oops:

bye.... :)

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by 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
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

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

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ław

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]
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.

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.
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

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
Rafał Sokołowski

Rav
New poster
Posts: 27
Joined: Sat Jun 14, 2003 1:00 pm
Location: Polska Wroc&#322;aw

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]
Rafał Sokołowski

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

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.
:oops:
"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

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.
AC makes me feels good,
But WA makes me thinks hard.

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

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

Post Reply

Return to “Volume 1 (100-199)”