Ticket distribution P62653


Statement
 

pdf   zip

html

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

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

Public test cases
  • Input

    aabbccddee
    S abcdef
    S zyxwvu
    S rr
    S aaaaaaaa
    S aabbccdd
    S aabbccdc
    S aabbcd
    T
    T
    T
    T
    T
    T
    E
    
    zyxwvutsrq
    T
    S hijk
    S a
    S y
    S z
    S z
    T
    T
    T
    T
    S za
    S zx
    S zy
    S zz
    S zyx
    T
    T
    T
    T
    T
    T
    T
    E
    
    aaaaaaaaaa
    S b
    S b
    E
    
    zzzzzzzzzz
    E
    

    Output

    rr
    aabbcd
    abcdef
    zyxwvu
    aabbccdd
    aaaaaaaa
    0 ticket(s) left
    1 supporter(s) with no ticket
    
    hijk
    z
    z
    a
    y
    zy
    zz
    za
    zx
    zyx
    2 ticket(s) left
    0 supporter(s) with no ticket
    
    0 ticket(s) left
    2 supporter(s) with no ticket
    
    0 ticket(s) left
    0 supporter(s) with no ticket
    
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Official solutions
    C++
    User solutions
    C++
    Event
    Desè Concurs de Programació de la UPC - Semifinal
    Date
    2012-06-30