962 - Taxicab Numbers

All about problems in Volume 9. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

zubi
New poster
Posts: 4
Joined: Sun Mar 25, 2007 5:49 pm

962 - Taxicab Numbers

Post by zubi » Sun Mar 25, 2007 5:51 pm

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
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Sun Mar 25, 2007 8:46 pm

Precalculate the numbers, then take input and print according to the input.
Ami ekhono shopno dekhi...
HomePage

zubi
New poster
Posts: 4
Joined: Sun Mar 25, 2007 5:49 pm

Post by zubi » Mon Mar 26, 2007 9:07 am

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

thanks for the reply..

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Mon Mar 26, 2007 8:23 pm

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 ?
Ami ekhono shopno dekhi...
HomePage

zubi
New poster
Posts: 4
Joined: Sun Mar 25, 2007 5:49 pm

Post by zubi » Tue Mar 27, 2007 10:47 am

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
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Tue Mar 27, 2007 5:19 pm

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.
Ami ekhono shopno dekhi...
HomePage

kgrant
New poster
Posts: 3
Joined: Tue Apr 10, 2007 9:56 pm

WA

Post by kgrant » Sun May 06, 2007 8:35 am

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
Learning poster
Posts: 98
Joined: Mon May 07, 2007 8:30 am

Post by hamedv » Wed Aug 15, 2007 9:12 am

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

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Wed Aug 15, 2007 3:59 pm

hamedv wrote:How many Taxicab Numbers is in range [1, 1001000000]?
1554.
Ami ekhono shopno dekhi...
HomePage

mukeshtiwari
Learning poster
Posts: 63
Joined: Tue Mar 07, 2006 6:51 pm
Location: india

Post by mukeshtiwari » Fri Sep 07, 2007 11:04 am

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
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Fri Sep 07, 2007 1:20 pm

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.
Ami ekhono shopno dekhi...
HomePage

lovemagic
Learning poster
Posts: 52
Joined: Thu Oct 02, 2003 11:38 am

Post by lovemagic » Sat Sep 08, 2007 2:19 am

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

mukeshtiwari
Learning poster
Posts: 63
Joined: Tue Mar 07, 2006 6:51 pm
Location: india

Post by mukeshtiwari » Mon Sep 10, 2007 4:57 am

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
New poster
Posts: 17
Joined: Mon May 15, 2006 12:24 pm
Location: Hyderabad, India
Contact:

962 Compilation Error

Post by himanshu » Sat Oct 27, 2007 7:21 pm

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
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Post by helloneo » Sun Oct 28, 2007 7:59 am

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

Post Reply

Return to “Volume 9 (900-999)”