11436 - Cubes - EXTREME!!!

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

Moderator: Board moderators

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

WA: 11436 - Cubes - EXTREME!!!

Post by naffi » Mon Oct 20, 2008 6:14 pm

I got AC.
Always At Your Help.

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

Re: 11436 - Cubes - EXTREME!!!

Post by bourne » Wed Dec 31, 2008 7:05 pm

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!!!

Post by MRH » Fri Jan 02, 2009 7:25 am

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
Location: SUST,SYLHET,BANGLADESH.
Contact:

Re: 11436 - Cubes - EXTREME!!!

Post by calicratis19 » Fri Aug 07, 2009 7:47 pm

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!!!

Post by m.shawkey » Thu Jun 13, 2013 2:13 pm

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!!!

Post by brianfry713 » Thu Jun 13, 2013 11:35 pm

Read this thread.
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!!!

Post by lighted » Sat Aug 02, 2014 11:43 pm

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

Post Reply

Return to “Volume 114 (11400-11499)”