10385 - Duathlon

All about problems in Volume CIII. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

10385 - Duathlon

Postby hotovaga » Mon Nov 29, 2010 9:42 pm

Can anyone tell me what is the problem in my code? I've just learnt ternary search from wikipedia and tried to implement it..I would be very happy if someone tell me why this code is judged as WA
Thanks in advance. here is my code:


Code: Select all
#include<iostream>
#include<cstdio>

using namespace std;

int res=0,c;
float r,k;
float contestant[25][2];
float precval=0.001;

int dist;
int ternary_search(float left,float right,float precval);
float f(float run_dist);

int main()
{
   int i,j;
   while(cin>>dist){
      res=-1;
      cin>>c;

      for(i=0;i<c;i++){
         cin>>contestant[i][0]>>contestant[i][1];
         //cin.ignore();
      }

      ternary_search(0,dist,precval);
      if(res<0)
         cout<<"The cheater cannot win."<<endl;
      else
         printf("The cheater can win by %d seconds with r = %.2fkm and k = %.2fkm.\n",res,r,k);
   }


return 0;
   }


int ternary_search(float left,float right,float precval)
{
   if(right-left<=precval){
      res=f(left);
      r=left;
      k=dist-left;
      return 0;
   }


   
   float first_third=(left*2+right)/3;
   float last_third=(left+right*2)/3;
//   cout<<first_third<<" "<<last_third<<endl;
   float l1=f(first_third),l2=f(last_third);
   if(l1<l2)
      return ternary_search(first_third,right,precval);
   else if(l1>=l2)
      return ternary_search(left,last_third,precval);
}


float f(float run_dist)
{
   float cyc_dist=dist-run_dist;
   float t=10000000000000,tempt;

   for(int i=0;i<c-1;i++){
      tempt=run_dist/contestant[i][0]+cyc_dist/contestant[i][1];
      if(tempt<t) t=tempt;
   }
   
   float cheater_t=run_dist/contestant[c-1][0]+cyc_dist/contestant[c-1][1];

   return (t-cheater_t)*3600;
}
hotovaga
New poster
 
Posts: 4
Joined: Mon Nov 29, 2010 9:35 pm

Previous

Return to Volume CIII

Who is online

Users browsing this forum: No registered users and 1 guest