문제2645--Inverse Move-to-Front Transform

2645: Inverse Move-to-Front Transform

실행시간 제한: 1 Sec  메모리사용 제한: 128 MB
제출: 2  통과: 2
[제출] [채점기록] [묻고답하기]

문제 설명

The Move-to-Front (MTF) transform is an encoding scheme which maps the input data into
a sequence of numbers. Entropy encoding schemes often achieve better compression ratio on
the data encoded by the MTF transform. The MTF transform is quite simple. The following
scheme is the MTF transform on string consisting of only characters in lowercase.
1. Maintain a list of characters in lowercase. Initially, the list is sorted in the lexicographic
order. I.e., the list is [abcdefghijklmnopqrstuvwxyz] at the beginning.
2. Read a character ↵ from the string. Output the index of ↵ in the list, then move ↵ to the
front of the list.
3. Repeat the previous step until all characters in the string are read.
For example, the following is how the transform above works on the string hakka.
1. The first character h has index 7 in [abcdefghijklmnopqrstuvwxyz]. Output 7, then
move h to the front of the list.
2. The second character a has index 1 in [habcdefgijklmnopqrstuvwxyz]. Output 1, then
move a to the front of the list.
3. The third character k has index 10 in [ahbcdefgijklmnopqrstuvwxyz]. Output 10, then
move k to the front of the list.
4. The fourth character k has index 0 in [kahbcdefgijlmnopqrstuvwxyz]. Output 0, then
move k to the front of the list.
5. The fourth character a has index 1 in [kahbcdefgijlmnopqrstuvwxyz]. Output 1, then
move a to the front of the list.
The MTF transform maps hakka into the sequence (7, 1, 10, 0, 1). Please write a program
to inverse the MTF transform. In other words, your program reads a sequence of numbers
($a_1$, $\dots$ ,$a_n$), then compute the string s such that the MTF transform maps s into ($a_1$, $\dots$ ,$a_n$),

입력 설명

The first line of the input contains an integer $T$, $T \leq 50$, which indicates the number of
test cases. Each test case consists of two lines. The first one contains a positive integer $n$,
$1 \leq n \leq 100$, which indicates the length of the sequence. The second line contains $n$ integers
$a_1$, $\dots$ ,$a_n$ separated by blanks. The input sequence is ($a_1$, $\dots$ ,$a_n$), and $a_i$  {$0 \leq a_i \leq 25$} for
$i$ ($1 \leq i \leq n$)

출력 설명

For each test case, output the string s such that the MTF transform maps s into ($a_1$, $\dots$ ,$a_n$).

입력 예시 Copy

3
5
7 1 10 0 1
6
1 1 13 1 1 1
8
7 1 1 1 20 4 0 1

출력 예시 Copy

hakka
banana
hahauccu

출처/분류