#B. Doge改试卷

    传统题 1000ms 256MiB

Doge改试卷

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目情景

最近期末了,试卷有点多,Doge在单选题的时候,改晕了,把答题卡上的一道题的答案弄丢了,没有办法恢复原样,导致单选题和批改的答案对不上,成绩改错了。

现在为了补偿这名无辜的学生,所以决定让学生任选一个位置插入一个正确答案到自己的答题卡上,然后重新按照答案进行批改,每个正确题目加一分。

那么问题来了,应该在哪个位置加入一个正确答案,才能获得最高分,最高分又是多少?

输入格式 test.in

第一行,输入一个长度为n的字符串,表示正确答案,n不大于1000 第二行,输入一个长度为n-1的字符串,表示学生出错的试卷答案,内部可能有空白的部分没选

输出格式 test.out

两个数字,pos和score,分别表示应该在第pos个答案后插入新的正确答案,最后得分的最高分是score。如果多个插入位置pos得到的分数同为最高分,取插入位置靠前的方法。

样例

输入样例1

AAAADBCA
BBBDBCA

输出样例1

0 5

输入样例2

ABCDAAADBCA
ABCDBBDBCA

输出样例2

4 9

输入样例3

ABCD
A A

输出样例3

1 2

样例提示

对于样例1,最优解为第0个位置后插入A,最后补全的卷子为ABBBDBCA,正确情况为10001111,得分5

对于样例2,最优解为在第四个字母后插入A,补全的卷子为ABCDABBDBCA,正确情况为11111001111。起始在第四位、第五位、第六位后面加入A的得分一致,选取第四位为方案。

2022-10 国庆集训第四天

未参加
状态
已结束
规则
OI
题目
3
开始于
2022-10-6 17:00
结束于
2022-10-6 18:30
持续时间
1.5 小时
主持人
参赛人数
18