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:

  1. The string consists of n lowercase English letters (that is, the string's length equals n), exactly k of these letters are distinct.
  2. 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).
  3. 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 非常喜爱字符串,而他最钟爱长度为 nn 的字符串。

某天,他想找出一个满足以下条件的字符串:

  1. 该字符串由 nn 个小写英文字母组成(即字符串长度为 nn),其中恰好有 kk 个互不相同的字母;
  2. 字符串中任意两个相邻字母均不相同;即若将字符串表示为 s=s1s2…sns = s_1 s_2 \dots s_n,则对所有 1≤i<n1 \le i < n,均有 si≠si+1s_i \ne s_{i+1};
  3. 在所有满足条件 1 和 2 的字符串中,所求字符串是字典序最小的。

请帮助他找到这样的字符串,或判断这样的字符串不存在。

字符串 x=x1x2…xpx = x_1 x_2 \dots x_p 在字典序上小于字符串 y=y1y2…yqy = y_1 y_2 \dots y_q,当且仅当满足下列条件之一:

  • p<qp < q,且 x1=y1, x2=y2, …, xp=ypx_1 = y_1,\, x_2 = y_2,\, \dots,\, x_p = y_p;
  • 或存在某个数 rr(满足 r<pr < p 且 r<qr < q),使得 x1=y1, x2=y2, …, xr=yrx_1 = y_1,\, x_2 = y_2,\, \dots,\, x_r = y_r,且 xr+1<yr+1x_{r+1} < y_{r+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.

一行包含两个正整数 nn 和 kk(1 ≤ n ≤ 1061 ≤ n ≤ 10^6,1 ≤ k ≤ 261 ≤ 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测评打分。不知道怎么写?

首页