比赛场次 377
比赛名称 20151028a
比赛状态 已结束比赛成绩
开始时间 2017-06-02 19:00:00
结束时间 2017-06-02 22:00:00
开放分组 全部用户
注释介绍
题目名称 愉快的logo设计
输入输出 JOI.in/out
时间限制 1000 ms (1 s)
内存限制 256 MiB
测试点数 45 简单对比
用户 结果 时间 内存 得分

愉快的logo设计

★★★   输入文件:JOI.in   输出文件:JOI.out   简单对比
时间限制:1 s   内存限制:256 MiB

【题目描述】


K理事长正在思考日本信息学奥林匹克竞赛选手的应援道具的logo问题。某天,K理事长突发奇想,想要设计一个用’J’,’O’,’I’三种文字环形排列的logo,意为希望选手能从JOI中收获快乐的意思。

(注:“环形地”在日文中的表述为“円状に”,“円”读作“en”,再加上“JOI”三个字即为“enjoy”……)

如下所示,对于任意非负整数k,我们定义标号为k的JOI序列Sk为:

·S0为’J’,’O’,’I’中任一字符构成的长度为1的字符串

·S[k+1]为最初4^k个字符都是’J’,接下来的4^k个字符都是’O’,接下来的4^k个字符都是’I’,最后4^k个字符是字符串Sk的长为4^(k+1)的字符串

现在,K理事长在纸上写下了由4^K个文字构成的一个环形字符串,字符串中每个字符都是’J’,’O’,’I’中的一个。K理事长想要修改一些文字,使得得到的字符串从某个起点开始顺时针读一圈后可以得到SK。在满足条件的情况下,要求修改的文字数量最少。


【输入格式】


第一行一个正整数K,表示K理事长在纸上写下了一个长度为4^K的环状字符串。

第二行一个由’J’,’O’,’I’三个字符构成的长为4^K的字符串,表示纸上的环形字符串从某个起点出发顺时针阅读一圈得到的字符串。


【输出格式】

输出一行一个整数,表示修改文字数量的最小值。

【样例输入】

2

JJOIJJOJOIOJOOOI

【样例输出】

7

【提示】

从○标记的位置顺时针阅读一圈得到“JJJJOOOOIIIIJOIJ”,满足S2的条件,且修改文字数达到最小值7。




对于30%的数据,1<=K<=5

对于100%的数据,1<=K<=10


【来源】

在此键入。