256 - Quirksome Squares

[hs]

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]

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

[MAXX^FACTOR]

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;
}

[kmhasan]

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]

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

-turuthok-

[thechaoshacker]

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

[the LA-Z-BOy]

you got problem with one number when case is 8, check it . 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

[Nick]

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]

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

[Nick]

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]

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]

Just precalc them with brute force..

[Julien Cornebise]

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]

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

[epsilon0]

err sorry i was wrong... its not 19998 but 9999. i just coded that problem again last night