222 - Budget Travel

[bigredteam2000]

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[52];

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[0].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]

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]

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]

Also, you assign min to 100000000000000. A 4-byte unsigned integer has 4294967296 (2^32) max. Think about it.

[Stefan Pochmann]

Almost correct. Max(int) is usually 2^31-1 = 2147483647.

[C8H10N4O2]

Yep, good one. My mistake. Unsigned 4-byte int should be 4294967295 (2^32-1) max.

[Shaikat Mahmud]

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[0].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[0].c + 2.0;

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

}
}

[jabawork]

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

[coolbila]

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.

[Shiraz]

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[52];

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[0].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]

#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[52];

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[10];
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[0].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]

#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[52];

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[10];
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[0].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]

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

Thanks in advance.
----
Sory for my poor English.

[Jan]

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.

[Tolien]

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
		{
			line = readLine(512);

		} 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(""))
			{
				lines.add(line);
			}
			try
			{
				line = readLine(512);
			}
			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;
			}

			return total + 20;
		}
		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)
		{
			car = System.in.read();
			if (car < 0 || car == '\r' | car == '\n')
				break;
			lin[lg++] += car;
		}
		if (car < 0 && lg == 0)
			return null;
		return new String(lin, 0, lg);
	}
}

(I'm aware it's probably not the most efficient code in the world, and using Java doesn't help much)

I think I've covered the points coolbila made, thought up as many testcases as I can, and still can't see what I'm doing wrong - any thoughts?