## 256 - Quirksome Squares

Moderator: Board moderators

hs
New poster
Posts: 5
Joined: Mon Nov 05, 2001 2:00 am
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

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?

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.

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
Problemsetter
Posts: 107
Joined: Fri Oct 26, 2001 2:00 am
Contact:

### MAXINT is not 32767

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:
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 ?

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
Learning poster
Posts: 94
Joined: Wed Jul 31, 2002 12:44 pm
Contact:
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
Istiaque Ahmed [the LA-Z-BOy]

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

### is everyone uses precalculate??

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:
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
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 ?

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:
Just precalc them with brute force..

Julien Cornebise
Experienced poster
Posts: 145
Joined: Sat Feb 23, 2002 2:00 am
Location: Paris, France
Contact:
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

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