시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 256 MB3883310814881129.746%

문제

N+1개의 I와 N개의 O로 이루어져 있으면, IO이 교대로 나오는 문자열을 PN이라고 한다.

  • P1 IOI
  • P2 IOIOI
  • P3 IOIOIOI
  • PN IOIOI...OI (O가 N개)

IO로만 이루어진 문자열 S와 정수 N이 주어졌을 때, S안에 PN이 몇 군데 포함되어 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. 둘째 줄에는 S의 길이 M이 주어지며, 셋째 줄에 S가 주어진다.

출력

S에 PN이 몇 군데 포함되어 있는지 출력한다.

제한

  • 1 ≤ N ≤ 1,000,000
  • 2N+1 ≤ M ≤ 1,000,000
  • S는 IO로만 이루어져 있다.

서브태스크

번호배점제한
150

N ≤ 100, M ≤ 10 000.

250

추가적인 제약 조건이 없다.

예제 입력 1

1
13
OOIOIOIOIIOII

예제 출력 1

4
  • OOIOIOIOIIOII
  • OOIOIOIOIIOII
  • OOIOIOIOIIOII
  • OOIOIOIOIIOII

예제 입력 2

2
13
OOIOIOIOIIOII

예제 출력 2

2
  • OOIOIOIOIIOII
  • OOIOIOIOIIOII
