← 返回题目列表

AtCoder · joi2009ho_a

A. IOIOI序列

中文机器翻译题面 查看原题

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

IOIOI - 原题 PDF 第 1 页
原题PDF第1页
IOIOI - 原题 PDF 第 2 页
原题PDF第2页
IOIOI - 原题 PDF 第 3 页
原题PDF第3页
可复制的 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