256  Quirksome Squares
Moderator: Board moderators

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

 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.
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;
}
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;
}
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
thus you're missing 3 output for 6, and 7 output for 8..
hope it helps

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

 Learning poster
 Posts: 94
 Joined: Wed Jul 31, 2002 12:44 pm
 Location: Dacca, Bangladesh
 Contact:
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 precalculate the answers first than make lookup table!!
This problem really brought up my curiosity. Please tell me if you can solve it without using precalculated table.
This problem really brought up my curiosity. Please tell me if you can solve it without using precalculated table.

 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:
Think about how this numbers are computed, and you see that exist easy way to get it
Best regards
DM
Look:
Code: Select all
869 0:00.010 64 Dominik Michniewski C 2000/02/2018:42:14.860 173949 (H0)
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)
Born from ashes  restarting counter of problems (800+ solved problems)

 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 !
Is there another solution than this too simple precalcuation ?
Could anybody help me to find a more interesting answer ? Is there one ?
Thank you !

 Experienced poster
 Posts: 145
 Joined: Sat Feb 23, 2002 2:00 am
 Location: Paris, France
 Contact:
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.
JeanBaptiste.
PS: i know next to nothing about number theory
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.
JeanBaptiste.
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