W3sicHJvYmxlbV9pZCI6IjU1MjUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJJT0lPSSIsImRlc2NyaXB0aW9uIjoiPHA+TisxXHVhYzFjXHVjNzU4IDxjb2RlPkk8XC9jb2RlPlx1YzY0MCBOXHVhYzFjXHVjNzU4IDxjb2RlPk88XC9jb2RlPlx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHVjNzNjXHViYTc0LCA8Y29kZT5JPFwvY29kZT5cdWM2NDAgPGNvZGU+TzxcL2NvZGU+XHVjNzc0IFx1YWQ1MFx1YjMwMFx1Yjg1YyBcdWIwOThcdWM2MjRcdWIyOTQgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzQ0IFA8c3ViPk48XC9zdWI+XHVjNzc0XHViNzdjXHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5QPHN1Yj4xPFwvc3ViPiA8Y29kZT5JT0k8XC9jb2RlPjxcL2xpPlxyXG5cdDxsaT5QPHN1Yj4yPFwvc3ViPiA8Y29kZT5JT0lPSTxcL2NvZGU+PFwvbGk+XHJcblx0PGxpPlA8c3ViPjM8XC9zdWI+IDxjb2RlPklPSU9JT0k8XC9jb2RlPjxcL2xpPlxyXG5cdDxsaT5QPHN1Yj5OPFwvc3ViPiA8Y29kZT5JT0lPSS4uLk9JPFwvY29kZT4gKDxjb2RlPk88XC9jb2RlPlx1YWMwMCBOXHVhYzFjKTxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPjxjb2RlPkk8XC9jb2RlPlx1YzY0MCA8Y29kZT5PPFwvY29kZT5cdWI4NWNcdWI5Y2MgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1YmIzOFx1Yzc5MFx1YzVmNCBTXHVjNjQwIFx1YzgxNVx1YzIxOCBOXHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFNcdWM1NDhcdWM1ZDAgUDxzdWI+TjxcL3N1Yj5cdWM3NzQgXHViYTg3IFx1YWQ3MFx1YjM3MCBcdWQzZWNcdWQ1NjhcdWI0MThcdWM1YjQgXHVjNzg4XHViMjk0XHVjOWMwIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBOXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBTXHVjNzU4IFx1YWUzOFx1Yzc3NCBNXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljMFx1YmE3MCwgXHVjMTRiXHVjOWY4IFx1YzkwNFx1YzVkMCBTXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5TXHVjNWQwIFA8c3ViPk48XC9zdWI+XHVjNzc0IFx1YmE4NyBcdWFkNzBcdWIzNzAgXHVkM2VjXHVkNTY4XHViNDE4XHVjNWI0IFx1Yzc4OFx1YjI5NFx1YzljMCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIiwibGltaXQiOiI8dWw+XHJcblx0PGxpPjEgJmxlOyBOICZsZTsgMSwwMDAsMDAwPFwvbGk+XHJcblx0PGxpPjJOKzEgJmxlOyBNICZsZTsgMSwwMDAsMDAwPFwvbGk+XHJcblx0PGxpPlNcdWIyOTQgPGNvZGU+STxcL2NvZGU+XHVjNjQwIDxjb2RlPk88XC9jb2RlPlx1Yjg1Y1x1YjljYyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuIiwic3VidGFzazEiOiI8cD5OICZsZTsgMTAwLCBNICZsZTsgMTAgMDAwLjxcL3A+XHJcbiIsInN1YnRhc2syIjoiPHA+XHVjZDk0XHVhYzAwXHVjODAxXHVjNzc4IFx1YzgxY1x1YzU3ZCBcdWM4NzBcdWFjNzRcdWM3NzQgXHVjNWM2XHViMmU0LjxcL3A+XHJcbiIsInNhbXBsZV9leHBsYWluXzEiOiI8dWw+XHJcblx0PGxpPjxjb2RlPk9PPHU+SU9JPFwvdT5PSU9JSU9JSTxcL2NvZGU+PFwvbGk+XHJcblx0PGxpPjxjb2RlPk9PSU88dT5JT0k8XC91Pk9JSU9JSTxcL2NvZGU+PFwvbGk+XHJcblx0PGxpPjxjb2RlPk9PSU9JTzx1PklPSTxcL3U+SU9JSTxcL2NvZGU+PFwvbGk+XHJcblx0PGxpPjxjb2RlPk9PSU9JT0lPSTx1PklPSTxcL3U+STxcL2NvZGU+PFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJzYW1wbGVfZXhwbGFpbl8yIjoiPHVsPlxyXG5cdDxsaT48Y29kZT5PTzx1PklPSU9JPFwvdT5PSUlPSUk8XC9jb2RlPjxcL2xpPlxyXG5cdDxsaT48Y29kZT5PT0lPPHU+SU9JT0k8XC91PklPSUk8XC9jb2RlPjxcL2xpPlxyXG48XC91bD5cclxuIn0seyJwcm9ibGVtX2lkIjoiNTUyNSIsInByb2JsZW1fbGFuZyI6IjIiLCJ0aXRsZSI6IklPSU9JIChJT0lPSSkiLCJkZXNjcmlwdGlvbiI6IjxwPjEgXHU0ZWU1XHU0ZTBhXHUzMDZlXHU2NTc0XHU2NTcwIE4gXHUzMDZiXHU1YmZlXHUzMDU3XHVmZjBjTiArIDEgXHU1MDBiXHUzMDZlIDxjb2RlPkk8XC9jb2RlPiBcdTMwNjggTiBcdTUwMGJcdTMwNmUgPGNvZGU+TzxcL2NvZGU+IFx1MzA5MiA8Y29kZT5JPFwvY29kZT4gXHUzMDRiXHUzMDg5XHU1OWNiXHUzMDgxXHUzMDY2XHU0ZWE0XHU0ZTkyXHUzMDZiXHU0ZTI2XHUzMDc5XHUzMDY2XHUzMDY3XHUzMDRkXHUzMDhiXHU2NTg3XHU1YjU3XHU1MjE3XHUzMDkyIFA8c3ViPk48XC9zdWI+IFx1MzA2OFx1MzA1OVx1MzA4Ylx1ZmYwZVx1MzA1M1x1MzA1M1x1MzA2NyA8Y29kZT5JPFwvY29kZT4gXHUzMDY4IDxjb2RlPk88XC9jb2RlPiBcdTMwNmZcdTMwNWRcdTMwOGNcdTMwNWVcdTMwOGNcdTgyZjFcdTU5MjdcdTY1ODdcdTViNTdcdTMwNmVcdTMwYTJcdTMwYTRcdTMwNjhcdTMwYWFcdTMwZmNcdTMwNjdcdTMwNDJcdTMwOGJcdWZmMGU8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5QPHN1Yj4xPFwvc3ViPiZuYnNwOzxjb2RlPklPSTxcL2NvZGU+PFwvbGk+XHJcblx0PGxpPlA8c3ViPjI8XC9zdWI+Jm5ic3A7PGNvZGU+SU9JT0k8XC9jb2RlPjxcL2xpPlxyXG5cdDxsaT5QPHN1Yj4zPFwvc3ViPiZuYnNwOzxjb2RlPklPSU9JPFwvY29kZT48XC9saT5cclxuXHQ8bGk+UDxzdWI+TjxcL3N1Yj4mbmJzcDs8Y29kZT5JT0lPSS4uLk9JPFwvY29kZT4gKDxjb2RlPk88XC9jb2RlPiBcdTMwNGMgTiBcdTUwMGIpPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+XHU2NTc0XHU2NTcwIE4gXHUzMDY4XHVmZjBjSSBcdTMwNjggTyBcdTMwNmVcdTMwN2ZcdTMwNGJcdTMwODlcdTMwNmFcdTMwOGJcdTY1ODdcdTViNTdcdTUyMTcgUyBcdTMwNGNcdTRlMGVcdTMwNDhcdTMwODlcdTMwOGNcdTMwNWZcdTMwNjhcdTMwNGRcdWZmMGNTIFx1MzA2ZVx1NGUyZFx1MzA2YiBQPHN1Yj5OPFwvc3ViPiBcdTMwNGNcdTRmNTVcdTMwZjZcdTYyNDBcdTU0MmJcdTMwN2VcdTMwOGNcdTMwNjZcdTMwNDRcdTMwOGJcdTMwNGJcdTMwOTJcdTZjNDJcdTMwODFcdTMwOGJcdTMwZDdcdTMwZWRcdTMwYjBcdTMwZTlcdTMwZTBcdTMwOTJcdTRmNWNcdTYyMTBcdTMwNWJcdTMwODhcdWZmMGU8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPjxzcGFuIHN0eWxlPVwibGluZS1oZWlnaHQ6MS42ZW1cIj5cdTZhMTlcdTZlOTZcdTUxNjVcdTUyOWJcdTMwNGJcdTMwODlcdTRlZTVcdTRlMGJcdTMwNmVcdTMwYzdcdTMwZmNcdTMwYmZcdTMwOTJcdThhYWRcdTMwN2ZcdThmYmNcdTMwODFcdWZmMGU8XC9zcGFuPjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPjEgXHU4ODRjXHU3NmVlXHUzMDZiXHUzMDZmXHU2NTc0XHU2NTcwIE4gXHUzMDRjXHU2NmY4XHUzMDRiXHUzMDhjXHUzMDY2XHUzMDQ0XHUzMDhiXHVmZjBlPFwvbGk+XHJcblx0PGxpPjIgXHU4ODRjXHU3NmVlXHUzMDZiXHUzMDZmXHU2NTc0XHU2NTcwIE0gXHUzMDRjXHU2NmY4XHUzMDRiXHUzMDhjXHUzMDY2XHUzMDQ0XHUzMDhiXHVmZjBlXHUzMDUzXHUzMDhjXHUzMDZmXHVmZjBjXHU1MTY1XHU1MjliXHUzMDY4XHUzMDU3XHUzMDY2XHU0ZTBlXHUzMDQ4XHUzMDg5XHUzMDhjXHUzMDhiXHU2NTg3XHU1YjU3XHU1MjE3IFMgXHUzMDZlXHU5NTc3XHUzMDU1XHUzMDRjIE0gXHUzMDY3XHUzMDQyXHUzMDhiXHUzMDUzXHUzMDY4XHUzMDkyXHU4ODY4XHUzMDU5XHVmZjBlPFwvbGk+XHJcblx0PGxpPjMgXHU4ODRjXHU3NmVlXHUzMDZiXHUzMDZmXHU5NTc3XHUzMDU1IE0gXHUzMDZlXHU2NTg3XHU1YjU3XHU1MjE3IFMgXHUzMDRjXHU2NmY4XHUzMDRiXHUzMDhjXHUzMDY2XHUzMDQ0XHUzMDhiXHVmZjBlPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJvdXRwdXQiOiI8cD5cdTZhMTlcdTZlOTZcdTUxZmFcdTUyOWJcdTMwNmJcdWZmMGNcdTY1ODdcdTViNTdcdTUyMTcgUyBcdTMwNmJcdTY1ODdcdTViNTdcdTUyMTcgUDxzdWI+TjxcL3N1Yj4gXHUzMDRjXHU0ZjU1XHUzMGY2XHU2MjQwXHU1NDJiXHUzMDdlXHUzMDhjXHUzMDY2XHUzMDQ0XHUzMDhiXHUzMDRiXHUzMDkyXHU4ODY4XHUzMDU5XHU2NTc0XHU2NTcwXHUzMDkyIDEgXHU4ODRjXHUzMDY3XHU1MWZhXHU1MjliXHUzMDViXHUzMDg4LiBcdTMwODJcdTMwNTcgUyBcdTMwNmIgUDxzdWI+TjxcL3N1Yj5cdTMwNGNcdTU0MmJcdTMwN2VcdTMwOGNcdTMwNjZcdTMwNDRcdTMwNmFcdTMwNDRcdTU4MzRcdTU0MDhcdTMwNmZcdWZmMGMwIFx1MzA5Mlx1NTFmYVx1NTI5Ylx1MzA1Ylx1MzA4OFx1ZmYwZTxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkphcGFuZXNlIiwibGltaXQiOiI8dWw+XHJcblx0PGxpPjEgJmxlOyBOICZsZTsgMSAwMDAgMDAwXHVmZjBlPFwvbGk+XHJcblx0PGxpPjJOICsgMSAmbGU7IE0gJmxlOyAxIDAwMCAwMDBcdWZmMGU8XC9saT5cclxuXHQ8bGk+XHU2NTg3XHU1YjU3XHU1MjE3IFMgXHUzMDZmIDxjb2RlPkk8XC9jb2RlPiBcdTMwNjggPGNvZGU+TzxcL2NvZGU+IFx1MzA2ZVx1MzA3Zlx1MzA0Ylx1MzA4OVx1MzA2YVx1MzA4Ylx1ZmYwZTxcL2xpPlxyXG48XC91bD5cclxuIiwic3VidGFzazEiOiI8cD5OICZsZTsgMTAwLCBNICZsZTsgMTAgMDAwLjxcL3A+XHJcbiIsInN1YnRhc2syIjoiPHA+XHU4ZmZkXHU1MmEwXHUzMDZlXHU1MjM2XHU5NjUwXHUzMDZmXHUzMDZhXHUzMDQ0XHVmZjBlPFwvcD5cclxuIiwic2FtcGxlX2V4cGxhaW5fMSI6IjxwPlA8c3ViPjE8XC9zdWI+IFx1MzA2ZiA8Y29kZT5JT0k8XC9jb2RlPiBcdTMwNjdcdTMwNDJcdTMwOGFcdWZmMGNcdTU2ZjMgMiBcdTMwNmJcdTc5M2FcdTMwNTdcdTMwNWYgNFx1MzBmNlx1NjI0MFx1MzA2Ylx1NTQyYlx1MzA3ZVx1MzA4Y1x1MzA2Nlx1MzA0NFx1MzA4Ylx1ZmYwZVx1MzA4OFx1MzA2M1x1MzA2Nlx1ZmYwY1x1NTFmYVx1NTI5Ylx1MzA2ZiA0IFx1MzA2N1x1MzA0Mlx1MzA4Ylx1ZmYwZTxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPjxjb2RlPk9PPHU+SU9JPFwvdT5PSU9JSU9JSTxcL2NvZGU+PFwvbGk+XHJcblx0PGxpPjxjb2RlPk9PSU88dT5JT0k8XC91Pk9JSU9JSTxcL2NvZGU+PFwvbGk+XHJcblx0PGxpPjxjb2RlPk9PSU9JTzx1PklPSTxcL3U+SU9JSTxcL2NvZGU+PFwvbGk+XHJcblx0PGxpPjxjb2RlPk9PSU9JT0lPSTx1PklPSTxcL3U+STxcL2NvZGU+PFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+XHU1NmYzIDIgTiA9IDFcdWZmMGNTIFx1MzA0YyA8Y29kZT5PT0lPSU9JT0lJT0lJPFwvY29kZT4gXHUzMDZlXHU1ODM0XHU1NDA4XHUzMDZlXHU0ZjhiPFwvcD5cclxuIiwic2FtcGxlX2V4cGxhaW5fMiI6IjxwPlA8c3ViPjI8XC9zdWI+IFx1MzA2ZiA8Y29kZT5JT0lPSTxcL2NvZGU+IFx1MzA2N1x1MzA0Mlx1MzA4YVx1ZmYwY1x1NTZmMyAzIFx1MzA2Ylx1NzkzYVx1MzA1N1x1MzA1ZiAyXHUzMGY2XHU2MjQwXHUzMDZiXHU1NDJiXHUzMDdlXHUzMDhjXHUzMDY2XHUzMDQ0XHUzMDhiXHVmZjBlXHUzMDg4XHUzMDYzXHUzMDY2XHVmZjBjXHU1MWZhXHU1MjliXHUzMDZmIDIgXHUzMDY3XHUzMDQyXHUzMDhiXHVmZjBlPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+PGNvZGU+T088dT5JT0lPSTxcL3U+T0lJT0lJPFwvY29kZT48XC9saT5cclxuXHQ8bGk+PGNvZGU+T09JTzx1PklPSU9JPFwvdT5JT0lJPFwvY29kZT48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5cdTU2ZjMgMyBOID0gMlx1ZmYwY1MgXHUzMDRjIDxjb2RlPk9PSU9JT0lPSUlPSUk8XC9jb2RlPiBcdTMwNmVcdTU4MzRcdTU0MDhcdTMwNmVcdTRmOGI8XC9wPlxyXG4ifV0=

출처

Olympiad > Japanese Olympiad in Informatics > JOI 2012/2013 P4번

Olympiad > Japanese Olympiad in Informatics > JOI 2008/2009 1번

Olympiad > Japanese Olympiad in Informatics > JOI 2013/2014 P4번

채점 및 기타 정보

  • 예제는 채점하지 않는다.