UVa 10341

Summary

Given an equation: f(x) = p*e-x + q*sin(x) + r*cos(x) + s*tan(x) + t*x2 + u = 0 and the values for p,q,r,s,t,u.

Find the value for x (if exists), where 0 <= x <= 1.

Explanation

The problem asks for the root of an equation. Since f is a non-increasing function on [0,1], it is sufficient to check the signs for f(0) and f(1) to determine whether there is a root in range [0,1]. There are at least three ways to find a root:

• The simplest is the Bisection method. It took ~32 ms to answer all the judge's input.
• A more effective way is the Secant method. It took ~20 ms to answer all the judge's input.
• The most effective way is the Newton's method. It took ~12 ms to answer all the judge's input and it only requires at most 5 iterations to find the root.

Gotchas

• Make sure that the root is computed with good precision (EPSILON <= 1e-7 is enough).

Implementations

The easiest to implement is the Bisection method:

#include <stdio.h>
#include <math.h>

#define EPS 1e-7

int p,q,r,s,t,u;

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

double bisection(){
double lo = 0, hi = 1;
while (lo + EPS < hi){
double x = (lo+hi)/2;
if (f(lo) * f(x) <= 0){
hi = x;
} else {
lo = x;
}
}
return (lo+hi)/2;
}

int main(){
while (scanf("%d %d %d %d %d %d",&p,&q,&r,&s,&t,&u)!=EOF){
if (f(0) * f(1) > 0){
puts("No solution");
} else {
printf("%.4lf\n", bisection());
}
}
}

A more effective root finding using Secant method:

double secant(){
if (f(0)==0) return 0;
for (double x0=0, x1=1; ; ){               // initial guess for x0 and x1
double d = f(x1)*(x1-x0)/(f(x1)-f(x0));  // compute delta
if (fabs(d) < EPS) return x1;            // the guess is accurate enough
x0 = x1;
x1 = x1 - d;
}
}

The most effective is the Newton's method:

double fd(double x){ // the derivative of function f
return -p*exp(-x) + q*cos(x) - r*sin(x) + s/(cos(x)*cos(x)) + 2*t*x;
}

double newton(){
if (f(0)==0) return 0;
for (double x=0.5; ;){             // initial guess x = 0.5
double x1 = x - f(x)/fd(x);      // x1 = next guess
if (fabs(x1-x) < EPS) return x;  // the guess is accurate enough
x = x1;
}
}

Input

0 0 0 0 -2 1
1 0 0 0 -1 2
1 -1 1 -1 -1 1
0 0 0 0 0 0
1 -20 3 -20 -5 6
2 -20 3 -20 -5 6
3 -20 3 -20 -5 6
4 -20 3 -20 -5 6
5 -20 3 -20 -5 6
6 -20 3 -20 -5 6
3 -4 1 -3 -2 5
6 -11 8 -20 -3 1
4 -4 4 -4 -4 5
17 -6 2 -8 -1 3
16 -1 12 -2 -12 4
4 -9 10 -2 -4 8
4 -15 19 0 -5 6
16 -1 9 -11 -14 18
11 -18 11 -7 -6 16
12 -3 1 -4 -18 19
12 -2 10 -3 -8 1
6 -15 11 -19 -7 -13
9 -7 10 0 -4 -1
15 -1 18 -8 -7 5
20 -6 6 -12 -18 -14
5 -5 3 -10 -15 -1
12 -15 18 -9 -4 -19
0 0 0 0 1 -1
0 0 0 0 -1 1

0.7071
No solution
0.7554
0.0000
0.2347
0.2521
0.2689
0.2850
0.3005
0.3154
0.7863
0.3807
0.8016
0.7628
No solution
No solution
No solution
0.9580
0.8911
0.9489
0.9074
0.0976
0.9066
0.9991
0.2879
0.2879
0.2879
1.0000
1.0000