CF288A.Polo the Penguin and Strings
普及-
通过率:0%
时间限制:2.00s
内存限制:256MB
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
Little penguin Polo adores strings. But most of all he adores strings of length n.
One day he wanted to find a string that meets the following conditions:
- The string consists of n lowercase English letters (that is, the string's length equals n), exactly k of these letters are distinct.
- No two neighbouring letters of a string coincide; that is, if we represent a string as s = _s_1_s_2... s__n, then the following inequality holds, s__i ≠ s__i + 1(1 ≤ i < n).
- Among all strings that meet points 1 and 2, the required string is lexicographically smallest.
Help him find such string or state that such string doesn't exist.
String x = _x_1_x_2... x__p is lexicographically less than string y = _y_1_y_2... y__q, if either p < q and _x_1 = _y_1, _x_2 = _y_2, ... , x__p = y__p, or there is such number r (r < p, r < q), that _x_1 = _y_1, _x_2 = _y_2, ... , x__r = y__r and x__r + 1 < y__r + 1. The characters of the strings are compared by their ASCII codes.
小企鹅 Polo 非常喜爱字符串,而他最钟爱长度为 n 的字符串。
某天,他想找出一个满足以下条件的字符串:
- 该字符串由 n 个小写英文字母组成(即字符串长度为 n),其中恰好有 k 个互不相同的字母;
- 字符串中任意两个相邻字母均不相同;即若将字符串表示为 s=s1s2…sn,则对所有 1≤i<n,均有 si=si+1;
- 在所有满足条件 1 和 2 的字符串中,所求字符串是字典序最小的。
请帮助他找到这样的字符串,或判断这样的字符串不存在。
字符串 x=x1x2…xp 在字典序上小于字符串 y=y1y2…yq,当且仅当满足下列条件之一:
- p<q,且 x1=y1,x2=y2,…,xp=yp;
- 或存在某个数 r(满足 r<p 且 r<q),使得 x1=y1,x2=y2,…,xr=yr,且 xr+1<yr+1。
字符串中字符的比较依据其 ASCII 码值。
输入格式
A single line contains two positive integers n and k (1 ≤ n ≤ 106, 1 ≤ k ≤ 26) — the string's length and the number of distinct letters.
一行包含两个正整数 n 和 k(1 ≤ n ≤ 106,1 ≤ k ≤ 26)——字符串的长度以及不同字母的个数。
输出格式
In a single line print the required string. If there isn't such string, print "-1" (without the quotes).
在一行中输出所需的字符串。如果不存在这样的字符串,则输出 -1(不带引号)。
输入输出样例
输入#1
7 4
输出#1
ababacd
输入#2
4 7
输出#2
-1
输入解题思路,AI测评打分。不知道怎么写?