期待已久的“国际信息奥林匹克日本编程大赛”(IJPC:IOIer日本编程大赛)终于来了。这是一项程序设计竞赛,由代表日本参加2010年加拿大和2011年泰国举办的国际信息奥林匹克竞赛(IOI)的5名选手提出问题,赛制与IOI类似,要求在5小时内解决3个问题。
让我们制作一面巨型横幅,以表达对IJPC参与者的感谢并宣传IJPC。虽然你想让它尽可能大和显眼,但如果你花太多时间制作横幅,你最终会浪费时间准备重要的比赛问题。换句话说,我想制作一个大横幅,同时又省时又省力。
顺便说一下,我手头上有一个巨大的横幅,我不知道它是用来做什么的。这面横幅极长,上面原本写着一串字符。当然,它不能直接用作IJPC的横幅,但稍微修改一下是否可以用于IJPC呢?
如果字符串“IJPC”包含在原始字符串中就好了,但这样可能行不通。需要重写一定量的文字,但由于横幅很大,重写文字的过程需要很多时间。现在,这就是该程序发挥作用的地方。让我们找到一种以尽可能少的重写来使用此横幅的方法。
課題
由大写字母组成 N 字符串 给出了 S 。S 重复将某个位置的一个字符重写为另一个字符的操作, 我希望四个字符“IJPC”出现在S 的子字符串中。从字符串中删除零个或多个任意字符得到的字符串称为原字符串的子串。
具有以下参数的过程 替换(N,S) 实施 :
- N -- 给定字符串中的字符数。N≧4 可以假设为 。
- S -- 一串大写英文字母。S 是 您也可以写 N 可以被假定为一个字符。 “IJPC”必须出现在
替换(N,S) 实施 是 您也可以写 S 的子字符串中最小重写次数必须作为返回值返回。
例
例1
N = 8,S =“IAMJAPLJ” 考虑 的情况。
在这种情况下, 创建一个S 的第 7 个或第 8 个字符重写为字符“C”, 您可以使“IJPC”出现在 S 的子字符串中。因此 必须返回 替换(N,S) 实施 是 您也可以写 1 。
例2
N = 28,S =“IOIER日本编程竞赛” 的情况。
在这种情况下 S 已包含“IJPC”作为子字符串,因此无需重写它。因此 替换(N,S) 实施 是 您也可以写 0 。
小課題
小課題 1 (50 点)
- N≤10
小課題 2 (50 点)
- N ≤ 100 000
实施细节
制限
- CPU时间限制:1秒
- 内存限制:64 MB
注意: 堆栈的大小没有固定限制。作为堆栈使用的内存包含在总内存使用量中。
接口 (API)
- 实现文件夹:ijpc/(原型: ijpc.zip)
- 参赛者实现的文件:ijpc.cpp
- 提交文件接口:ijpc.h
- 评分程序示例:grader.cpp
- 评分程序的示例输入:grader.in.1、grader.in.2、...
注意:示例评分程序按以下格式读取输入。- 1 行目: 整数 N 。
- 2 行目: 文字列 S 。
- 评分程序输出
注意:评分程序响应输入将以下内容输出到标准输出。 如果- 1 行目: 整数 X 。X 是 您也可以写 替换(N,S) 实施 是应该返回的值。
- 问题提案:JAPLJ
- 问题陈述:JAPLJ