## Sunday, October 26, 2014

### UVa Problem 10341 - Solve it

Problem:

Solution:

Note that all the non-linear functions involved is monotonic increasing in $[0, 1]$. So all we have to do is to apply the method of bisection to solve the equation.

The not so trivial part is error bound. In order to be 4 decimal place accurate, the error between the estimate and the real solution can not be larger than 0.00005. Bisection can make sure the error go arbitrarily small. Since I am lazy, so I just run it 100 iterations, which make the error $2^{-100}$, way better than enough for the problem.

Code:

#include "stdafx.h"

// http://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=1282

#include <iostream>
#include <iomanip>
#include <cmath>

using namespace std;

double evaluate(int p, int q, int r, int s, int t, int u, double x)
{
return p * exp(-x) + q * sin(x) + r * cos(x) + s * tan(x) + t * x * x + u;
}

int UVa10341()
{
int p, q, r, s, t, u;
while (true)
{
cin >> p;
if (cin.eof())
{
break;
}
cin >> q;
cin >> r;
cin >> s;
cin >> t;
cin >> u;
double first = evaluate(p, q, r, s, t, u, 0);
double second = evaluate(p, q, r, s, t, u, 1);
if (first * second > 0)
{
cout << "No solution" << endl;
}
else
{
bool first_is_negative = first < 0;
double left = 0;
double right = 1;
int i = 0;
for (int i = 0; i < 100; i++) // way more than enough :)
{
double middle = (left + right) / 2;
double middle_result = evaluate(p, q, r, s, t, u, middle);
if (first_is_negative)
{
if (middle_result < 0)
{
left = middle;
}
else
{
right = middle;
}
}
else
{
if (middle_result < 0)
{
right = middle;
}
else
{
left = middle;
}
}
}
std::cout << std::setprecision(4) << std::fixed << left << endl;
}
}
return 0;
}