CF1411E.Poman Numbers
提高+/省选-
通过率:0%
时间限制:1.00s
内存限制:256MB
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
You've got a string S consisting of n lowercase English letters from your friend. It turned out that this is a number written in poman numerals. The poman numeral system is long forgotten. All that's left is the algorithm to transform number from poman numerals to the numeral system familiar to us. Characters of S are numbered from 1 to n from left to right. Let's denote the value of S as f(S), it is defined as follows:
- If ∣S∣>1, an arbitrary integer m (1≤m<∣S∣) is chosen, and it is defined that f(S)=−f(S[1,m])+f(S[m+1,∣S∣]), where S[l,r] denotes the substring of S from the l-th to the r-th position, inclusively.
- Otherwise S=c, where c is some English letter. Then f(S)=2pos(c), where pos(c) is the position of letter c in the alphabet (pos(a)=0, pos(z)=25).
Note that m is chosen independently on each step.
Your friend thinks it is possible to get f(S)=T by choosing the right m on every step. Is he right?
你从朋友那里得到了一个由 n 个小写英文字母组成的字符串 S。原来,这是一个用波曼(poman)数字系统表示的数。波曼数字系统早已被遗忘,目前仅存一种将波曼数字转换为我们所熟悉的数字系统的算法。字符串 S 的字符从左到右编号为 1 到 n。我们用 f(S) 表示 S 的值,其定义如下:
- 若 ∣S∣>1,则任选一个整数 m(满足 1≤m<∣S∣),并定义 f(S)=−f(S[1,m])+f(S[m+1,∣S∣]),其中 S[l,r] 表示 S 中从第 l 个位置到第 r 个位置(含端点)的子串;
- 否则 S=c,其中 c 是某个英文字母,此时 f(S)=2pos(c),而 pos(c) 表示字母 c 在英文字母表中的位置(即 pos(a)=0,pos(z)=25)。
注意:每一步中 m 的选取是相互独立的。
你的朋友认为,只要在每一步都恰当地选择 m,就一定能使得 f(S)=T。他的说法正确吗?
输入格式
The first line contains two integers n and T (2≤n≤105, −1015≤T≤1015).
The second line contains a string S consisting of n lowercase English letters.
第一行包含两个整数 n 和 T(2≤n≤105,−1015≤T≤1015)。
第二行包含一个由 n 个小写英文字母组成的字符串 S。
输出格式
Print "Yes" if it is possible to get the desired value. Otherwise, print "No".
You can print each letter in any case (upper or lower).
如果可以得到目标值,则输出“Yes”;否则输出“No”。
您可以以任意大小写(大写或小写)输出每个字母。
输入输出样例
输入#1
2 -1 ba
输出#1
Yes
输入#2
3 -7 abc
输出#2
No
输入#3
7 -475391 qohshra
输出#3
Yes
说明/提示
In the second example, you cannot get −7. But you can get 1, for example, as follows:
- First choose m=1, then f(abc)=−f(a)+f(bc)
- f(a)=20=1
- f(bc)=−f(b)+f(c)=−21+22=2
- In the end f(abc)=−1+2=1
在第二个例子中,你无法得到 −7。但你可以得到 1,例如,按如下步骤进行:
- 首先选择 m=1,则 f(abc)=−f(a)+f(bc)
- f(a)=20=1
- f(bc)=−f(b)+f(c)=−21+22=2
- 最终 f(abc)=−1+2=1
输入解题思路,AI测评打分。不知道怎么写?