AlgoLensArena
ContestlərProblemlərOtaqlar
Vizualizator
← Məsələlər

FPC25-012.Jumbled Keys

Easy · 2 s · 256 MB

  • icpc
  • fpc
  • 2025

Georgi is a freshman, who just started his Computer Science studies in The Netherlands. Being very ambitious, he already looked at last year's exam for the Introduction to Programming course, and was concerned by how little time he had to do it. To help him complete his exam on time, Georgi has devised a brilliant new way to type – the Finger Placement Configuration (FPC). The FPC is just a new keyboard layout, where pressing any letter on his QWERTY keyboard results in a unique English letter being input. Every lowercase English letter can be typed and every key only inputs one letter.

After a rigorous day of studying and practicing with the new iteration of the keyboard layout, Georgi decides to log into one of his favourite games: Warstone – Heroes of Hearthcraft. However, he has forgotten his password. He had written his password into his password manager software, but made a mistake when doing so: he had typed the password thinking that the keyboard was in QWERTY mode, but the FPC layout was still enabled! The password can probably be recovered knowing the configuration of the keys in the FPC layout, but, being exhausted, he has completely forgotten that too. The only tool he can use is his training sheet. Each entry in the training sheet consists of a sequence of keys to press on the FPC layout, followed by the resulting word. On the verge of giving up, he desparately asks you for help in figuring out what his password was.

Giriş formatı

The input consists of:

• One line with a single integer nnn (1≤n≤10001\leq n\leq 10001≤n≤1000), the number of training words.

• nnn lines, each with two strings of equal length: the first is the sequence of keys that need to be pressed to enter a word using the FPC layout, and the second is the resulting word.

• One word, the sequence of keys that need to be pressed to obtain the password using the FPC layout.

Each word in the input has a length between 111 and 100010001000 characters and only consists of English lowercase characters (a-z).

Çıxış formatı

Output Georgi's password.

It is guaranteed that it is possible to uniquely reconstruct the original password based on the data from the training sheet.

Qeyd

Source: Freshmen Programming Contest 2025 · License: CC BY-SA 4.0 · Original: https://fpc.wisv.ch · Statement adapted for AlgoLens and shared under the same license. · 11 of the 34 original test cases (the largest) are omitted here to keep the problem lightweight.

Nümunələr

Giriş #1

2
abc acb
cbde bced
abcde

Çıxış #1

acbed

Giriş #2

1
abcdefghij amlvsioked
eabgcidehf

Çıxış #2

samolevski

Giriş #3

1
abcdefghijklmnopqrstuvwxy abcdefghijklmnopqrstuvwxz
abcdefghijklmnopqrstuvwxyz

Çıxış #3

abcdefghijklmnopqrstuvwxzy