Sign-up Thread: Problem Solving #1

Title: Problem Solving #1: Hotel Rooms
Directions:

Quote:

---

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
3 2
1 1 100
2 2 50
3 1 30
3 2 60
2 1 40
1 2 50

SAMPLE OUTPUT: HOTEL.OUT
1
0
2

Taken from OCC. February 2001

---

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.

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.
Criteria:
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
Special Criteria:
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)
ygfperson

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 protected] .

I'll judge. Just try to keep the code standard people. I don't want to have to go through the problems of downloading other compilers.

>>For example: guest 1 would pay $100 for room 1, $50 for room 2, $90 for room 3 and so on.

:confused:

Typo?

I'll participate in the contest.

Be sure to only have active judges who really are interested in judging the contest.
I mean, has the text-compression contest been judged yet?

I'll sign up as a contestant.

I didn't get the pricing of the rooms:

Quote:

---

guest 1 would pay $100 for room 1, $50 for room 2, $90 for room 3 and so on.

---

100, 50, 90, what series give that output? Clarification plz :).

Oh, and since the input/output is through files, there is no need for a fancy interface, right?

add me in

I was gonna participate but ill only do it if i can make it for windows, cause thats what im in the mood for, so instead i offer to JUDGE, and i will be a good judge and stick with judging, im here everyday so.... pick me to judge :D

Quote:

---

Originally posted by Magos

100, 50, 90, what series give that output? Clarification plz :).

---

45n^2 + 185n + 240 :)

Seriously, if I understood ygfperson right, the input numbers are arbitary.

Quote:

---

Originally posted by Magos
I'll sign up as a contestant.

I didn't get the pricing of the rooms:

100, 50, 90, what series give that output? Clarification plz :).

---

i'll get back to y'all on that...

Quote:

---

Oh, and since the input/output is through files, there is no need for a fancy interface, right?

---

correct. you don't even have to use files, if you don't want to.

Quote:

---

Be sure to only have active judges who really are interested in judging the contest.
I mean, has the text-compression contest been judged yet?

---

hehehe... :D
i'll get to it soon. only one judge did send in his scores for that contest. i'll add in my scores, average, and post a long-overdue thread.

Sorry, I didn't read the problem close enough.

If I understand correctly, in the file, you first print N and M (N = rooms, M = guests).

Then you print the costs for all combinations of rooms and guests (for whatever reason they should differ :)).

Example (4 rooms, 2 guests):

Code:

---

4 2

1 1 500
1 2 200

2 1 240
2 2 180

3 1 20
3 2 8000

4 1 320
4 2 640

---

Is this correct?

If I understand it right, the file is
organized into a two dimensional array such that the
profit of the ith client staying at the j room is
P[i][j]. Problem is that example file has more than
6 numbers.

How is everyone doing on this contest? I'm having troubles, basically because the costs for a room is different for every guest.

I have seen this problem solved and source code posted some where... I think using questions already posted somewhere else is a good idea..

I'm hoping it's obvious that this contest has been abandoned by me... :(

I got this question from a guy named oskillian. You can find him on flashdaddee. I'm pretty sure he has the correct answer for this, so if it's bugging you, post something there.

He also has many other problems like this, some more difficult, few that are less, but most that are more clearly worded. He wrote down some of these problems from an international c/c++ programming contest, I forget what it's called. Feel free to ask him for some practice problems, or for another contest idea.

Hi,
ygfperson.. Dont you have any free time left.. I feel that you had the right attitude to run the contests here..

Vasanth

Quote:

---

I got this question from a guy named oskillian. You can find him on flashdaddee. I'm pretty sure he has the correct answer for this, so if it's bugging you, post something there.

---

I think this is the correct answer but I coded it sort of
sloppy.

Code:

---

#include <iostream>
using std::cerr;
using std::cout;
using std::endl;

#include <fstream>
using std::ifstream;
using std::ofstream;

const int MAX_M    = 200;
const int MAX_N    = 200;
const int COST_INF = 100000;
int M, N;

void load_file(const char* filename);
void print_results(const char* filename);
int find_optimal();

int C[MAX_M][MAX_N];
int S[MAX_M][MAX_N];


int main(void)
{
    load_file("HOTEL.IN");
    cout << "optimal = " << find_optimal() << endl;
    print_results("HOTEL.OUT");
   
    return 0;
}

void load_file(const char* filename)
{
    ifstream in(filename);

    if (!in) {
        cerr << "Error opening file" << endl;
        exit(EXIT_FAILURE);
    }

    in >> N;
    in >> M;

    int rn, cn, c;
    for (int i = 0; i < M * N; ++i) {
        in >> rn;
        in >> cn;
        in >> c;
        C[cn - 1][rn - 1] = c;
    }
}


int find_optimal()
{
    int T[MAX_M + 1][MAX_N + 1];
    int m, m_k;
   
    for (int i = 0; i < M; ++i) {
        T[i][N] = -COST_INF;
    }

    for (int i = 0; i <= N; ++i) {
        T[M][i] = 0;
    }

   
    for (int i = M - 1; i >= 0; --i) {
        for (int j = N - 1; j >= 0; --j) {
            m = -COST_INF;
            for (int k = j; k < N; ++k) {
                int t = C[i][k] + T[i + 1][k + 1];
                if (t > m) {
                    m = t;
                    m_k = k;
                }
            }
            T[i][j] = m;
            S[i][j] = m_k;
        }
    }

    return T[0][0];
}

void print_results(const char* filename)
{
    ofstream out(filename);
    int n = 1;
    int j, jp;
    int zn;
   
    if (!out) {
        cerr << "Error opening output file" << endl;
        exit(EXIT_FAILURE);
    }

    j = -1;
    zn = 0;
    for (int i = 0; i < M; ++i) {
        j = S[i][j + 1];
        for (int k = zn; k < j; ++k)
            out << 0 << endl;
       
        zn = j + 1;
        out << n << endl;
        n++;
    }

    for (int k = zn; k < N; ++k)
        out << 0 << endl;
}

---