Page 1 of 2
962 - Taxicab Numbers
Posted: Sun Mar 25, 2007 5:51 pm
by 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");
}
Posted: Sun Mar 25, 2007 8:46 pm
by Jan
Precalculate the numbers, then take input and print according to the input.
Posted: Mon Mar 26, 2007 9:07 am
by zubi
i didnot understand, could you elaborate a little bit. What do you mean
thanks for the reply..
Posted: Mon Mar 26, 2007 8:23 pm
by 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 ?
Posted: Tue Mar 27, 2007 10:47 am
by 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?
Posted: Tue Mar 27, 2007 5:19 pm
by Jan
Check the case
Input:
Output:
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.
WA
Posted: Sun May 06, 2007 8:35 am
by 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.
Posted: Wed Aug 15, 2007 9:12 am
by hamedv
How many Taxicab Numbers is in range [1, 1001000000]?
Posted: Wed Aug 15, 2007 3:59 pm
by Jan
hamedv wrote:How many Taxicab Numbers is in range [1, 1001000000]?
1554.
Posted: Fri Sep 07, 2007 11:04 am
by 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.
Posted: Fri Sep 07, 2007 1:20 pm
by 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.
Posted: Sat Sep 08, 2007 2:19 am
by lovemagic
u can solve it without precalculation.
but remember,u have to fix the upper & lower bound carefully.
Posted: Mon Sep 10, 2007 4:57 am
by 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);
}
}
}
962 Compilation Error
Posted: Sat Oct 27, 2007 7:21 pm
by 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
Posted: Sun Oct 28, 2007 7:59 am
by helloneo
Well.. "count" variable is maybe pre-defined..
Try changing the name of the variable..
