Page 1 of 3

### 11571 - Simple Equations - Extreme!!

Posted: Sat Dec 27, 2008 10:47 pm
i used long double to get AC . Lots of precision problems and EPS = 1e-12.

Code: Select all

``````4
350000055 750000012500000000 92500003000002525
790001541 1827015957846402603 498101288421155771
1 1 4
56 63 33

AC output.
50 50000000 300000005
29 90000679 700000833
No solution.
No solution.

Input
10
1 9603 19211
1 19008 19021
1 9408 18821
2 9504 19018
1 28215 18835
1 18620 18633
2 18810 18830
1 9215 18435
2 9310 18630

AC output

-97 -1 99
-96 -2 99
-96 -1 98
-96 -1 99
-95 -3 99
-95 -2 98
-95 -2 99
-95 -1 97
-95 -1 98
-95 -1 99
``````

### Re: 11571 Simple Equations - Extreme!!

Posted: Sun Dec 28, 2008 2:26 am
Thank you so much.

### Re: 11571 Simple Equations - Extreme!!

Posted: Sun Dec 28, 2008 11:16 pm
I solved "Simple Equations" using brute force method. That solution will certainly get TLE for this problem. Can anyone give some hints please?

### Re: 11571 Simple Equations - Extreme!!

Posted: Mon Dec 29, 2008 8:58 pm
Hint 1: xyz = B. So, if |x| is smaller than |y| and |z|, then |x^3| <= B.
Hint 2: x is a divisor of B.

Btw I haven't got accepted yet. Getting WA. So far, I haven't found any bug. I am not using any floating point arithmetic. For finding square/cubic root I am using binary search.

### Re: 11571 - Simple Equations - Extreme!!

Posted: Tue Dec 30, 2008 1:26 am
Jan wrote: Btw I haven't got accepted yet. Getting WA. So far, I haven't found any bug. I am not using any floating point arithmetic. For finding square/cubic root I am using binary search.
Couldn't that be an overflow error? Does that code get AC for the easy version?

### Re: 11571 - Simple Equations - Extreme!!

Posted: Tue Dec 30, 2008 1:31 am
Yeah, I have got accepted for the easy version. Here is my code...

Code: Select all

``````Accepted..
``````
I cant find any overflow. If you find anything, please let me know. Thanks in advance.

### Re: 11571 - Simple Equations - Extreme!!

Posted: Tue Dec 30, 2008 2:45 am
For large numbers your code sometimes doesn't find the solution. Here are 5 such example:

Code: Select all

``````5
2387162575 717973329951426968 5698749207640446741
2237352967 4503748340026097400 5003636701648133909
2297417884 3760073721300737960 5277585283697652330
2289936967 3843198163089955800 5244186565713749245
2223913532 3690224662037965920 4946159590427260520
``````
But my AC code returns by:

Code: Select all

``````-33854 -8884 2387205313
4305 467690 2236880972
15995 102328 2297299561
-41091 -40842 2290018900
-48722 -34056 2223996310
``````

### Re: 11571 - Simple Equations - Extreme!!

Posted: Tue Dec 30, 2008 3:36 am
A Hint:
(a + b + c)^2 = a^2 + b^2 + c^2 + 2(xy + yz + zx)

At least my solution uses it. And yes, then the biggest trouble is the precision.

### Re: 11571 - Simple Equations - Extreme!!

Posted: Tue Dec 30, 2008 8:27 am
Jan, you have got overflow problem.

your A^2 -4*B can overshoot 2^31*2^31 .
If your B is negative .

Now you have high as INT_MAX ie 2^31 -1 , so high^2 < 2^62 < 6*10^18 . take high as 1LL<<32 and mid as unsigned long long , i got correct answers for the robert's question.

Anyone care to help me with
http://acm.uva.es/board/viewtopic.php?f ... d04#p99255
?

### Re: 11571 - Simple Equations - Extreme!!

Posted: Tue Dec 30, 2008 12:17 pm
Thanks Robert Gerbicz and, tryit1. Got accepted. Just handled the overflow carefully .

### Re: 11571 - Simple Equations - Extreme!!

Posted: Thu Jan 01, 2009 11:56 am
I have tried to tackle this problem but I am getting WA. I have passed the given input in this thread. here is my code:

Code: Select all

``````#include <iostream>
#include <cmath>
using namespace std;

