11436 - Cubes - EXTREME!!!

[naffi]

I got AC.

[bourne]

I have tested a lot of test cases still I am getting WA. Can't find the bug.

Here's the code:

Code: Select all

#include<iostream>
#include<vector>
#include<string>
#include<queue>
#include<sstream>
#include<map>
#include<stack>
#include<set>
#include<cmath>
#include<iomanip>
using namespace std;
#define PB push_back
#define vi vector<int>
#define LL long long
#define all(v) v.begin(),v.end()
#define pii pair<int,int>
#define MP make_pair
#define INF 200000000

int main()
{
	while(1)
	{
		LL n,x,y;
		cin>>n;
		if(!n) break;
		vi div;
		for(int i=1;i<=50000;i++)
			if(n%i==0) div.PB(i);
		LL k;
		pii res=MP(INF,INF);
		for(int i=0;i<div.size();i++)
		{
			bool done=0;
			k=div[i];
			LL lo=1,hi=100000000,mid;
			while(lo<=hi)
			{
				mid=lo+(hi-lo)/2;
				LL m=k * ( k*k + 3*k*mid + 3*mid*mid );
				if(m==n){
					y=mid;
					done=1;
					break;
				}
				else if(m>n)
					hi=mid-1;
				else
					lo=mid+1;
			}
			x=k+y;
			if(done) res=min(res,MP((int)y,(int)x));
		}
		if(res.first==INF) 
			printf("No solution\n");
		else
			printf("%d %d\n",res.second,res.first);
	}
}

[MRH]

try this case:
input :
101
1000
10000000000
8888888888888
9999999999999
1000000099999
10987654321
99999998888887
my acc code gave:

No solution
No solution
No solution
No solution
No solution
No solution
No solution
No solution

[calicratis19]

Code: Select all

26
63

your code gives no solution to them both.

which should be

Code: Select all

3 1
4 1

hope it helps.

[m.shawkey]

what are the properties of the difference of the cubes that can help me solve this problem?

[brianfry713]

Read this thread.

[lighted]

For problem 11428 i got accepted just calculating square root of discriminant.

Code: Select all

q = sqrt(d);

But for problem 11436 my program didn't match sample.

For n = 2299304209293 square root of discriminant was q = 96713648 instead of 96713649.

It matched when i added eps value to sqrt.

Code: Select all

q = sqrt(d) + eps;