Page 1 of 1

Problem with algorithm puzzle

Posted: November 5th, 2017, 2:28 pm
by Tismas
Hi

I have a problem with a puzzle on spoj. it's not connected to any of the Chilli series but I thought this place is the best way to go.

It's only on polish spoj so I'll introduce the problem:
In first line you're given 2 integers - total distance to overcome and number(N) of hotels on the way.
In the next N lines you've got 2 integers each line - distance from the beggining and cost of the hotel.
You can't drive more than 800km without spending night at hotel. The goal is to print the smallest amount of money that can be spent to overcome total distance. Distances are given in ascending order, total distance is lower than 16000 and hotels count as well as cost of a hotel is lower than 1000.

Here's example input:

Code: Select all

2000 7
100 54
120 70
400 17
700 38
1000 25
1200 18
1440 40
And output for it is 35.

My code which gets wrong answer:
Spoiler:

Code: Select all

#include <iostream>
#include <vector>
using namespace std;

class Entry {
public:
	int lastStop;
	int costSum;

	Entry(int dist, int cost) {
		lastStop = dist;
		costSum = cost;
	}
};

int main() {
	vector<Entry> entries;
	entries.emplace_back(Entry(0, 0));
	int totalDist, hotelCount;
	cin >> totalDist >> hotelCount;
	while (hotelCount--) {
		int dist, cost;
		cin >> dist >> cost;
		for (int i = 0, s = entries.size(); i < s; i++) {
			Entry& e = entries[i];
			entries.emplace_back(Entry(dist, e.costSum + cost));
		}
		for (int i = 0; i < entries.size(); i++) {
			Entry& e = entries[i];
			if (dist - e.lastStop >= 800) {
				swap(e, entries.back());
				entries.pop_back();
				i--;
			}
		}
	}
	for (int i = 0; i < entries.size(); i++) {
		Entry& e = entries[i];
		if (totalDist - e.lastStop > 800) {
			swap(e, entries.back());
			entries.pop_back();
			i--;
		}
	}
	int minCost = entries[0].costSum;
	for (Entry& e : entries) if (e.costSum < minCost) minCost = e.costSum;
	cout << minCost;
}
You can check out this task here: http://pl.spoj.com/problems/HOT/, as I mentioned it's polish site, but you can try to submit the solution anyway.

Can you spot input which gives wrong answer or tell me better way to solve this problem?