main() {
int n;
long double a, b, c, x, y, z;
long double p, q, d, u, v, phi, e, e1;

double pi = acos(-1.0);

cin >> n;
for (int i=0; i<n; i++) {
cin >> a >> b >> c;
p=(a*a-3*c)/6.0;
q=(5*a*a*a-9*a*c-54*b)/54.0;
d=p*p*p/27.0+q*q/4;
//  cout << "P=" << p << ";Q=" << q << ";D=" << d << endl;
if (d<0) {
phi=acos(-1.0*q/2.0/sqrt(fabs(p*p*p)/27.0));
e1=2*sqrt(fabs(p)/3)*cos(phi/3.0);
e = e1;

e1=-2*sqrt(fabs(p)/3)*cos((phi+pi)/3.0);
if (e > e1)
e = e1;

e1=-2*sqrt(fabs(p)/3)*cos((phi-pi)/3.0);
if (e > e1)
e = e1;
}
else if (d == 0) {
u = pow((-q/2 + sqrt(d)), (long double)1.0/3.0);
v = pow((-q/2 - sqrt(d)), (long double)1.0/3.0);
e1 = u + v;
e = e1;
e1 = (u + v) / -2.0;
if (e > e1)
e = e1;
}
else {
u = pow((-q/2 + sqrt(d)), (long double)1.0/3.0);
v = pow((-q/2 - sqrt(d)), (long double)1.0/3.0);
e = u + v;
}

x = e + a / 3.0;
u = a - x;
v = b / x;
y = (u - sqrt(u*u-4*v))/2.0;
z = (u + sqrt(u*u-4*v))/2.0;

//   cout << endl << "A=" << a << ";B=" << b << ";C=" << c << endl;
//   cout << "R=" << (x - round(x) + y - round(y) + z - round(z)) << endl;
if (isnan(y) || isnan(z) || x == y || y == z)
cout << "No solution." << endl;
else if (fabs(x - round(x) + y - round(y) + z - round(z)) > pow(10.0,-7.0))
cout << "No solution." << endl;
else
printf("%.0Lf %.0Lf %.0Lf\n", x, y, z);
}

return 0;
}
``````
Could somebody give some critical inputs that my code may fail? Thanks.

### Re: 11571 - Simple Equations - Extreme!!

Posted: Mon Feb 16, 2009 1:06 am
Some more I/O from an ACC program.

I think the trick in this problem (apart from the precision problems)
is to print 'No solution' even when we have a solution but the roots x,y,z are not
three different integer numbers (maybe most people overlook the 'different' part).

So for example, (1,1,1) is not a solution.
Another example, (1,1,2) is also not a solution.

Code: Select all

``````5
3 1 3
3000000 1000000000000000000 3000000000000
5700000 3468000000000000000 14810000000000
300006 1000060001100006 30001200017
300006 1000060001100006 30001200014``````

Code: Select all

``````No solution.
No solution.
600000 1700000 3400000
No solution.
100001 100002 100003``````
Hope these notes will be of some use to other
people still trying to solve the problem.

### Re: 102

Posted: Sun Oct 11, 2009 9:15 pm
thank i get my fault .

### Re: 102

Posted: Sun Oct 11, 2009 9:36 pm
which come first

GCB or CGB

### 102

Posted: Fri Jan 08, 2010 2:54 am
Hi
I solved this problem , but it's WA
I don't know why could anyone help me ?
my code :

Code: Select all

``````#include<iostream>
#include<string>
#include<fstream>
using namespace std ;
fstream fin("IN.txt");
int main()
{
int bin1 , bin2 , bin3 ;
string result ;
while(fin>>bin1)
{
int max = 0 ;
int sum=bin1 ;
for(int i=1; i<3 ; i++)
{
fin>>bin1[i] ;
sum+=bin1[i];
}
for(int i=0; i<3 ; i++)
{
fin>>bin2[i] ;
sum+=bin2[i];
}
for(int i=0; i<3 ; i++)
{
fin>>bin3[i] ;
sum+=bin3[i];
}
for(int i=0 ;i<3 ; i++)
{
for(int z=0 ; z<3 ; z++)
{
for(int j=0 ; j<3 ; j++)
{
if(i!=j && i!=z && j!=z)
{
int s = bin1[i]+bin2[j]+bin3[z] ;
if(s>max)
{
max = s ;
if(i==0 && j==2 && z==1)
result = "BCG" ;
else if(i==0 && j==1 && z==2)
result = "BGC" ;
else if(i==2 && j==0 && z==1)
result = "CBG" ;
else if(i==2 && j==1 && z==0)
result = "CGB" ;
else if(i==1 && j==0 && z==2)
result = "GBC" ;
else if(i==1 && j==2 && z==0)
result = "GCB" ;
}
}
}
}
}
cout<<result<<" "<<sum-max<<endl;
}
return 0 ;
}``````