256 - Quirksome Squares

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

Moderator: Board moderators

hs
New poster
Posts: 5
Joined: Mon Nov 05, 2001 2:00 am

Post by hs » Tue Nov 06, 2001 3:59 pm

Aren't this the quirksome numbers:

00
01
81
0000
0001
2025
3025
9801
000000
000001
088209
494209
998001
00000000
00000001
04941729
07441984
24502500
25502500
52881984
60481729
99980001

junjieliang
Experienced poster
Posts: 169
Joined: Wed Oct 31, 2001 2:00 am
Location: Singapore

Post by junjieliang » Wed Nov 07, 2001 3:23 pm

They are! Check your mailer's setting and try hardcoding the answers.

User avatar
MAXX^FACTOR
New poster
Posts: 7
Joined: Mon Sep 16, 2002 7:29 am
Location: EARTH.ASIA.TAIWAN.TAIPEI
Contact:

256..............another piece of cake?

Post by MAXX^FACTOR » Fri Oct 04, 2002 6:56 am

P256 Quirksome Squares
find the number with the following property:
3025=(30+25)^2
The number of digits may be 2,4,6 or 8. The maxint is only 32767 and numbers of eight digits are asked for.
Please note that the number of digits in the output is equal to the number in the corresponding input line : leading zeroes may not be suppressed.

My answer is listed bellow,
could anybody tell me why i got WA?

if( digit==2 ){
cout<<"00"<<endl;
cout<<"01"<<endl;
cout<<"81"<<endl;
}
if( digit==4 ){
cout<<"0000"<<endl;
cout<<"0001"<<endl;
cout<<"2025"<<endl;
cout<<"3025"<<endl;
cout<<"9801"<<endl;
}
if( digit==6 ){
cout<<"000000"<<endl;
cout<<"000001"<<endl;
}
if( digit==8 ){
cout<<"00000000"<<endl;
cout<<"00000001"<<endl;
}

User avatar
kmhasan
Problemsetter
Posts: 107
Joined: Fri Oct 26, 2001 2:00 am
Location: Canada
Contact:

MAXINT is not 32767

Post by kmhasan » Fri Oct 04, 2002 10:04 am

MAXINT is not 32767, int is 4 bytes in linux gcc
thus you're missing 3 output for 6, and 7 output for 8..

hope it helps

turuthok
Experienced poster
Posts: 193
Joined: Thu Sep 19, 2002 6:39 am
Location: Indonesia
Contact:

Post by turuthok » Fri Oct 04, 2002 10:04 am

Well, your pre-calculated list missed some quirksome numbers for digit 6 and 8. For instance, 494209 = (494 + 209)^2 ...

-turuthok-

thechaoshacker
New poster
Posts: 6
Joined: Wed Jan 22, 2003 9:19 pm
Contact:

WA ?

Post by thechaoshacker » Thu Jan 23, 2003 2:55 pm

Why am I getting WA ? Did I miss out any number ?
#include<stdio.h>

int ar[32000];

void f()
{
int a;
while(scanf("%d", &a)!=EOF)

switch(a)
{
case 2: printf("00\n01\n81\n"); break;
case 4: printf("0000\n0001\n2025\n3025\n9801\n");break;
case 6: printf("000000\n000001\n088209\n494209\n998001\n");break;
case 8: printf("00000000\n00000001\n04941729\n07441984\n24502500\n25502550\n52881984\n60481729\n99980001\n");break;
case 0:return;
default : printf("Wrong parameter\n");break;
}
}

void main()
{
f();
}
TheChaosHacker

User avatar
the LA-Z-BOy
Learning poster
Posts: 94
Joined: Wed Jul 31, 2002 12:44 pm
Location: Dacca, Bangladesh
Contact:

Post by the LA-Z-BOy » Sat Jan 25, 2003 6:44 am

you got problem with one number when case is 8, check it :wink:. if the problem persists please contact the program vendor... ooooooops please check your mailing prog. settings for long lines, or just spread one line into two or more.
greetings
Istiaque Ahmed [the LA-Z-BOy]

Nick
Learning poster
Posts: 53
Joined: Sun Jan 12, 2003 4:49 am

is everyone uses precalculate??

Post by Nick » Fri Aug 01, 2003 7:36 am

Hi, I wonder if anyone really has an algorithm that can find all the numbers in less than 10 seconds or so....or is everyone just pre-calculate the answers first than make look-up table!!

This problem really brought up my curiosity. Please tell me if you can solve it without using precalculated table.

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

Post by Dominik Michniewski » Fri Aug 01, 2003 7:57 am

I've done this problem without hardcoding answer in code
Look:

Code: Select all

869 0:00.010 64 Dominik Michniewski C 2000/02/20-18:42:14.860 173949   (H0)  
Think about how this numbers are computed, and you see that exist easy way to get it :)

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)

Nick
Learning poster
Posts: 53
Joined: Sun Jan 12, 2003 4:49 am

Post by Nick » Wed Aug 06, 2003 7:08 am

Thank you, Dominik!!

Now I know how to solve this problem. My solution still slow, there are many other that is better. But I believe that will be enough for this problem

Julien Cornebise
Experienced poster
Posts: 145
Joined: Sat Feb 23, 2002 2:00 am
Location: Paris, France
Contact:

Other solution than precalc ?

Post by Julien Cornebise » Fri Jul 16, 2004 12:17 pm

Hi everybody

Is there another solution than this too simple precalcuation ?
Could anybody help me to find a more interesting answer ? Is there one ?

Thank you !

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Fri Jul 16, 2004 5:59 pm

Just precalc them with brute force..

Julien Cornebise
Experienced poster
Posts: 145
Joined: Sat Feb 23, 2002 2:00 am
Location: Paris, France
Contact:

Post by Julien Cornebise » Tue Jul 20, 2004 11:49 pm

Okay, I just wondered if there happened to be some number theory behind it to avoid precalc (wich gets AC quite easily, compared to what number theory could be)... Doesn't seem to be, though. Thanks :)

epsilon0
Experienced poster
Posts: 112
Joined: Tue Nov 12, 2002 11:15 pm
Location: Paris, France.

NO NO NO

Post by epsilon0 » Mon Jul 26, 2004 8:41 pm

NO NO NO

precomputation is lame, and you may have noticed that NO problem here requires it.

about this one, i have lost my sources unfortunately, but i just remembered how i solved it. there is indeed a very easy and fast solution that doesnt require brute force.

or rather, yes, you might call it a brute force, although you only have to test 19998 possibilities for the 8 digits one. but its so fast that you dont have to precompute anything. maybe a few milliseconds ;)

just keep looking... i gave you a big hint.

Jean-Baptiste.

PS: i know next to nothing about number theory ;)
We never perform a computation ourselves, we just hitch a ride on the great Computation that is going on already. --Tomasso Toffoli

epsilon0
Experienced poster
Posts: 112
Joined: Tue Nov 12, 2002 11:15 pm
Location: Paris, France.

Post by epsilon0 » Tue Jul 27, 2004 2:11 pm

err sorry i was wrong... its not 19998 but 9999. i just coded that problem again last night
We never perform a computation ourselves, we just hitch a ride on the great Computation that is going on already. --Tomasso Toffoli

Post Reply

Return to “Volume 2 (200-299)”