时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 512 M,其他语言1024 M
64bit IO Format: %lld
题目描述
小王是一名热爱编程竞赛的学生,尤其痴迷于 Codeforces 平台上的比赛(简称 CF)。然而他的老师为了让他专心学习,布置了大量作业任务。这些作业被编码为由四种字符组成的字符串:`c`、`f`、`z`、`y`。
其中:
- `c` 和 `f` 代表 Codeforces 比赛,是小王的最爱;
- `z` 和 `y` 代表作业任务,是小王最讨厌的部分。
每当小王看到 CF 相关的字符组合时就会精力充沛,而看到作业相关的字符组合时就会疲惫不堪。现在,我们需要计算小王完成所有作业时的精力变化情况。
作业序列是一个c、f、z、y 组成的字符串

。小王按照字符串的顺序依次完成每一项任务。假设小王的 初始精力值为

,已经完成的所有任务构成的字符串为

,则小王当前的精力值为h+(s′中cf子序列的 数量)−(s′中 zy 子序列的数量) 。 子序列是指从一个原始序列中通过去除某些元素而不改变剩余元素的相对顺序所形成的新序列。 初始精力值

为

。如果在任何时候精力值变为负数,则任务失败。对于每组数据,判断小王是否能完成任务;如果不能,计算至少需要多少初始精力才能完成任务.
子序列为从原字符串中删除任意个(可以为零、可以为全部)字符得到的新字符串。
输入描述:
每个测试文件包含
组测试数据,测试文件的第一行输入
(
)。
对于每组测试数据:
输入一行一个由c、f、z、y组成的字符串
(
)。
数据保证每个测试文件有
。
输出描述:
对于每组数据:
- 如果可以完成任务,输出 YES;
- 如果不能完成任务,输出 NO,并在下一行输出需要的最小初始精力值。
示例1
输入
复制
3
cfzy
zycf
cffcfcfzzyyzy
说明
对于第一组测试数据:
初始时,小王的精力值为0。
完成第一项任务后,已完成的任务为c,精力值依然为0。
完成第二项任务后,已完成的任务为cf,共出现1个cf子序列,精力值增长到1。
完成第三项任务后,精力值不变。
完成第四项任务后,已完成的任务为cfzy,共出现1个cf子序列和1个zy子序列,精力值减少到0。
过程中小王的精力值始终为非负数,因此他成功完成任务
备注: