Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
K
, E
, Y
のみからなる文字列 S が与えられます。
S の隣接する 2 文字を入れ替える操作を K 回まで行えるとき、作ることができる文字列は何種類ありますか?
制約
- 2 \leq |S| \leq 30
- 0 \leq K \leq 10^9
- S は
K
,E
,Y
のみからなる
入力
入力は以下の形式で標準入力から与えられる。
S K
出力
答えを出力せよ。
入力例 1
KEY 1
出力例 1
3
KEY
に対して 1 回以下の操作を行うことで得られる文字列は KEY
, EKY
, KYE
の 3 種類です。
入力例 2
KKEE 2
出力例 2
4
KKEE
に対して 2 回以下の操作を行うことで得られる文字列は KKEE
, KEKE
, EKKE
, KEEK
の 4 種類です。
入力例 3
KKEEYY 1000000000
出力例 3
90
Score : 500 points
Problem Statement
Given is a string S consisting of K
, E
, Y
.
How many strings are there that can be obtained with at most K swaps of two adjacent characters in S?
Constraints
- 2 \leq |S| \leq 30
- 0 \leq K \leq 10^9
- S consists of
K
,E
,Y
.
Input
Input is given from Standard Input in the following format:
S K
Output
Print the answer.
Sample Input 1
KEY 1
Sample Output 1
3
With at most one swap, there are three strings that can be obtained: KEY
, EKY
, KYE
.
Sample Input 2
KKEE 2
Sample Output 2
4
With at most two swaps, there are four strings that can be obtained: KKEE
, KEKE
, EKKE
, KEEK
.
Sample Input 3
KKEEYY 1000000000
Sample Output 3
90