logo AlgoBeat OnlineJudge
登录 注册

#214389. [ROI 2013 Day1] 装配机器人

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

某高校的学生设计了一款机器人,用于部分自动化航空发动机的装配过程。

在发动机装配过程中可能遇到 26 种类型的操作,用小写拉丁字母表示。装配过程由 个操作组成。计划使用机器人一次来执行装配过程中部分连续的操作。

机器人的内存由 个单元组成,每个单元存储一个操作。操作按顺序执行,从第一个操作开始,按照它们在内存中的排列顺序进行。执行完最后一个操作后,机器人会从第一个操作继续工作。机器人可以在执行任意数量的操作后停止。如果机器人执行了至少 个操作,则机器人的使用在经济上是合理的。

需要编写一个程序,根据给定的装配过程确定机器人在经济上合理的使用方式数量。

输入格式

输入文件的第一行写有数字 )——可以写入机器人内存的操作数量。

第二行由 )个小写拉丁字母组成,表示操作——即发动机的装配过程。相同类型的操作用相同的字母表示。

输出格式

输出文件应包含一个整数——机器人在经济上合理的使用方式数量。

样例

样例输入 1

2
zabacabab

样例输出 1

5

样例输入 2

2
abc

样例输出 2

0

数据范围与提示

说明

在第一个样例中,以下操作序列使用机器人在经济上是合理的:

  • 第 2 到第 4 个操作:aba,此时机器人内存中的操作为 ab
  • 第 4 到第 6 个操作:aca,机器人内存中的操作为 ac
  • 第 6 到第 8 个操作:aba,机器人内存中的操作为 ab
  • 第 6 到第 9 个操作:abab,机器人内存中的操作为 ab
  • 第 7 到第 9 个操作:bab,机器人内存中的操作为 ba

评分

本题包含三个子任务。每个子任务的评分使用独立的测试组。仅当通过相应组的所有测试时,子任务的得分才会被计入。

子任务 1

。 该子任务分值为 30 分。

子任务 2

。 该子任务分值为 30 分。

子任务 3

。 该子任务分值为 40 分。