10385 - Duathlon

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

Moderator: Board moderators

hotovaga
New poster
Posts: 4
Joined: Mon Nov 29, 2010 9:35 pm

10385 - Duathlon

Post by 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;
}

matrix2220
New poster
Posts: 9
Joined: Mon Jul 07, 2014 3:37 pm
Contact:

Re: 10385 - Duathlon

Post by 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)

Post Reply

Return to “Volume 103 (10300-10399)”