## 222 - Budget Travel

Moderator: Board moderators

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

### Re: 222 - Budget Travel

Code: Select all

``````ac never mind
``````

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

### Re: 222 - Budget Travel

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

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;
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.dist = 0; stops.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;
}``````