Just another WordPress.com site

Solution Procedure :

         1 . A simple brute force approach is preferable for this problem .

         2 . Pre-calculation saves time .

Code :

#include<iostream>
using namespace std;

int main()
{
    int i,j,k,test,array[50000+1][3]={0},d;

    for(i=0;i*i<=50000;i++)
      for(j=i;i*i+j*j<=50000;j++)
          for(k=j;i*i+j*j+k*k<=50000;k++)
          {
             d = i*i+j*j+k*k;
             if(!array[d][0] && !array[d][1] && !array[d][2]){
                array[d][0]=i;
                array[d][1]=j;
                array[d][2]=k;
            }
         }

    cin>>test;
    for(i=1;i<=test;i++)
    {
         cin>>d;
         if( !array[d][0] && !array[d][1] && !array[d][2] )
            cout<<-1<<endl;
        else
            cout<<array[d][0]<<‘ ‘<<array[d][1]<<‘ ‘<<array[d][2]<<endl;
    }
    return 0;
}

 

Another Code:

 

#include<stdio.h>
#include<math.h>

#define MAX 50000

long A[MAX+7][3];
char Find[ MAX+7];

void Calc( void)
{
    long i,j,k,Sum =0;

    long Limit =(long)sqrt( MAX);
    for( i=0;i<=Limit;i++){
        Sum +=i*i;
        for( j=i;j<=Limit;j++){
            Sum +=j*j;
            for( k=j;k<=Limit;k++){
                Sum +=k*k;

                if( Sum>MAX){
                    Sum -=k*k;
                    break;
                }
                
                if( !Find[Sum]){
                    A[Sum][0] =i;
                    A[Sum][1] =j;
                    A[Sum][2] =k;
                    Find[Sum] =1;
                }
                Sum -=k*k;
            }
            if( Sum >MAX){
                Sum -=j*j;
                break;
            }
            else Sum -=j*j;
        }
        Sum -=i*i;
    }
}

int main( void)
{
    long N,Icase;

    scanf(“%ld”,&Icase);
    Calc();
    while( Icase–){
        scanf(“%ld”,&N);
        if( Find[N]) printf(“%ld %ld %ld\n”,A[N][0],A[N][1],A[N][2]);
        else printf(“-1\n”);
    }

    return 0;
}
        

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: