1.
package acm_10341_solve_it;
/**
* FWP, Ausgew¦hlte Probleme aus dem ACM Programming Contest, SS10
* Problem: 10341 Solve it
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=15&page=show_problem&problem=1282
*
* @author Martin Lambeck
* @version 1.0, 01/08/2010
*
* Method : newtons method, bisection (both AC)
* Status : Accepted
* Runtime: 0.620
*/
public class Main
{
static BufferedLongReader blr = new BufferedLongReader();
static long p, q, r, s, t, u;
public static void main (String...args)
{
while (testcase());
}
public static boolean testcase()
{
try
{
p = blr.nextLong();
q = blr.nextLong();
r = blr.nextLong();
s = blr.nextLong();
t = blr.nextLong();
u = blr.nextLong();
} catch (IllegalStateException e)
{
//input is terminated by eof
if (e.getCause() instanceof java.io.EOFException)
return false;
else
throw e;
}
//bisection and newton are both AC
double result;
result = bisection();
//result = newton();
if (result >= 0.0 && result <= 1.0)
System.out.printf("%.4f%n", result, result);
else
System.out.println("No solution");
return true;
}
//f(x) is monotone decreasing in [0,1]
// if f(x) is not collinear with the x-axis in [0,1] then
// sign( f(a) ) != sign( f(b) ), a < b <=> A c exists, such that ( f(c) == 0 ), with ( a <= c <= b )
public static double bisection()
{
if (f(0.0) == 0.0)
return 0.0;
if (f(1.0) == 0.0)
return 1.0;
if (f(0.0) * f(1.0) > 0) //if same sign
return -1;
double l = 0.0;
double r = 1.0;
double mid = 0.5;
while (f(l)-f(r) > 0.000000001)
{
mid = (r - l) / 2.0 + l;
if (f(mid) == 0)
return mid;
if (f(mid) * f(r) > 0) //check for same sign
r = mid;
else
l = mid;
}
return mid;
}
//the well-known newton's method. see wikipedia
public static double newton()
{
double bestx = -1;
double bestfx = 999;
double x = 0.0;
double gx = -1;
double fx = -1;
//use different startvalues for x
for (double x0 = 0.0; x0 <= 1.01; x0 += 0.1)
{
x = x0;
//do 30 iterations ( way more than actually required ;) )
for (int i = 0; i < 30; i++)
{
gx = g(x);
fx = f(x);
if (fx == 0 && x <= 1 && x >= 0)
return x;
// if slope is too flat we probably wont get a useful value for x
// especially handle gx==0
if (Math.abs(gx) < 0.00001)
{
x = -1;
break;
}
x = x - fx/gx; // x <- x - f(x)/f'(x)
}
if (x <= 1 && x >= 0 && Math.abs(fx) < bestfx)
{
bestfx = Math.abs(fx);
bestx = x;
}
}
if (Math.abs(f(bestx)) <= 0.00001)
return bestx;
else
return -1;
}
public static double f(double x)
{
double result;
double cosx;
double sinx;
cosx = Math.cos(x);
sinx = Math.sin(x);
result = (p * Math.exp(-x)) + (q * sinx) + (r * cosx) + (s * (sinx/cosx)) + (t * x * x) + u;
return result;
}
//g(x) = f'(x) = df(x)/dx
public static double g(double x)
{
double result;
double cosx;
cosx = Math.cos(x);
result = (-p * Math.exp(-x)) + (q * cosx) - (r * Math.sin(x)) + (s / (cosx*cosx)) + (2 * t * x);
return result;
}
}
class BufferedLongReader
{
byte[] buf = new byte[1024*32];
int pos = 0;
int len = 0;
public long nextLong()
{
long num = 0;
int chr;
boolean found = false;
boolean negative = false;
boolean stop = false;
while (!stop)
{
if (pos == len)
{
pos = 0;
try
{
len = System.in.read(buf);
} catch (java.io.IOException e)
{
throw new IllegalStateException(e); //wrap into runtime exception and throw
}
}
if (len == -1)
{
if (!found)
throw new IllegalStateException(new java.io.EOFException());
stop = true;
chr = ' ';
} else
{
chr = buf[pos];
pos++;
}
if (chr >= '0' && chr <= '9')
{
num = num*10 + (chr - '0');
found = true;
} else if (chr == '-')
{
if (found)
{
// - after a number
// stop here, and push back - into the buffer, maybe sign of next number
stop = true;
pos--;
buf[pos] = '-';
} else
{
negative = true;
}
} else
{
if (found)
stop = true;
else
negative = false;
}
}
return (negative ? -num : num);
}
}
2.
1.
import java.util.Scanner;
/**
* @group Lermer Florian, Sayli Hidir, Taskin Umut
* @contact lermer@gmail.de, hidirsayli@hotmail.de taskin_umut@yahoo.de
* @Problem_ID=U10341
* @Link http://icpcres.ecs.baylor.edu/onlinejudge/index.php?option=com_onlinejudge&Itemid=8&category=15&page=show_problem&problem=1282
* @external_help_link http://online-judge.uva.es/board/viewtopic.php?f=20&t=1058&st=0&sk=t&sd=a&sid=ca99548db7a11d738230331897e5504c
*
* @status Accepted
* @Version V1.09
*
* @problematical_issues - Only mathematical Problems *
* @param args
*/
/*
* 1. calculate x=f(0) and y=f(1)
2. if (x > 0 && y > 0) print 'No solution'.
3. if (x < 0 && y < 0) print 'No solution'.
4. if ( x == 0 ) print '0.0000'.
5. if ( y == 0 ) print '1.0000'.
6. You are sure that u have a solution, and calculate it (by your process).
*/
public class Main {
/**
* @param args
*/
private static int u,r,s,t,q,p;
public static void main(String[] args)
{
Scanner sc=new Scanner(System.in);
double x,y;
while(sc.hasNext())
{
p=sc.nextInt();
q=sc.nextInt();
r=sc.nextInt();
s=sc.nextInt();
t=sc.nextInt();
u=sc.nextInt();
x=function(0);
y=function(1);
if (x > 0 && y > 0){ System.out.println("No solution");continue;}
if (x < 0 && y < 0){ System.out.println("No solution");continue;}
if ( x == 0 ){ System.out.println("0.0000");continue;}
if ( y == 0 ){ System.out.println("1.0000");continue;}
else {
x=0.5;
for (int i=0;i<10;i++){
x=x-function(x)/dfunction(x);
}
System.out.printf("%.4f%n",x);
}
}
}
private static double function(double x) {
// return p/pow(E,x) + q*sin(x) + r*cos(x) + s*tan(x) + t*x*x + u;
double se=p/Math.pow(Math.E, x)+q* Math.sin(x)+r*Math.cos(x)+ s*Math.tan(x)+t*x*x+u;
return se;
}
private static double dfunction(double x)
{
// double se=1.0/cos(x);
// se*=se;
// return -p/pow(E,x) + q*cos(x) - r*sin(x) + s*se + t*2*x;
double se=1.0/Math.cos(x);
se*=se;
se=-p/Math.pow(Math.E, x)+q* Math.cos(x)-r*Math.sin(x)+ s*se+t*2*x;
return se;
}
}
3.
/**
* ACM Training 2009
* ACM Problem #10341 -
Solve It
* Link:
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=15&page=show_problem&problem=1282
*
* @author Felix Dietrich
* @version 1.0, 09/23/2009
*
* Methode: Newton Method
* Status : Accepted
* Runtime: 0.672
*/
import java.util.*;
public class Main
{
static
double p,q,r,s,t,u;
public
static void main(String... strs)
{
Scanner sc = new Scanner(System.in);
double solution;
while(sc.hasNext())
{
p = sc.nextInt();
q = sc.nextInt();
r = sc.nextInt();
s = sc.nextInt();
t = sc.nextInt();
u = sc.nextInt();
if(Math.abs(f(0.0)) < 1e-6 )
System.out.println(String.format("%.04f", 0.0000));
else if(Math.abs(f(1.0))<1e-6)
System.out.println(String.format("%.04f", 1.0000));
else if(f(0.0) * f(1.0) > 0)
System.out.println("No
solution");
else
{
solution = 0.5;
for(int i=0; i<20; i++)
{
solution
= solution - f(solution)/fDiff(solution);
}
System.out.println(String.format("%.04f", solution));
}
}
}
private
static double f(double x)
{
return
p*Math.exp(-x)+q*Math.sin(x)+r*Math.cos(x)+s*Math.tan(x)+t*x*x+u;
}
private
static double fDiff(double x)
{
return
-p*Math.exp(-x)+q*Math.cos(x)-r*Math.sin(x)+s*1.0/(Math.cos(x)*Math.cos(x))+2.0*t*x;
}
}