222 - Budget Travel

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

Moderator: Board moderators

Labib
New poster
Posts: 12
Joined: Tue Mar 05, 2013 4:49 pm

Re: 222 - Budget Travel

Post by Labib » Sun Mar 10, 2013 1:11 pm

Code: Select all

ac never mind
thanks in advance.

vatsa_17
New poster
Posts: 4
Joined: Fri May 22, 2015 8:20 am

Re: 222 - Budget Travel

Post by vatsa_17 » Fri May 22, 2015 11:26 am

hi!! i am trying to solve this problemhttp://uva.onlinejudge.org/external/2/222.pdfm on uva o9 judge,but i am getting WA on test cases.here's my codehttp://ideone.com/Sq8Nrv...can someone please explain why??

uonline
New poster
Posts: 1
Joined: Sat May 28, 2016 2:21 am

Re: 222 - Budget Travel

Post by uonline » Sat May 28, 2016 2:28 am

What to be done is simply follow the question. No extra assumptions.
checked only for MoreThanHalf && CanReachNext. Cents need to be rounded off at each stop and at final sum.

Code: Select all

#include <stdio.h>
typedef struct _Node
{
	double dist;
	double price;
} Node;

double dest, rate,cap, invest;
int N;
Node stops[55];
double Ans = -1;
void _bt(int last, int curr, double cost)
{
	int canReachNext = 0;
	int MoreThanHalf = 0;
	int Reachable = 0;
	double StopCost = 0;
	if(curr == N+2)
	{
		if(Ans < 0 || Ans > cost) Ans = cost; return;
	}

	if((stops[curr+1].dist - stops[last].dist) <= cap*rate) canReachNext = 1;
	if((stops[curr].dist - stops[last].dist) <= cap*rate) Reachable= 1;
	if(((stops[curr].dist - stops[last].dist)*2) <= cap*rate) MoreThanHalf = 1;

	if(!Reachable) return;
	if(Ans > 0 && Ans < cost) return;

	StopCost = ((stops[curr].dist - stops[last].dist)*stops[curr].price)/rate;
	StopCost = (int)(StopCost+0.5);
	StopCost += 200;

	if(MoreThanHalf && canReachNext) _bt(last, curr+1, cost);
/*	else if(MoreThanHalf && !canReachNext) _bt(curr, curr+1, cost+StopCost);
	else if(!MoreThanHalf && !canReachNext) _bt(curr, curr+1, cost+StopCost);
	else if(!MoreThanHalf && canReachNext){*/
	else{
		 _bt(last, curr+1, cost);
		 _bt(curr, curr+1, cost+StopCost);
	}
}
int main()
{
	int n, set=0;
	scanf("%lf", &dest);
	/*printf("%lf\n",dest);*/
	while(dest > 0)
	{
		scanf("%lf %lf %lf %d", &cap, &rate, &invest, &N);
		/*printf("%lf %lf %lf %d\n", cap, rate, invest, N);*/
		for(n=1; n<=N; n++)
		{
			scanf("%lf %lf", &stops[n].dist, &stops[n].price);
			/*printf("%lf %lf", stops[n].dist, stops[n].price);*/
		}
		stops[0].dist = 0; stops[0].price = invest;
		stops[n].dist = dest; stops[n].price = 0;

		_bt(0,1,invest*100);
		Ans = (int)(Ans+0.5);
		printf("Data Set #%d\nminimum cost = $%0.2lf\n",++set, Ans/100);
		scanf("%lf", &dest);
		Ans = -1;
	}
	return 0;
}

Post Reply

Return to “Volume 2 (200-299)”