Sign-up Thread: Problem Solving #1
Title: Problem Solving #1: Hotel Rooms
I realize this is difficult, and it's meant as a starting point. If you wish for a less difficult question, let me know and i'll find one.
A hotel has N rooms numbered from 1 to N. One day, M guests numbered from 1 to M according to their importancy (this is, client 1 is more important than client 2). The hotel's a good hotel, so it always has more rooms than clients, so everybody can have a room.
However, the price of a room depends in the room number and the client staying in it. For example: guest 1 would pay $100 for room 1, $50 for room 2, $90 for room 3 and so on. That way, each client has his own price list for all the hotel rooms.
Since clients have a hierarchy, the client with the lowest number is the most important, so he must go to a room that has a lower number than the rest of the clients (due to how close the room is to the restaurant). That happens too with the rest of the clients, they must go to a room with lesser number than the clients with less importance.
The hotel manager must allow them all to stay in the hotel, but he wishes to get as most profit as possible, but respecting hierarchy and allowing every guest in the hotel.
The input file, HOTEL.IN , has in its first line, the number N and the number M (M < N and N <= 200), after that, there are MxN lines with three numbers, the first one is the room number, the second one is the client's number and the last one is the corresponding fee for that room for that client.
The output file, HOTEL.OUT , must have N lines, wach one with a number indicating the number of the client which is staying in that room, or 0 if that room stays free. This configuration report must lead to a maximum profit.
NOTE: if there is more than one possible configuration that leads to the same maximum profit, any one of these configurations will be marked as valid.
SAMPLE INPUT: HOTEL.IN
1 1 100
2 2 50
3 1 30
3 2 60
2 1 40
1 2 50
SAMPLE OUTPUT: HOTEL.OUT
Taken from OCC. February 2001
The files mentioned, HOTEL.IN and HOTEL.OUT are not needed. You may accept input and output from whatever normal source you want. However, the input and output must look mostly like the problem above.
efficiency: how many resources are used by a program, and any noticable speed bumps in the program
elegance: code readability, appropriate functions, etc...
portability: correct and compilable code across all platforms
Correctness: Does your program do what is asked completely and correctly, even with different yet valid input?
Logic: this measure will be ranked against other contestants. This criteria grades against brute force and for intelligent problem solving.
Judges: (3 slots left)
Contestants: (10 slots left)
Time limit: 2 weeks, until November 28, midnight. Deadline is flexible, and will be extended if needed.
Have fun, and don't forget to make sure your program works. :)
Feel free to ask for any clarification.
e-mail entries to email@example.com .