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

bigredteam2000
New poster
Posts: 11
Joined: Sat Nov 17, 2001 2:00 am
It works with the sample input but when we sent it we received a wrong answer. We are checking all possible costs using a backtracking algorithm and choose the minimum cost at the end. Here is our source code:

//@begin_of_source_code
/*@JUDGE_ID: 15975FF 222 C++*/
#include<iostream.h>
#include<iomanip.h>

long double tank_size, max_ride, mpg, cost_at_dest, dist;
int stat_num, min;

struct gas_stat
{
long double dist_from_orig;
long double cost_per_gallon;
};
gas_stat G;

void Calculate(int index, long double dist1, int cost_so_far)
{
int ptr, i, ptr1;
long double temp;
if (index == stat_num+1)
{
if(cost_so_far < min)
{
min = cost_so_far;
}
return;

}
else
{
if (dist1 <= max_ride)
{
Calculate(stat_num+1, 0, cost_so_far);
}
else
{
ptr = index;
while ((ptr != stat_num+1) && ((G[ptr].dist_from_orig -
G[index].dist_from_orig)*2 <= max_ride))
{
ptr = ptr + 1;
}
ptr1 = ptr;
while(( ptr1 != stat_num+1) && (G[ptr1].dist_from_orig -
G[index].dist_from_orig <= max_ride ))
{
//cout << ptr1 << endl;
temp = cost_so_far+200+((G[ptr1].dist_from_orig - G[index].dist_from_orig)/mpg)*G[ptr1].cost_per_gallon + 0.5;
Calculate(ptr1, dist1-G[ptr1].dist_from_orig, int(temp));
ptr1++;
}
}
}
}

int main (void)
{
int i, counter = 1;
cin >> dist;
while (dist >= 0)
{
cin >> tank_size >> mpg >> cost_at_dest >> stat_num;
cost_at_dest = cost_at_dest*100;
G.dist_from_orig = 0;
for (i=1; i<=stat_num; i++)
{
cin >> G.dist_from_orig;
cin >> G.cost_per_gallon;
}
max_ride = mpg*tank_size;
min = 100000000000000;
Calculate(0, dist, int(cost_at_dest));
cin >> dist;
cout << "Data Set #" << counter++ << endl;
cout << "minimum cost = \$";
cout << setprecision(2) <<setiosflags(ios::fixed | ios::showpoint)<< double(min)/100 << endl;;
}
}
//@end_of_source_code

<font size=-1>[ This Message was edited by: bigredteam2000 on 2001-12-23 22:07 ]</font>

wyvmak
Experienced poster
Posts: 110
Joined: Thu Dec 13, 2001 2:00 am
if i haven't overlooked, it seems that the code cannot cope with the case that the last station needs to re-fill the tank.

C8H10N4O2
Experienced poster
Posts: 137
Joined: Wed Feb 27, 2002 2:00 am
I don't remember having to refill the tank at the end of the trip. I suggest you check your rounding/truncating; they look questionable on a first glance. "The amount paid at each stop is rounded to the nearest cent (where 100 cents make a dollar)."

C8H10N4O2
Experienced poster
Posts: 137
Joined: Wed Feb 27, 2002 2:00 am
Also, you assign min to 100000000000000. A 4-byte unsigned integer has 4294967296 (2^32) max. Think about it.

Stefan Pochmann
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:
Almost correct. Max(int) is usually 2^31-1 = 2147483647.

C8H10N4O2
Experienced poster
Posts: 137
Joined: Wed Feb 27, 2002 2:00 am
Yep, good one. My mistake. Unsigned 4-byte int should be 4294967295 (2^32-1) max.

Shaikat Mahmud
New poster
Posts: 1
Joined: Fri Sep 27, 2002 8:14 pm
Can anyone tell me why i am getting wrong answer ?

I think i am getting wrong answer for the way i handle precision, Is it the
right way to round to the nearest cent?

#include<stdio.h>
#include<math.h>

#define MAXSIZE 61
#define INF pow(2,31) - 1

float des;
float capg, mpg, cgd;
long N;

struct Station
{
float c, dis, costg;
}st[MAXSIZE];

float MIN(float a,float b)
{
if(a < b)
return a;
return b;
}

float round(float c)
{
c = floor(c * 100.0 + 0.5) * 0.01;
return c;
}

