962 - Taxicab Numbers

[zubi]

Hey, this is the first question i attempted *properly* in online judge.. im gettin time limit exceeded.. any hints?time showed 10.035 seconds..

Code: Select all

#include<iostream>
//#include<stdlib.h>

using namespace std;

main()
{

long x,y;
int i,j,l;
int count=0;
int balls=0;

while(cin>>x>>y)
{  balls=0;
   for(i=x;i<x+y;i++)
   {
   count=0;
     for(j=1;j<=sqrt((float)i);j++)
     
         for(l=1;j*j*j+l*l*l<=i;l++)
         {

         if(j*j*j+l*l*l==i)
               {
               count++;

               if(count==3)
              {cout<<i<<endl;balls++;}
               }


        }

     }

 if(balls==0)
 cout<<"None\n";

}
    //  system("pause");
}

[Jan]

Precalculate the numbers, then take input and print according to the input.

[zubi]

i didnot understand, could you elaborate a little bit. What do you mean

thanks for the reply..

[Jan]

First calculate all the taxicab numbers and store them in an array. Then take input and print the taxicab numbers in the range from the array. Got it ?

[zubi]

here, i have calculated taxicab numbers btwn the ranges

u say calculate the taxicab numbers ... till what point do u want me to calculate?

in any case wont it come time limited exceeded anywyas?

[Jan]

Check the case

Input:

Code: Select all

1000000000
100000

Output:

Code: Select all

None

Your code fails, and takes a lot of time.

I was talking about the highest range which is 1000000000 + 100000, now calculate all the taxicab numbers between 1 and (1000000000 + 100000) and save them in an array.

Suppose the input is 500 1000, then just find a number greater than or equal to 500 (in the array), and then print until the number in the array is not greater than 500 + 1000 or if you reach the end of the array.

To be more specific, let X1, X2, X3, ... , Xn be all the taxicab numbers from 1 to (1000000000 + 100000). You have stored them all in an array named T[]. Now suppose the input is X7 and 100. Then find X7 in the array, then start printing from X7 to all in the range.

Hope these help.

[kgrant]

Hi, I am doing the obvious precomputation then listing the cab numbers from the given range, but I am getting WA.

Edit: I found my silly problem, I was double counting numbers when there was > 2 ways to make it. For example 87539319 = 167^3 + 436^3 = 228^3 + 423^3 = 255^3 + 414^3.

[hamedv]

How many Taxicab Numbers is in range [1, 1001000000]?

[Jan]

How many Taxicab Numbers is in range [1, 1001000000]?

1554.

[mukeshtiwari]

within how much time we can generate all the numbers in the range [1, 1001000000] . my program is taking too much time almost in hours . suggestion will be helpful.

[Jan]

I dont know how did you implement it. My code takes less than 1 second to calculate all the numbers. I think you should describe your idea.

[lovemagic]

u can solve it without precalculation.
but remember,u have to fix the upper & lower bound carefully.

[mukeshtiwari]

hello everybody sorry for late reply .

first i stored cubes of all the numbers from 1 to 1011 in array of cube. then for each value from lowerlimit to lowerlimit+range , i iterated through a loop and calculate v=i-j^3 and using binary search i searched this value(v) in array cube . if it is there then v is perfect cube otherwise not . if successful increment counter . and if counter >=2 it means it can be expressed as sum of two cubes. here is my implimenatation .thnkx

Code: Select all

#include<cstdio>
#include<cmath>
	
	int cube[1101];
		
	int binary(int val,int low,int high)
		{	
			//printf("mukes");
			int mid;
			while(low<=high)
			 {
				mid=(low+high)/2;
				if(cube[mid]>val)
				 {
					high=mid-1;
				 }
				else if(cube[mid]<val)
					low=mid+1;
				else
					return mid;
			 }
			
			return 0;
		}
	/*int binary(int val,int low,int high)
		{
			int i;
			for(i=low;i<=high;i++)
				if(cube[i]==val)
					return i;
			return 0;
		}*/

	int main()
		{

			int i,l,r,j,v,count,k;
			for(i=0;i<=1011;i++)
			 	{
					cube[i]=i*i*i;
					//printf("%d %d\n",i,cube[i]);
				}
			while(scanf("%d",&l)!=EOF)
			   {

					scanf("%d",&r);
					for(i=l;i<=l+r;i++)
					 {
						count=-1;
						for(j=1;;j++)
						 {
							v=i-j*j*j;
							//printf("v=%d j^3=%d\n",v,j*j*j);
							k=binary(v,0,1011);
							if(k!=0)
							   {
								//printf("k=%d cube[%d]=%d\n",k,k,cube[k]);
								count++;
							   }
						 	if(count==2 || v<0)
								break;
							
						 }
						
						if(count==2)
							printf("%d\n",i);
					}
			 }
		}

[himanshu]

Judge gives me CE but my compiler doesn't

Code: Select all

#include<iostream>

using namespace std;

/* STORE THE OFFSETS OF CUBIC SUMS FROM n1 HERE */
int count[100001]; 

void find_sum_of_cubes(unsigned long int n1, unsigned long int rg)
{
	int i;	
	/* init the counter of combinations */
	for(i = 0; i < 100001; i++)
		count[i] = 0;

	for(i = 1; i <= 1000; i++)		
		for(int j = i+1; j <= 1000; j++)
		{
			unsigned long int index = i*i*i-n1+j*j*j;
			if(index >= 0 && index <= rg)
			{
				cout << i << '\t' << j << '\t' << index+n1 << endl;
				count[index]++;			
			}
		}
	bool found = false;
	for(unsigned long int i = 0; i <= rg; i++)
		if(count[i] > 1)
		{
			found = true;
			cout << n1+i << endl;
		}
	if(!found)
		cout << "None\n";
}
int main()
{	
	unsigned long int n1, rg;
	while(cin >> n1 >> rg)
		find_sum_of_cubes(n1, rg);				

	return 0;
}

Please help.

Thank You,
HG

[helloneo]

Well.. "count" variable is maybe pre-defined..
Try changing the name of the variable..