Page 1 of 1 [ 1 post ]

#### Problem with algorithm puzzle

 Print view Previous topic | Next topic

#### Problem with algorithm puzzle

Author Message
 Post subject: Problem with algorithm puzzle  Posted: November 5th, 2017, 2:28 pm

Joined: January 6th, 2017, 9:36 pm
Posts: 3
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:
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:
#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?

Display posts from previous:  Sort by

 Page 1 of 1 [ 1 post ]

 You cannot post new topics in this forumYou cannot reply to topics in this forumYou cannot edit your posts in this forumYou cannot delete your posts in this forumYou cannot post attachments in this forum

 Search for: