Thread: Sign-up Thread: Problem Solving #1

  1. #1
    Just because ygfperson's Avatar
    Join Date
    Jan 2002
    Posts
    2,490

    Sign-up Thread: Problem Solving #1

    Title: Problem Solving #1: Hotel Rooms
    Directions:

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

  2. #2
    ˇAmo fútbol!
    Join Date
    Dec 2001
    Posts
    2,138
    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.

  3. #3
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708
    >>For example: guest 1 would pay $100 for room 1, $50 for room 2, $90 for room 3 and so on.



    Typo?
    Code:
    #include <cmath>
    #include <complex>
    bool euler_flip(bool value)
    {
        return std::pow
        (
            std::complex<float>(std::exp(1.0)), 
            std::complex<float>(0, 1) 
            * std::complex<float>(std::atan(1.0)
            *(1 << (value + 2)))
        ).real() < 0;
    }

  4. #4
    S Sang-drax's Avatar
    Join Date
    May 2002
    Location
    Göteborg, Sweden
    Posts
    2,072
    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?
    Last edited by Sang-drax : Tomorrow at 02:21 AM. Reason: Time travelling

  5. #5
    Confused Magos's Avatar
    Join Date
    Sep 2001
    Location
    Sweden
    Posts
    3,145
    I'll sign up as a contestant.

    I didn't get the pricing of the rooms:
    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?
    MagosX.com

    Give a man a fish and you feed him for a day.
    Teach a man to fish and you feed him for a lifetime.

  6. #6
    Its not rocket science vasanth's Avatar
    Join Date
    Jan 2002
    Posts
    1,683
    add me in

  7. #7

    Cool

    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

  8. #8
    S Sang-drax's Avatar
    Join Date
    May 2002
    Location
    Göteborg, Sweden
    Posts
    2,072
    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.
    Last edited by Sang-drax : Tomorrow at 02:21 AM. Reason: Time travelling

  9. #9
    Just because ygfperson's Avatar
    Join Date
    Jan 2002
    Posts
    2,490
    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...


    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.

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

  10. #10
    Confused Magos's Avatar
    Join Date
    Sep 2001
    Location
    Sweden
    Posts
    3,145
    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?
    MagosX.com

    Give a man a fish and you feed him for a day.
    Teach a man to fish and you feed him for a lifetime.

  11. #11
    Blank
    Join Date
    Aug 2001
    Posts
    1,034
    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.

  12. #12
    Confused Magos's Avatar
    Join Date
    Sep 2001
    Location
    Sweden
    Posts
    3,145
    How is everyone doing on this contest? I'm having troubles, basically because the costs for a room is different for every guest.
    MagosX.com

    Give a man a fish and you feed him for a day.
    Teach a man to fish and you feed him for a lifetime.

  13. #13
    Its not rocket science vasanth's Avatar
    Join Date
    Jan 2002
    Posts
    1,683
    I have seen this problem solved and source code posted some where... I think using questions already posted somewhere else is a good idea..

  14. #14
    Just because ygfperson's Avatar
    Join Date
    Jan 2002
    Posts
    2,490
    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.

  15. #15
    Its not rocket science vasanth's Avatar
    Join Date
    Jan 2002
    Posts
    1,683
    Hi,
    ygfperson.. Dont you have any free time left.. I feel that you had the right attitude to run the contests here..

    Vasanth

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Listening socket and thread problem
    By esaptonor in forum Windows Programming
    Replies: 6
    Last Post: 06-19-2010, 03:04 AM
  2. Terminating secondary thread from another thread
    By wssoh85 in forum C++ Programming
    Replies: 13
    Last Post: 12-19-2008, 05:14 AM
  3. Thread Prog in C language (seg fault)
    By kumars in forum C Programming
    Replies: 22
    Last Post: 10-09-2008, 01:17 PM
  4. problem with struct?
    By cangel in forum C Programming
    Replies: 8
    Last Post: 09-27-2008, 11:35 PM
  5. Simple thread object model (my first post)
    By Codeplug in forum Windows Programming
    Replies: 4
    Last Post: 12-12-2004, 11:34 PM