SP6951 CTOI10D1 - MP3 Player

**The MP3 Player** ================== Georg's new MP3 player has many interesting features, one of them being the key lock. All the keys are locked after more than _T_ seconds of inactivity. After the key lock is engaged, no key performs its original function, but if any key is pressed, the key lock is disengaged. For example, assume that _T_ = 5 and the player is currently locked. Georg presses the key _A_, waits for 3 seconds, presses the key _B_, waits for 5 seconds, presses _C_, waits for 6 seconds, and presses _D_. In this case only the keys _B_ and _C_ perform their regular functions. Note that the keys became locked between _C_ and _D_ was pressed. Sound level of the MP3 player is controlled by the + and - keys, increasing and decreasing volume by 1 unit respectively. The sound level is an integer between 0 and _V_ $ _{max} $ . Pressing the + key at volume _V_ $ _{max} $ or pressing the - key at volume 0 leaves the volume unchanged. **Task specification** ---------------------- Georg does not know the value of _T_. He wanted to find it by an experiment. Starting with a locked keyboard, he pressed a sequence of _N_ + and - keys. At the end of the experiment Georg read the final volume from the player's display. Unfortunately, he forgot to note the volume before his first keypress. For the purpose of this task, the unknown initial volume will be denoted _V_ $ _{1} $ and the known final volume will be denoted _V_ $ _{2} $ . You are given the value _V_ $ _{2} $ and a list of keystrokes in the order in which Georg made them. For each key, you are given the type of the key (+ or -) and the number of seconds from the beginning of the experiment to the moment when the key was pressed. The task is to find the largest possible **integer** value of _T_ which is consistent with the outcome of the experiment. **Input specification** ----------------------- The first line of the input contains three space-separated integers _N_, _V_ $ _{max} $ and _V_ $ _{2} $ (). Each of the next _N_ lines contains a description of one key in the sequence: a character + or -, a space and an integer _C_ $ _{i} $ (), the number of seconds from the beginning of the experiment. You may assume that the keypresses are in sorted order and that all times are distinct (i.e., _C_ $ _{i} $ < _C_ $ _{i + 1} $ for all ). **Constraints** --------------- You may assume that  and . In test cases worth 40 points . In test cases worth 70 points . **Output specification** ------------------------ If _T_ can be arbitrarily large, output a single line containing the word "infinity" (quotes for clarity). Otherwise, output a single line containing two integers _T_ and _V_ $ _{1} $ separated by a single space. The values must be such that carrying out the experiment with locking time _T_ starting at volume _V_ $ _{1} $ gives the final volume _V_ $ _{2} $ . If there are multiple possible answers, output the one with the largest _T_; if there are still multiple possible answers, output the one with the largest _V_ $ _{1} $ . (Note that at least one solution always exists: for _T_ = 0 none of the keys performs its action, so it suffices to take _V_ $ _{1} $ = _V_ $ _{2} $ .) **Examples** ------------ ****input:**** ``` 6 4 3 - 0 + 8 + 9 + 13 - 19 - 24 ``` ****output:**** ``` 5 4 ``` _For _T_ = 5 the keys perform the following actions: unlock, unlock, +, +, unlock, -._ _For any  we would get _V_ $ _{2} $ = 3. Note that the output contains the largest possible _V_ $ _{1} $ ._ _For  the last two keystrokes will both be active, hence it will be impossible to_ have _V_ $ _{2} $ = 3. ****input:**** ``` 3 10 10 + 1 + 2 + 47 ``` ****output:**** ``` infinity ``` _If _V_ $ _{1} $ = 10 then for any _T_ we'll have _V_ $ _{2} $ = 10._

N/A

N/A