首页 > 代码库 > codeforces 288A:Polo the Penguin and Strings

codeforces 288A:Polo the Penguin and Strings

Description

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 = s1s2... sn, then the following inequality holds, si ≠ si + 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 = x1x2... xp is lexicographically less than string y = y1y2... yq, if either p < q and x1 = y1, x2 = y2, ... , xp = yp, or there is such number r (r < p, r < q), that x1 = y1, x2 = y2, ... , xr = yr and xr + 1 < yr + 1. The characters of the strings are compared by their ASCII codes.

Input

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.

Output

In a single line print the required string. If there isn‘t such string, print "-1" (without the quotes).

Examples
Input
7 4
Output
ababacd
Input
4 7
Output
-1



正解:贪心
解题报告:
  直接每次贪心地让ab不断重复,注意特判一些细节,这题的数据好坑

 1 //It is made by jump~ 2 #include <iostream> 3 #include <cstdlib> 4 #include <cstring> 5 #include <cstdio> 6 #include <cmath> 7 #include <algorithm> 8 #include <ctime> 9 #include <vector>10 #include <queue>11 #include <map>12 #include <set>13 using namespace std;14 typedef long long LL;15 int n,k,cnt;16 17 inline int getint()18 {19        int w=0,q=0; char c=getchar();20        while((c<0 || c>9) && c!=-) c=getchar(); if(c==-) q=1,c=getchar(); 21        while (c>=0 && c<=9) w=w*10+c-0, c=getchar(); return q ? -w : w;22 }23 24 inline void work(){25     n=getint(); k=getint();26     if(k>n || (k==1 && n>1)) { printf("-1"); return ; }    27     if(k==1 && n==1) { printf("a"); return ; }28     cnt=2; k-=2;29     for(int i=1;i<=n;i++) {30     if(n-i<k) printf("%c",(char)cnt+a),cnt++;31     else {32         if(i&1) printf("a"); else printf("b");33     }34     }35 }36 37 int main()38 {39   work();40   return 0;41 }

 

codeforces 288A:Polo the Penguin and Strings