Register    Login    Forum    Search    FAQ

Board index » Everything




Post new topic Reply to topic  [ 1 post ] 
Author Message
 Post 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?


Top 
 Profile  
Reply with quote  
Display posts from previous:  Sort by  
 
Post new topic Reply to topic  [ 1 post ] 

Board index » Everything


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

Search for:
cron