void main(void)
{
float t1, t2, min, c, mincost, nd, d, g;
long i, j, kase = 1;

// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);

while(1)
{
scanf("%f",&des);
if(des < 0)
break;

scanf("%f%f%f%ld",&capg,&mpg,&cgd,&N);

for(i = 1; i <= N; i++)
{
scanf("%f%f",&t1,&t2);
st.dis = t1;
st.costg = t2 * 0.01;
st.c = INF;
}

st[N+1].dis = des;
st[N+1].c = INF;
st[N+1].costg = 0;

st[N + 2].dis = des;

st.c = cgd;

for(i = 1; i <= N+1; i++)
{
for(j = i - 1; j >= 0; j--)
{

d = st.dis - st[j].dis;
g = d / mpg;
if(g > capg)
break;

nd = st[i + 1].dis - st.dis;

if( ((capg - g) <= capg /2) || (capg - g) < (nd / mpg))
{
c = st[j].c + round(g * st.costg) + 2 ;
st.c = MIN(st.c, c );
}
}
}

if( des <= 0.001)
st[N+1].c = st.c + 2.0;

printf("Data Set #%ld\n",kase++);
printf("minimum cost = \$%.2f\n",st[N+1].c - 2);

}
}

jabawork
New poster
Posts: 1
Joined: Fri Feb 21, 2003 1:43 pm

222 WA

Is anybody who can offer some test case??
thx ^^

coolbila
New poster
Posts: 8
Joined: Tue Apr 01, 2003 8:11 pm
I got WA many times
Finally I got AC

You should note :

1.If it is not enough gasoline, you never go to the station.
2.If you don't fill the tank in this station you can't go to the next station.
3.If the station is the destination you can always go there no matter how much gasoline it has.
4.If the tank is more than half , you shouldn't fill the tank in this station.
5.Others, you should fill the tank.
Oh my God ... Wrong Answer

Shiraz
New poster
Posts: 1
Joined: Sun May 15, 2005 9:43 pm

Why WA in p222......Somebody please fix this.....

Hiii........can someone please fix my problem.....i keep getting WA....i cant find the problem in this code....

//@begin_of_source_code
/*@JUDGE_ID: 15975FF 222 C++*/
#include<iostream.h>
#include<iomanip.h>

long double tank_size, max_ride, mpg, cost_at_dest, dist;
int stat_num, min;

struct gas_stat
{
long double dist_from_orig;
long double cost_per_gallon;
};
gas_stat G;

void Calculate(int index, long double dist1, int cost_so_far)
{
int ptr, i, ptr1;
long double temp;
if (index == stat_num+1)
{
if(cost_so_far < min)
{
min = cost_so_far;
}
return;

}
else
{
if (dist1 <= max_ride)
{
Calculate(stat_num+1, 0, cost_so_far);
}
else
{
ptr = index;
while ((ptr != stat_num+1) && ((G[ptr].dist_from_orig -
G[index].dist_from_orig)*2 <= max_ride))
{
ptr = ptr + 1;
}
ptr1 = ptr;
while(( ptr1 != stat_num+1) && (G[ptr1].dist_from_orig -
G[index].dist_from_orig <= max_ride ))
{
//cout << ptr1 << endl;
temp = cost_so_far+200+((G[ptr1].dist_from_orig - G[index].dist_from_orig)/mpg)*G[ptr1].cost_per_gallon + 0.5;
Calculate(ptr1, dist1-G[ptr1].dist_from_orig, int(temp));
ptr1++;
}
}
}
}

int main (void)
{
int i, counter = 1;
cin >> dist;
while (dist >= 0)
{
cin >> tank_size >> mpg >> cost_at_dest >> stat_num;
cost_at_dest = cost_at_dest*100;
G.dist_from_orig = 0;
for (i=1; i<=stat_num; i++)
{
cin >> G.dist_from_orig;
cin >> G.cost_per_gallon;
}
max_ride = mpg*tank_size;
min = 4294967295;
Calculate(0, dist, int(cost_at_dest));
cin >> dist;
cout << "Data Set #" << counter++ << endl;
cout << "minimum cost = \$";
cout << setprecision(2) <<setiosflags(ios::fixed | ios::showpoint)<< double(min)/100 << endl;;
}
}
//@end_of_source_code

THANX
SHIRAZ

hina
New poster
Posts: 2
Joined: Tue Dec 06, 2005 8:22 pm

budget travel solution

#include<iostream.h>
#include<iomanip.h>

long double tank_size, max_ride, mpg, cost_at_dest, dist;
int stat_num, min;

struct gas_stat
{
long double dist_from_orig;
long double cost_per_gallon;
};
gas_stat G;

void Calculate(int index, long double dist1, int cost_so_far)
{
int ptr, ptr1;
long double temp;
if (index == stat_num+1)
{
if(cost_so_far < min)
{
min = cost_so_far;
}
return;

}
else
{
if (dist1 <= max_ride)
{
Calculate(stat_num+1, 0, cost_so_far);
}
else
{
ptr = index;
while ((ptr != stat_num+1) && ((G[ptr].dist_from_orig -
G[index].dist_from_orig)*2 <= max_ride))
{
ptr = ptr + 1;
}
ptr1 = ptr;
while(( ptr1 != stat_num+1) && (G[ptr1].dist_from_orig -
G[index].dist_from_orig <= max_ride ))
{
//cout << ptr1 << endl;
temp = cost_so_far+200+((G[ptr1].dist_from_orig - G[index].dist_from_orig)/mpg)*G[ptr1].cost_per_gallon + 0.5;
Calculate(ptr1, dist1-G[ptr1].dist_from_orig, int(temp));
ptr1++;
}
}
}
}

int main (void)
{
double tcost;
int i, counter = 0;
cin >> dist;
while (dist >= 0)
{
cin >> tank_size >> mpg >> cost_at_dest >> stat_num;
cost_at_dest = cost_at_dest*100;
G.dist_from_orig = 0;
for (i=1; i<=stat_num; i++)
{
cin >> G.dist_from_orig;
cin >> G.cost_per_gallon;
}
max_ride = mpg*tank_size;
min = 100000000000000;
Calculate(0, dist, int(cost_at_dest));

tcost[counter]=double(min)/100 ;
cin >> dist;
counter++;
}
for(int j=0;j<counter;j++)

{
cout << "Data Set #" << j+1<< endl;
cout << "minimum cost = \$";
cout << setprecision(2) <<setiosflags(ios::fixed | ios::showpoint)<< tcost[j] << endl;;
}
}

hina
New poster
Posts: 2
Joined: Tue Dec 06, 2005 8:22 pm

budget travel solution

#include<iostream.h>
#include<iomanip.h>

long double tank_size, max_ride, mpg, cost_at_dest, dist;
int stat_num, min;

struct gas_stat
{
long double dist_from_orig;
long double cost_per_gallon;
};
gas_stat G;

void Calculate(int index, long double dist1, int cost_so_far)
{
int ptr, ptr1;
long double temp;
if (index == stat_num+1)
{
if(cost_so_far < min)
{
min = cost_so_far;
}
return;

}
else
{
if (dist1 <= max_ride)
{
Calculate(stat_num+1, 0, cost_so_far);
}
else
{
ptr = index;
while ((ptr != stat_num+1) && ((G[ptr].dist_from_orig -
G[index].dist_from_orig)*2 <= max_ride))
{
ptr = ptr + 1;
}
ptr1 = ptr;
while(( ptr1 != stat_num+1) && (G[ptr1].dist_from_orig -
G[index].dist_from_orig <= max_ride ))
{
//cout << ptr1 << endl;
temp = cost_so_far+200+((G[ptr1].dist_from_orig - G[index].dist_from_orig)/mpg)*G[ptr1].cost_per_gallon + 0.5;
Calculate(ptr1, dist1-G[ptr1].dist_from_orig, int(temp));
ptr1++;
}
}
}
}

int main (void)
{
double tcost;
int i, counter = 0;
cin >> dist;
while (dist >= 0)
{
cin >> tank_size >> mpg >> cost_at_dest >> stat_num;
cost_at_dest = cost_at_dest*100;
G.dist_from_orig = 0;
for (i=1; i<=stat_num; i++)
{
cin >> G.dist_from_orig;
cin >> G.cost_per_gallon;
}
max_ride = mpg*tank_size;
min = 100000000000000;
Calculate(0, dist, int(cost_at_dest));

tcost[counter]=double(min)/100 ;
cin >> dist;
counter++;
}
for(int j=0;j<counter;j++)

{
cout << "Data Set #" << j+1<< endl;
cout << "minimum cost = \$";
cout << setprecision(2) <<setiosflags(ios::fixed | ios::showpoint)<< tcost[j] << endl;;
}
}

rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

222 - Budget Travel

I think this problem is not so difiicult, but still gettng WA.
Is there a tricky case?

