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

Post by bigredteam2000 » Sun Dec 23, 2001 11:07 pm

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
Experienced poster
Posts: 110
Joined: Thu Dec 13, 2001 2:00 am

Post by wyvmak » Mon Mar 04, 2002 5:21 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
Location: Pasadena, CA

Post by C8H10N4O2 » Tue Mar 05, 2002 5:59 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
Location: Pasadena, CA

Post by C8H10N4O2 » Tue Mar 05, 2002 6:01 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:

Post by Stefan Pochmann » Wed Mar 06, 2002 3:26 am

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

C8H10N4O2
Experienced poster
Posts: 137
Joined: Wed Feb 27, 2002 2:00 am
Location: Pasadena, CA

Post by C8H10N4O2 » Wed Mar 06, 2002 3:29 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

Post by Shaikat Mahmud » Fri Sep 27, 2002 8:37 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[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
New poster
Posts: 1
Joined: Fri Feb 21, 2003 1:43 pm

222 WA

Post by jabawork » Fri Feb 28, 2003 6:05 pm

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

User avatar
coolbila
New poster
Posts: 8
Joined: Tue Apr 01, 2003 8:11 pm

Post by coolbila » Wed May 14, 2003 7:56 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.....

Post by Shiraz » Sun May 15, 2005 9:52 pm

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
New poster
Posts: 2
Joined: Tue Dec 06, 2005 8:22 pm

budget travel solution

Post by hina » Sat Dec 17, 2005 7:48 pm

#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
New poster
Posts: 2
Joined: Tue Dec 06, 2005 8:22 pm

budget travel solution

Post by hina » Sat Dec 17, 2005 7:49 pm

#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;;
}
}

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

222 - Budget Travel

Post by rio » Mon Nov 13, 2006 10:59 pm

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
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Tue Nov 14, 2006 3:48 am

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

Post by Tolien » Thu May 29, 2008 6:18 pm

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?

Post Reply

Return to “Volume 2 (200-299)”