Final exams P87812


Statement
 

pdf   zip

html

Professor Oak is dealing with the final exams of his course. He can either:

  • Put an exam on top of the other exams on his desk.
  • Remove the exam on top.
  • Check which is the best qualification among the exams on his desk.

Please help him to do it efficiently.

Input

To avoid large input files, the commands and numbers will be pseudo-randomly generated. The integer sequence will be produced by the following linear congruential generator:

A := 8433437992146984169
B := 7905438737954111703
X := S   // initial seed
function nextinteger():
    X := (A*X + B) mod 2^64
    return X / 2^32

For each number y returned, the command will be:

  • “Put”, if y ≢0 mod4. The grade of the exam will be the next pseudo-random number generated, which should not be counted as a command.
  • “Remove”, if y ≡ 0 mod4 and y ≢0 mod8.
  • “Check”, if y ≡ 0 mod4 and y ≡ 0 mod8.

Input consists of several cases, each with the number of instructions (between 0 and 106) and the initial seed S (between 0 and 264−1). Print “EMPTY DESK” every time that Prof. Oak tries to remove an exam or check the best qualification but there are no exams on his desk.

Output

For every case, print the best qualification for every query, together with the error messages. Print a blank line after every case.

Public test cases
  • Input

    9 3
    19 18446744073709551614
    1 10
    

    Output

    3931067935
    EMPTY DESK
    4132970100
    
    4208990443
    4208990443
    
    EMPTY DESK
    
    
  • Information
    Author
    Javier Gómez Serrano
    Language
    English
    Official solutions
    C++
    User solutions
    C++
    Event
    Novè Concurs de Programació de la UPC - Semifinal
    Date
    2011-06-29