## 11436 - Cubes - EXTREME!!!

Moderator: Board moderators

naffi
New poster
Posts: 23
Joined: Wed Mar 19, 2008 12:25 pm
Contact:

### WA: 11436 - Cubes - EXTREME!!!

I got AC.

bourne
New poster
Posts: 11
Joined: Wed Jun 04, 2008 1:39 pm

### Re: 11436 - Cubes - EXTREME!!!

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
Learning poster
Posts: 51
Joined: Mon Aug 11, 2008 9:09 pm

### Re: 11436 - Cubes - EXTREME!!!

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
Learning poster
Posts: 76
Joined: Mon Jul 21, 2008 8:50 am
Contact:

### Re: 11436 - Cubes - EXTREME!!!

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.
Heal The World

m.shawkey
New poster
Posts: 9
Joined: Tue Jun 11, 2013 2:58 pm

### Re: 11436 - Cubes - EXTREME!!!

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

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 11436 - Cubes - EXTREME!!!

Check input and AC output for thousands of problems on uDebug!

lighted
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

### Re: 11436 - Cubes - EXTREME!!!

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;``
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman