102274: [AtCoder]ABC227 E - Swap

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

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

Input

题意翻译

给定一个字符串 $S$ 和一个非负整数 $K$,求从 $S$ 开始至多进行 $K$ 次相邻字符的交换,可以生成多少种不同的字符串。 $2\le |S|\le 30$,$0\le K\le 10^9$,$S$ 只包含字符 `K`、`E`、`Y`。

Output

得分:500分

问题描述

给定一个由KEY组成的字符串$S$。

在最多进行$K$次相邻字符交换的情况下,可以得到多少个字符串?

限制条件

  • $2 \leq |S| \leq 30$
  • $0 \leq K \leq 10^9$
  • $S$由KEY组成。

输入

从标准输入以以下格式获取输入:

$S$
$K$

输出

打印答案。


样例输入1

KEY
1

样例输出1

3

在最多进行一次交换的情况下,可以得到三个字符串:KEYEKYKYE


样例输入2

KKEE
2

样例输出2

4

在最多进行两次交换的情况下,可以得到四个字符串:KKEEKEKEEKKEKEEK


样例输入3

KKEEYY
1000000000

样例输出3

90

加入题单

上一题 下一题 算法标签: