Ticket distribution

Go to the Jutge statement of the problem

A football club does not usually have enough tickets for all its supporters, so some method is needed to distribute them:

When a supporter asks for a ticket, if there is any available at that moment, the supporter immediately gets one. Otherwise, the supporter’s code is recorded. When a ticket is available, if there is no recorded code at that moment, the ticket is stored. Otherwise, the ticket is given to the supporter with the shortest code.

Ties are broken as follows: A fixed word w is arbitrarily chosen at the beginning of the process. Then, lexicographical order is used among codes of length n, except that w[1..n] is considered the first code, and the rest are considered cyclically. For instance, if n = 4 and w[1..4] =“abcd”, then codes of length 4 are sorted in this order: “abcd”, “abce”, … , “abcz”, “abda”, … , “abdz”, … , “zzzz”, “aaaa”, … , “abcc”.

Write a program to distribute tickets among supporters according to the method just described above.

Input: Input consists of several cases. Each case begins with a string w made up of 10 lowercase letters, followed by several events:

‘T’ for an available ticket, and
‘S’ for a supporter asking for a ticket.

In the latter case follows the supporter’s code (a non-empty string with at most 10 lowercase letters). The same supporter can ask for more than one ticket.

An ‘E’ marks the end of the events of a case. Assume that each case has no more than 105 events.

Output: For every case, print the codes of the supporters who get tickets, in the order in which this happens. Print two lines with final information. Count every supporter who unsuccessfully asked for t tickets exactly as t supporters who unsuccessfully asked for one ticket. Print an empty line after every case.

Hint

Use a priority_queue with a custom ordering to store the codes of the supporters waiting for a ticket. First focus on getting the exercise done, perhaps with a “wrong” ordering, and then focus on the ordering on the supporters.

The code below shows a possible way to use a priority_queue for this, but not the custom ordering required by the exercise.

A possible C++ code to start the problem

// STL - Ticket distribution
#include<iostream>
#include<queue>

using namespace std;

string w;

struct comp {
    bool operator()(const string &s1, const string &s2){
        // do something
    }
};


int main(){
    while (cin >> w){
        priority_queue<string, vector<string>, comp> pq;
        char op;//operation
        int avail = 0;//available tickets
        while(cin >> op and op!='E'){
            if (op == 'T'){
                if (pq.size()== 0) ++avail;
                else{
                    cout << pq.top()<< endl;
                    pq.pop();
                }
            }
            else{//op is 'S'
                string code;
                cin >> code;
                if (avail == 0) pq.push(code);
                else{
                    cout << code << endl;
                    --avail;
                }

            }
        }
        cout << avail <<" ticket(s) left" << endl;
        cout << pq.size() << " supporter(s) with no ticket" << endl << endl;
    }
}

A possible solution

// STL - Ticket distribution
#include<iostream>
#include<queue>

using namespace std;

string w;

struct comp {
    bool operator()(const string &s1, const string &s2){
        if (s1.size()>s2.size()) return true;
        if (s1.size()<s2.size()) return false;
        string ref = w.substr(0,s1.size());
        if (s2 < ref) return s1 < ref and s2 < s1;
        else          return s1 < ref or s1 > s2;
    }
};


int main(){
    while (cin >> w){
        priority_queue<string, vector<string>, comp> pq;
        char op;//operation
        int avail = 0;//available tickets
        while(cin >> op and op!='E'){
            if (op == 'T'){
                if (pq.size()== 0) ++avail;
                else{
                    cout << pq.top()<< endl;
                    pq.pop();
                }
            }
            else{//op is 'S'
                string code;
                cin >> code;
                if (avail == 0) pq.push(code);
                else{
                    cout << code << endl;
                    --avail;
                }

            }
        }
        cout << avail <<" ticket(s) left" << endl;
        cout << pq.size() << " supporter(s) with no ticket" << endl << endl;
    }
}

Other Links