Informatica Online Judge

  문자열 IOI [0979 / 03D3]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 41   Total Tried : 48


The Champion of this Problem (C++) : gs15120 - 0ms / 1365byte
My Best Submission (C++) : N/A

[JOI 2014 Practice]

Background

1이상 정수 N에 대해서 N+1개의 "I"와 N개의 "O"를 "I"로부터 시작하여 반복하여 나열한 문자열을 Pn이라고 한다.

예를 들어

P1 = "IOI"
P2 = "IOIOI"
:
Pn = "IOIOI...IOI" (O가 N개)

정수 N과 "I"와 "O"로 이루어진 길이가 M인 문자열 S가 주어질 때, S에서 Pn이 몇 나타나는지를 구하는 프로그램을 작성하시오.

Input

첫 번째 줄에 N이 입력된다.
두 번째 줄에 M이 입력된다.
세 번째 줄에 길이가 M인 문자열 S가 입력된다.

[입력값의 정의역]
1 <= N <= 1,000,000
2N+1 <= M <= 1,000,000

[부분 문제]
sub-task #1 : N은 100이하, M은 10,000이하의 값이다. (50%)
sub-task #2 : 문제의 제한조건 한계값까지 입력된다. (50%)

Output

문자열 S에서 Pn이 나타나는 횟수를 출력한다.

IO Example

입력
1
13
OOIOIOIOIIOII

출력
4

[해설]
OOIOIOIOIIOII
OOIOIOIOIIOII
OOIOIOIOIIOII
OOIOIOIOIIOII

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]