Problem D
Keylogger
Languages
da
en
Thore likes mechanical keyboards. He uses a highly customised design, where every key has been carefully selected for resistance, actuation point, tactile feedback, travel distance, and clickiness. He finds the sound of the mechanical keys very satisfying. Your office is next to Thore’s and you hear the click-clock-clinging of him typing. After a while you notice that every key has a unique sound.
Given the sounds from Thore’s office, can you hear what he’s typing?
Each key except shift can be tapped, and has its own distinctive sound when tapped. The spacebar inserts a single space character at the end. The letter keys insert a single letter in their upper- or lowercase form at the end. For instance, tapping M inserts the lowercase “m” or the uppercase “M”. The delete key removes a single symbol, starting from the latest inserted symbol, provided there are symbols left. (Otherwise, nothing happens.)
Case is determined by the keyboard’s state, which is either capslocked or not, and whether the shift key is held down. Tapping the capslock key switches the state to capslocked or back. In the capslocked state, all letter keys produce their uppercase form. This behaviour is inverted when the shift key is held down. For instance, if the keyboard is not capslocked and shift is held down then tapping M inserts an uppercase “M”. Likewise, if the keyboard is capslocked and shift is held down then tapping M inserts a lowercase “m”.
The shift key is never tapped. Instead, it is either held down or released, each with its own sound. Thore’s keyboard has a single shift key (under his left thumb), so the two sounds must alternate.
Thore starts the work day with the keyboard not in capslocked state and with the shift key not held down.
The following table shows the sound each key makes. You hear no other sounds than those listed in the table.
![\includegraphics[width=0.7\textwidth ]{img/table-en.pdf}](/problems/keylogger/file/statement/en/img-0002.png)
Input
The first line of input is an integer $N$, where $N > 0$, the number of sounds you hear from Thore’s office. The following $N$ lines each contain a single sound, matching one of the keys in the table.
Output
Print the resulting text.
Scoring
|
Group |
Points |
Limits |
|
1 |
20 |
Thore only types letters, $N \leq 1\, 000$ |
|
2 |
30 |
Thore can also use spacebar, capslock, and delete, $N \leq 100\, 000$ |
|
3 |
50 |
Thore can use any key, $N \leq 100\, 000$ |
| Sample Input 1 | Sample Output 1 |
|---|---|
26 clank bong click tap poing clonk clack ping tip cloing tic cling bing pong clang pang clong tac boing boink cloink rattle clock toc clink tuc |
abcdefghijklmnopqrstuvwxyz |
| Sample Input 2 | Sample Output 2 |
|---|---|
14 bump tip whack bump clock clank pong boink whack pang tip tuc tuc clank |
I want pizza |
| Sample Input 3 | Sample Output 3 |
|---|---|
10 dink pong clang whack bump click thumb clank pang boing |
NO cAPS |
