以下页面来自日本信息收集官方发布的原题PDF,已完整保存并渲染到本地。



可复制的 PDF 提取文本
第8回日本情報オリンピック本選問題1
2009年2月8日
受験生への注意事項
• 試験開始の指示のあるまで, 問題が入った封筒を開けないで下さい.
• 問題は5 問, 試験時間は4 時間(10 時~14 時)です.
• 提出方法や注意事項はoverview sheet に記述されています.
• まず,cygwin のhome directory
/home/[受験番号] (C:¥cygwin¥home¥[受験番号])
にあるjoi2009.exe を実行してください.パスワードは
AmGHtN4@
です.
• 前項の処理を行うとhome directory にjoi2009 というdirectory が作成され,そ
の下に2009-ho-t1, 2009-ho-t2, 2009-ho-t3, 2009-ho-t4, 2009-ho-t5 の5
つのdirectory が作成されます.解答はこれらのdirectory で,overview sheet の
指示に従い行ってください.また,これらのdirectory には,各問の
– 入力データ例とその入力に対する正解出力データ
(いくつかの入力データ例には,対応する正解出力データはありません.)
– 採点時と同じ方法でコンパイルするスクリプト
– 上のスクリプトでコンパイルしたプログラムを,指定した入力データ例
に対して実行するスクリプト
– 上のスクリプトでコンパイルしたプログラムを,指定した入力データ例
に対して実行しその出力を正解と比較するスクリプト
があります.
情報オリンピック日本委員会
1Copyright c⃝2009 The Japanese Committee for International Olympiad in Informatics
著作権は情報オリンピック日本委員会に帰属します.
1 IOIOI
問題
整数n (1 ≦n) に対し,n + 1 個のI とn 個のO をI から始めて交互に並べてでき
る文字列をPn とする.ここでI とO はそれぞれ英大文字のアイとオーである.
P1 IOI
P2 IOIOI
P3 IOIOIOI
... ...
Pn IOIOIO| {z· · · OI}
O がn 個
図1-1 本問で考える文字列Pn
整数n と,I とO のみからなる文字列s が与えられた時,s の中にPn が何ヶ所含ま
れているかを出力するプログラムを作成せよ.
例
n が1,s がOOIOIOIOIIOII の場合,P1 はIOI であり,下図1-2 に示した4ヶ所に
含まれている.よって,出力は4 である.
OOIOIOIOIIOII
OOIOIOIOIIOII
OOIOIOIOIIOII
OOIOIOIOIIOII
図1-2 n が1,s がOOIOIOIOIIOII の場合の例
n が2,s がOOIOIOIOIIOII の場合,P2 はIOIOI であり,下図1-3 に示した2ヶ所
に含まれている.よって,出力は2 である.
OOIOIOIOIIOII
OOIOIOIOIIOII
図1-3 n が2,s がOOIOIOIOIIOII の場合の例
問題1-1
入力
入力ファイルのファイル名はinput.txt である.
1 行目には整数n (1 ≦n ≦1000000) が書かれている.
2 行目には整数m (1 ≦m ≦1000000) が書かれている.m はs の文字数を表す.
3 行目には文字列s が書かれている.s はI とO のみからなる.
全ての採点用データで,2n + 1 ≦m である.採点用データのうち, 配点の50% 分
については, n ≦100, m ≦10000 を満たす.
出力
出力ファイルのファイル名はoutput.txt である.
output.txt は,文字列s に文字列Pn が何ヶ所含まれるかを表す1 つの整数を含
む1 行からなる.
s にPn が含まれていない場合は,整数として0 を出力せよ.
入出力の例
例1 例2
input.txt input.txt
1 2
13 13
OOIOIOIOIIOII OOIOIOIOIIOII
output.txt output.txt
4 2
問題1-2