10341  Solve It
Moderator: Board moderators
I used Newton's method to solve it, but would like if someone could point out why it didn't work until I used Jan's approach.
I was getting all the correct outputs for the inputs posted in this thread, but until I switched to first checking that f(0) and f(1) are of a different sign, I was getting WAs (I did handle NaN and Infinity, well, I thought I did).
My question would actually be: How do you know that there is no zero if both f(1) and f(0) are on the same side of the xaxis? I guess it is true in this case, but I couldn't tell by just looking at the function. Do you just chance it and see if it works?
(EDIT: I just played around with gnuplot a bit, it seems that the fact that coefficients are integers has something to do with it, but I still am not 100% sure)
(EDIT(2): sin(x)+cos(x)tan(x)+x*x1 has two zeros on [0,1]. It probably doesn't mean anything, because q is supposed to be negative, but still)
Thanks,
Darko
I was getting all the correct outputs for the inputs posted in this thread, but until I switched to first checking that f(0) and f(1) are of a different sign, I was getting WAs (I did handle NaN and Infinity, well, I thought I did).
My question would actually be: How do you know that there is no zero if both f(1) and f(0) are on the same side of the xaxis? I guess it is true in this case, but I couldn't tell by just looking at the function. Do you just chance it and see if it works?
(EDIT: I just played around with gnuplot a bit, it seems that the fact that coefficients are integers has something to do with it, but I still am not 100% sure)
(EDIT(2): sin(x)+cos(x)tan(x)+x*x1 has two zeros on [0,1]. It probably doesn't mean anything, because q is supposed to be negative, but still)
Thanks,
Darko
The function is continuous and differentiable on [0,1]. Just take its derivative, and you'll see that f'(x) <= 0 for all x in [0,1], and for given restrictions on values of p,q,...,u. That means f(x) is nonincreasing on [0,1].How do you know that there is no zero if both f(1) and f(0) are on the same side of the xaxis?
Sigh, I feel so stupid. I missed the restrictions at first (Started it last night around 2am), so I just got confused more and more. (I realized that some are only nonpositive and some are only nonnegative after my 2nd edit  long after my AC, now when I look at the code, I've never even seen the "integer" part, I'm parsing doubles)
Thanks, mf.
Just one more thing  if you have time: In your experience, what would be the limiting factors to using Newton's method? This is only the 2nd time I used it and I am really fascinated by it (for this problem it gets correct answers in 5 iterations).
Darko
Thanks, mf.
Just one more thing  if you have time: In your experience, what would be the limiting factors to using Newton's method? This is only the 2nd time I used it and I am really fascinated by it (for this problem it gets correct answers in 5 iterations).
Darko
Hi fellows!
I got AC 10341  "Solve It" with bisection, but would like to consider it in terms of NewtonRaphson method. This is to be my first NewtonRaphson , so I need your help.
This is my code:
(here I get initial approximation of the root by bisection(not that with this bisection only it got AC),  if in 10 iterations the root wasn't found, then begin NR )
Please help  why this gets WA?
I got AC 10341  "Solve It" with bisection, but would like to consider it in terms of NewtonRaphson method. This is to be my first NewtonRaphson , so I need your help.
This is my code:
(here I get initial approximation of the root by bisection(not that with this bisection only it got AC),  if in 10 iterations the root wasn't found, then begin NR )
Please help  why this gets WA?
Code: Select all
#include<stdio.h>
#include<math.h>
#define Epsilon 0.00000001
#define oo 21
int p,q,r,s,t,u;
double F(double x){
/*F(1)<=F(x)<=F(0) for each x: 0<=x<=1*/
return p/exp(x)+r*cos(x);
}
double G(double x){
/*G(0)<=G(x)<=G(1) for each x: 0<=x<=1*/
return q*sin(x)+s*tan(x)+t*x*xu;
}
/*the equation itself*/
double H(double x){
return(p/exp(x)+r*cos(x)+q*sin(x)+s*tan(x)+t*x*x+u);
}
/*derivative of the above*/
double dH(double x){
double f=cos(x);
return (p/exp(x)r*sin(x)+q*f+s/(f*f)+2*t*x);
}
int main()
{
int counter;
double up,down,f,g;
double x,y;
#ifndef ONLINE_JUDGE
freopen("10341.in","r",stdin);
#endif
while(scanf("%d %d %d %d %d %d",&p,&q,&r,&s,&t,&u)!=EOF)
{
if(p==0 && q==0 && r==0 && s==0 && t==0 && u==0)
{
printf("No solution\n");
continue;
}
q=q;
s=s;
t=t;
if(F(1)>G(1)F(0)<G(0))
{
printf("No solution\n");
continue;
}
up=1.0;
down=0.0;
counter=10;
while(updown>Epsilon)
{
x=(up+down)/2;
f=F(x);
g=G(x);
if(f<g)
up=x;
else if(f>g)
down=x;
else
break;
if(counter==0)
break;
}
if(fabs(F(x)G(x))<Epsilon){
printf("%.4lf\n",x);
continue;
}
q=q;
s=s;
t=t;
y=x;
while(fabs((x=yH(y)/dH(y))y)>Epsilon)
y=x;
printf("%.4lf\n",x);
}
return 0;
}
Last edited by serur on Tue May 23, 2006 1:57 pm, edited 1 time in total.
If there is ever a war between men and machines, it is easy to guess who will start it (c) Arthur Clarke
First of all, code tags can really help :)
Anyway  why do you treat all 0's that way? Now when I think about it, you can pick any x, but someone posted their solution with 0.0000 as answer (just checked, mine does that too).
Took me a while to make it work, but it ended up being my Java solution in C :(
First I check if H(0) and H(1) are of different signs (if not, there is no zero) and then if zeros are maybe at 0.0 or 1.0. Then I do Newton's. I start with x=0.5.
To answer my own question  you can always make a guess for x_0 and then check if it was a good one. After a few iterations, if it is good, it will converge. Meaning  the difference between two elements will be < EPS (like your check  be careful if you pick a bad x_0). If that difference is >EPS, pick another x_0 and try again. That worked for me in 10631.
Anyway  why do you treat all 0's that way? Now when I think about it, you can pick any x, but someone posted their solution with 0.0000 as answer (just checked, mine does that too).
Took me a while to make it work, but it ended up being my Java solution in C :(
First I check if H(0) and H(1) are of different signs (if not, there is no zero) and then if zeros are maybe at 0.0 or 1.0. Then I do Newton's. I start with x=0.5.
To answer my own question  you can always make a guess for x_0 and then check if it was a good one. After a few iterations, if it is good, it will converge. Meaning  the difference between two elements will be < EPS (like your check  be careful if you pick a bad x_0). If that difference is >EPS, pick another x_0 and try again. That worked for me in 10631.
You are right, there is no need to check around 0 and 1, I probably had that there first then added other stuff later.
Thanks, this actually helped me to figure out what Newton's actually does. I just redid it in Java checking only if it converges and if it does, if it is in [0,1]. For some reason I can't do it in C. Well, "some reason" might be that I don't really know C that well. I was just hoping that by doing it I would improve the time (now that my Java time is gone)
Thanks, this actually helped me to figure out what Newton's actually does. I just redid it in Java checking only if it converges and if it does, if it is in [0,1]. For some reason I can't do it in C. Well, "some reason" might be that I don't really know C that well. I was just hoping that by doing it I would improve the time (now that my Java time is gone)
Re: 10341  Solve It
Hi, how are you??
I'm trying this problem but still getting WA...
I'm using Newton's Raphson method, I have tryed each test input in this topic and the output is ok...
any ideas?, thanks
I'm trying this problem but still getting WA...
I'm using Newton's Raphson method, I have tryed each test input in this topic and the output is ok...
any ideas?, thanks
Code: Select all
#include <cstdio>
#include <cmath>
#include <iostream>
#define E 2.7182818284590452353602874713526624977572470937
#define EPS 1e12
using namespace std;
double p,q,r,s,t,u;
double func(double x){
return p/pow(E,x) + q*sin(x) + r*cos(x) + s*tan(x) + t*x*x + u;
}
double dfunc(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;
}
int main() {
#ifndef ONLINE_JUDGE
freopen("10341.in","r",stdin);
#endif
double s1,s2,x;
int i;
while(scanf("%lf %lf %lf %lf %lf %lf",&p,&q,&r,&s,&t,&u)==6) {
s1=func(0.0);
s2=func(1.0);
if ((s1>EPS && s2>EPS)  (s1<EPS && s2<EPS))
printf("No solution\n");
else {
x=0.5;
for (i=0;i<10;i++){
x=xfunc(x)/dfunc(x);
}
printf("%.4lf\n",x);
}
}
return 0;
}
There is no knowledge that is no power.

 New poster
 Posts: 3
 Joined: Sun Sep 07, 2008 6:25 pm
Re: 10341  Solve It
hi, everyone.
i've solved it using newtonrhapson method;
can anyone plz tell me why the TLE???
i am sure there is an infinity loop.but where????
thanks.
i've solved it using newtonrhapson method;
can anyone plz tell me why the TLE???
i am sure there is an infinity loop.but where????
thanks.
Code: Select all
#include<iostream>
#include<cmath>
using namespace std;
int main()
{
double p,q,qq,r,s,t,u,d,er,rr,ex,x,x1,fx,ffx;
freopen("1.txt","r",stdin);
while(scanf("%lf %lf %lf %lf %lf %lf",&p,&qq,&r,&s,&t,&u)==6){
x=.5;
if(p==0&&qq==0&&r==0&&s==0&&t==0&&u==0){
printf("No solution\n");
continue;
}
while(1){
er=x;
ex=exp(x);
fx=p*ex+qq*sin(x)+r*cos(x)+s*tan(x)+t*x*x+u;
d=1/cos(x);
ffx=1*p*ex+qq*cos(x)r*sin(x)+s*d*d+2*t*x;
if(ffx==0)x+=.01;/*if the denominator is zero i am simply changing it. it is a quadratic equation, so at best two such denominator can come.so it'll not slow down the algorithm much.*/
else{
rr=x1=x(fx/ffx);
x=x1;
er=fabs(er);
rr=fabs(rr);
q=fabs(errr);
if(q<=.00001)break;
}
}
if(x1<0x1>1)printf("No solution\n");
else printf("%.4lf\n",x1);
}
return 0;
}
Re: 10341  Solve It
Hello,I get WA many times.
But I really don't know what's wrong in this code.
I think it should be a stupid mistake, but I can't find it....
help me if you can,thank you~
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
//p*ex + q*sin(x) + r*cos(x) + s*tan(x) + t*x2 + u = 0
int p,q,r,s,t,u;//input parameter
bool in();
double caculate(double x);
int main(){
double lower_bound;
double upper_bound;
double mid;
int count=1;
char input;
int solution;
//freopen("in","r",stdin);
//freopen("out","w",stdout);
while(in()){
lower_bound=0;
upper_bound=1;
mid=(lower_bound+upper_bound)/2;
solution=2;
scanf("%c",&input);
while((upper_boundlower_bound)>0.00000001){
if(caculate(lower_bound)==0){
solution=1;
break;
}
else if(caculate(mid)==0){
solution=2;
break;
}
else if(caculate(upper_bound)==0){
solution=3;
break;
}
else if(caculate(lower_bound)*caculate(upper_bound)>0){
solution=0;
break;
}
else if(caculate(mid)*caculate(lower_bound)<0){
upper_bound=mid;
}
else if(caculate(mid)*caculate(upper_bound)<0){
lower_bound=mid;
}
mid=(lower_bound+upper_bound)/2;
}
if(count>1)
printf("\n");
switch (solution){
case 0:
printf("No solution");
break;
case 1:
printf("%.4lf",lower_bound);
break;
case 2:
printf("%.4lf",mid);
break;
case 3:
printf("%.4lf",upper_bound);
break;
default:
printf("%.4lf",mid);
break;
}
count++;
}
return 0;
}
bool in(){
if(scanf("%d%d%d%d%d%d",&p,&q,&r,&s,&t,&u)!=6){
return false;
}
else
return true;
}
double caculate(double x){
double result;
result=p*exp(x)+q*sin(x)+r*cos(x)+s*tan(x)+t*pow(x,2)+u;
return result;
}
But I really don't know what's wrong in this code.
I think it should be a stupid mistake, but I can't find it....
help me if you can,thank you~
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
//p*ex + q*sin(x) + r*cos(x) + s*tan(x) + t*x2 + u = 0
int p,q,r,s,t,u;//input parameter
bool in();
double caculate(double x);
int main(){
double lower_bound;
double upper_bound;
double mid;
int count=1;
char input;
int solution;
//freopen("in","r",stdin);
//freopen("out","w",stdout);
while(in()){
lower_bound=0;
upper_bound=1;
mid=(lower_bound+upper_bound)/2;
solution=2;
scanf("%c",&input);
while((upper_boundlower_bound)>0.00000001){
if(caculate(lower_bound)==0){
solution=1;
break;
}
else if(caculate(mid)==0){
solution=2;
break;
}
else if(caculate(upper_bound)==0){
solution=3;
break;
}
else if(caculate(lower_bound)*caculate(upper_bound)>0){
solution=0;
break;
}
else if(caculate(mid)*caculate(lower_bound)<0){
upper_bound=mid;
}
else if(caculate(mid)*caculate(upper_bound)<0){
lower_bound=mid;
}
mid=(lower_bound+upper_bound)/2;
}
if(count>1)
printf("\n");
switch (solution){
case 0:
printf("No solution");
break;
case 1:
printf("%.4lf",lower_bound);
break;
case 2:
printf("%.4lf",mid);
break;
case 3:
printf("%.4lf",upper_bound);
break;
default:
printf("%.4lf",mid);
break;
}
count++;
}
return 0;
}
bool in(){
if(scanf("%d%d%d%d%d%d",&p,&q,&r,&s,&t,&u)!=6){
return false;
}
else
return true;
}
double caculate(double x){
double result;
result=p*exp(x)+q*sin(x)+r*cos(x)+s*tan(x)+t*pow(x,2)+u;
return result;
}

 New poster
 Posts: 7
 Joined: Fri Sep 18, 2009 5:15 pm
 Location: Dhaka
 Contact:
Re: 10341  Solve It
Pls someone help me.getting tons of WA
here goes my code
Thanks in advance
here goes my code
Code: Select all
#include <stdio.h>
#include <math.h>
#include <iostream>
#define EPS 1e4
int p,q,r,s,t,u;
double x,val,low,high,med,val_low,a,b,val_hig;
double calcul(double x)
{
return (p / exp(x) + q * sin(x) + r*cos(x) + s*tan(x) + t*x*x +u);
}
using namespace std;
int main()
{
while(scanf("%d%d%d%d%d%d",&p,&q,&r,&s,&t,&u)==6)
{
a=calcul(0.0000);
b=calcul(1.0000);
if((a > EPS && b > EPS)  (a < EPS && b < EPS) )
printf("No solution\n");
else if(fabs(a) < EPS)
printf("0.0000\n");
else if(fabs(b) < EPS)
printf("1.0000\n");
else if(p == 0 && q == 0 && r == 0 && s == 0 && t == 0 && u == 0)
{
printf("0.0000\n");
}
else
{
for(low=0,high=.005;high<=1.0000EPS;low+=.005,high+=.005)
{
val_low=calcul(low);
val_hig=calcul(high);
if((val_low<EPS && val_hig > EPS)(val_low>EPS && val_hig < EPS))
break;
}
x=0.0000;
for(;low<=highEPS;)
{
med= (high+low)/2;
val=calcul(med);
val_low=calcul(low);
val_hig=calcul(high);
if((val < EPS && val_hig > EPS) ( val > EPS && val_hig < EPS))
low=med;
else if((val < EPS && val_low > EPS) (val > EPS && val_low < EPS))
high=med;
else
{
x=med;
break;
}
}
printf("%.4lf\n",x);
}
}
return 0;
}
Thanks in advance
onlinejudge.uva.es • Post a reply
Hi fellows! I got AC 10341  "Solve It" with bisection, but would like to consider it in terms of NewtonRaphson method. This is to be my first NewtonRaphson , so I need your help. This is my code: (here I get initial approximation of the root by bisection(not that with this bisection only it got AC),  if in 10 iterations the root wasn't found, then begin NR ) Please help  why this gets WA? Code: Select all#include<stdio.h>#include<math.h>#define Epsilon 0.00000001#define oo 21int p,q,r,s,t,u;double F(double x){ /*F(1)<=F(x)<=F(0) for each x: 0<=x<=1*/ return p/exp(x)+r*cos(x);}double G(double x){ /*G(0)<=G(x)<=G(1) for each x: 0<=x<=1*/ return q*sin(x)+s*tan(x)+t*x*xu;}/*the equation itself*/double H(double x){ return(p/exp(x)+r*cos(x)+q*sin(x)+s*tan(x)+t*x*x+u);}/*derivative of the above*/double dH(double x){ double f=cos(x); return (p/exp(x)r*sin(x)+q*f+s/(f*f)+2*t*x);} int main(){ int counter; double up,down,f,g; double x,y;#ifndef ONLINE_JUDGE freopen("10341.in","r",stdin);#endif while(scanf("%d %d %d %d %d %d",&p,&q,&r,&s,&t,&u)!=EOF) { if(p==0 && q==0 && r==0 && s==0 && t==0 && u==0) { printf("No solution\n"); continue; } q=q; s=s; t=t; if(F(1)>G(1)F(0)<G(0)) { printf("No solution\n"); continue; } up=1.0; down=0.0; counter=10; while(updown>Epsilon) { x=(up+down)/2; f=F(x); g=G(x); if(f<g) up=x; else if(f>g) down=x; else break; if(counter==0) break; } if(fabs(F(x)G(x))<Epsilon){ printf("%.4lf\n",x); continue; } q=q; s=s; t=t; y=x; while(fabs((x=yH(y)/dH(y))y)>Epsilon) y=x; printf("%.4lf\n",x); } return 0;}