codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1384A.md (2424B)


      1 Source: https://codeforces.com/problemset/problem/1384/A
      2 
      3 A. Common Prefixes
      4 
      5 time limit per test
      6 
      7 1 second
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 The length of the longest common prefix of two strings $s = s_1 s_2 \ldots s_n$ and $t = t_1 t_2 \ldots t_m$ is defined as the maximum integer $k$ ($0 \le k \le min(n,m)$) such that $s_1 s_2 \ldots s_k$ equals $t_1 t_2 \ldots t_k$.
     22 
     23 Koa the Koala initially has $n+1$ strings $s_1, s_2, \dots, s_{n+1}$.
     24 
     25 For each $i$ ($1 \le i \le n$) she calculated $a_i$ — the length of the longest common prefix of $s_i$ and $s_{i+1}$.
     26 
     27 Several days later Koa found these numbers, but she couldn't remember the strings.
     28 
     29 So Koa would like to find some strings $s_1, s_2, \dots, s_{n+1}$ which would have generated numbers $a_1, a_2, \dots, a_n$. Can you help her?
     30 
     31 If there are many answers print any. We can show that answer always exists for the given constraints.
     32 
     33 Input
     34 
     35 Each test contains multiple test cases. The first line contains $t$ ($1 \le t \le 100$) — the number of test cases. Description of the test cases follows.
     36 
     37 The first line of each test case contains a single integer $n$ ($1 \le n \le 100$) — the number of elements in the list $a$.
     38 
     39 The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 50$) — the elements of $a$.
     40 
     41 It is guaranteed that the sum of $n$ over all test cases does not exceed $100$.
     42 
     43 Output
     44 
     45 For each test case:
     46 
     47 Output $n+1$ lines. In the $i$-th line print string $s_i$ ($1 \le |s_i| \le 200$), consisting of lowercase Latin letters. Length of the longest common prefix of strings $s_i$ and $s_{i+1}$ has to be equal to $a_i$.
     48 
     49 If there are many answers print any. We can show that answer always exists for the given constraints.
     50 
     51 Example
     52 
     53 Input
     54 
     55 ```
     56 4
     57 4
     58 1 2 4 2
     59 2
     60 5 3
     61 3
     62 1 3 1
     63 3
     64 0 0 0
     65 ```
     66 
     67 Output
     68 
     69 ```
     70 aeren
     71 ari
     72 arousal
     73 around
     74 ari
     75 monogon
     76 monogamy
     77 monthly
     78 kevinvu
     79 kuroni
     80 kurioni
     81 korone
     82 anton
     83 loves
     84 adhoc
     85 problems
     86 ```
     87 
     88 Note
     89 
     90 In the $1$-st test case one of the possible answers is $s = [aeren, ari, arousal, around, ari]$.
     91 
     92 Lengths of longest common prefixes are:
     93 
     94 * Between $\color{red}{a}eren$ and $\color{red}{a}ri$ $\rightarrow 1$
     95 * Between $\color{red}{ar}i$ and $\color{red}{ar}ousal$ $\rightarrow 2$
     96 * Between $\color{red}{arou}sal$ and $\color{red}{arou}nd$ $\rightarrow 4$
     97 * Between $\color{red}{ar}ound$ and $\color{red}{ar}i$ $\rightarrow 2$