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

Re: 10385 - Duathlon

Postby matrix2220 » Wed Aug 06, 2014 4:35 pm

Some Things You should know:
-----------------------------------
1) Contestants speed in km/hour
2) Time margin should be rounded before printing
---------------
Hints:
-------
1) r = t - k
2) Ternary search on K
3) No solution if time margin is -ve
------------------------

Input:
Code: Select all
7
2
3 4
4 3

100
9
25 20
40 12
37 23
9 49
17 19
33 5
67 3
34 11
21 30


AC output
Code: Select all
The cheater can win by 2100 seconds with r = 7.00km and k = 0.00km.
The cheater can win by 1270 seconds with r = 21.53km and k = 78.47km.


Hope That Helps
Abdelrahman Ali (MaTrix)
matrix2220
New poster
 
Posts: 9
Joined: Mon Jul 07, 2014 3:37 pm

Previous

Return to Volume CIII

Who is online

Users browsing this forum: Baidu [Spider] and 4 guests