UVa 10341

From Algorithmist
Jump to navigation Jump to search

10341 - Solve It[edit]

Summary[edit]

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[edit]

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[edit]

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

Implementations[edit]

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[edit]

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

Output[edit]

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