----
Sory for my poor English.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
I used straight forward BFS. So, I think there are no tricky cases. The only trick (I can think of ) is
The amount paid at each stop is rounded to the nearest cent (where 100 cents make a dollar).
Hope it helps.
And dont open a new thread if you can find an old one.
Ami ekhono shopno dekhi...
HomePage

Tolien
New poster
Posts: 1
Joined: Thu May 29, 2008 6:08 pm

Re: p222

I keep getting WA with this:

Code: Select all

import java.io.IOException;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Scanner;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;

public class Main
{
public static void main(String[] args) throws Exception
{
ArrayList<String> lines = new ArrayList<String>();
String line = "";
try
{

} catch (Exception e)
{
}
HashMap<Double, Double> stations = new HashMap<Double, Double>();
double tripLength = 0;
double tankSize = 0;
double mpg = 0;
double priceAtHome = 0;
int counter = 1;
int stationCount = 0;
while (!line.contains("-"))
{
if (!line.equals(""))
{
}
try
{
}
catch (Exception e)
{
}
}
Iterator<String> it = lines.iterator();
while (it.hasNext())
{
line = it.next();
Scanner scan = new Scanner(line);
if (entryCount(line) == 1)
{
//This is the first line of a block
if (stations.size() > 0 & stations.size() == stationCount)
{
Double minimum = solve(tripLength, tankSize, mpg, priceAtHome, stations);
System.out.println("Data Set #" + counter);
if ((minimum * 100) < 10000)
{
System.out.println("minimum cost = \$" + minimum + "0");
}
else
{
System.out.println("minimum cost = \$" + minimum);
}
counter++;
stations = new HashMap<Double, Double>();
tripLength = 0;
tankSize = 0;
mpg = 0;
priceAtHome = 0;
tripLength = scan.nextDouble();
}
else
{
tripLength = scan.nextDouble();
}
}
else if (entryCount(line) == 4)
{
//The parameters for the car
tankSize = scan.nextDouble();
mpg = scan.nextDouble();
priceAtHome = scan.nextDouble();
stationCount = scan.nextInt();
}
else if (entryCount(line) == 2)
{
double distance = scan.nextDouble();
double price = scan.nextDouble();
stations.put(distance, price);
}
}
Double minimum = solve(tripLength, tankSize, mpg, priceAtHome, stations);
System.out.println("Data Set #" + counter);
if ((minimum * 100) < 10000)
{
System.out.println("minimum cost = \$" + minimum + "0");
}
else
{
System.out.println("minimum cost = \$" + minimum);
}
}

public static int entryCount(String line)
{
Scanner scan = new Scanner(line);
int counter = 0;
while(scan.hasNext())
{
counter++;
scan.next();
}
return counter;
}

public static Double solve(double length, double tank,
double mpg, double priceAtHome,
HashMap<Double, Double> stations)
{
Double range = mpg * tank;
if (range < length)
{
double distanceRemaining = length;
double total = 0;
double point = 0;

while (distanceRemaining > range)
{
Set<Map.Entry<Double, Double>> set = stations.entrySet();
Iterator<Map.Entry<Double, Double>> it = set.iterator();

double minimum = 100000000;
double distance = 0;

while (it.hasNext())
{
Map.Entry<Double, Double> station = it.next();
double cost = station.getValue() * (station.getKey() - point) / mpg;
if (station.getKey() > point)
{
if (range + point >= station.getKey())
{
int stationsInFront = stationsInFront(stations, station.getKey());
if ((station.getKey() - point) > (range / 2) || stationsInFront == 0)
{
if (cost < minimum)
{
if (station.getKey() >= (length - distanceRemaining))
{
minimum = cost;
distance = station.getKey();
}
}
}
}

}
}

minimum += 200;
minimum = Math.ceil(minimum);
minimum /= 100;

distanceRemaining -= distance;
point = distance;
total += minimum;
}

}
else
{
return priceAtHome;
}
}

public static int stationsInFront(HashMap<Double, Double> stations, double distance)
{
Iterator<Map.Entry<Double, Double>> it = stations.entrySet().iterator();
int count = 0;
while (it.hasNext())
{
Map.Entry<Double, Double> station = it.next();
if (station.getKey() > distance)
{
count++;
}
}
return count;
}
static String readLine(int maxLg) throws IOException
{
byte[] lin = new byte[maxLg];
int lg = 0, car = -1;
while (lg < maxLg)
{