1511D.md (1116B)
1 Source: https://codeforces.com/problemset/problem/1511/D 2 3 D. Min Cost String 4 5 time limit per test 6 7 2 seconds 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 Let's define the cost of a string $s$ as the number of index pairs $i$ and $j$ ($1 \le i \lt j \lt |s|$) such that $s_i = s_j$ and $s_{i+1} = s_{j+1}$. 22 23 You are given two positive integers $n$ and $k$. Among all strings with length $n$ that contain only the first $k$ characters of the Latin alphabet, find a string with minimum possible cost. If there are multiple such strings with minimum cost — find any of them. 24 25 Input 26 27 The only line contains two integers $n$ and $k$ ($1 \le n \le 2 \cdot 10^5; 1 \le k \le 26$). 28 29 Output 30 31 Print the string $s$ such that it consists of $n$ characters, each its character is one of the $k$ first Latin letters, and it has the minimum possible cost among all these strings. If there are multiple such strings — print any of them. 32 33 Examples 34 35 Input 36 37 ``` 38 9 4 39 ``` 40 41 Output 42 43 ``` 44 aabacadbb 45 ``` 46 47 Input 48 49 ``` 50 5 1 51 ``` 52 53 Output 54 55 ``` 56 aaaaa 57 ``` 58 59 Input 60 61 ``` 62 10 26 63 ``` 64 65 Output 66 67 ``` 68 codeforces 69 ```