prithivMLmods/Coder-Stat

1 2 3 4 5<h2>JOIOI の塔(Tower of JOIOI)</h2>6 7<p>8JOIOI の塔とは，1 人で遊ぶ円盤を使ったゲームである．9</p>10 11<p>12このゲームは，<span>J</span>，<span>O</span>，<span>I</span> のいずれかの文字が書かれたいくつかの円盤を用いて行う．円盤は直径が互いに異なり，ゲーム開始時にはこれらの円盤は直径の大きいものから順に下から上に向かって積まれている．あなたは，これらの円盤を用いて，出来るだけ多くのミニ JOIOI の塔を作りたい．ミニ JOIOI の塔とは 3 枚の円盤からなり，円盤の直径が小さいものから順に読んで <span>JOI</span> もしくは <span>IOI</span> と読めるものである．ただし，同じ円盤を2 度以上使うことはできない．13</p>14 15<center>16<img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE2_JOI2012_2012_ho_4"><br>17<p>18図: <span>JOIOII</span> からはミニ JOIOI の塔が 2 つ作れる19</p>20</center>21 22<h3>課題</h3>23 24<p>25用意された円盤に書かれた文字がそれぞれ円盤の直径が小さいものから順に長さ <var>N</var> の文字列 <var>S</var> として与えられる．これらの円盤を使って作ることのできるミニ JOIOI の塔の個数の最大値を求めるプログラムを作成せよ．26</p>27 28<h3>制限</h3>29<ul>30<li>1 &le; <var>N</var> &le; 1 000 000 &nbsp;&nbsp;&nbsp;&nbsp; 文字列 <var>S</var> の長さ</li>31</ul>32 33<h3>入力</h3>34<p>35標準入力から以下のデータを読み込め．36</p>37<ul>38<li> 1 行目には整数 <var>N</var> が書かれている．<var>N</var> は文字列 <var>S</var> の長さを表す． </li>39<li> 2 行目には文字列 <var>S</var> が書かれている．</li>40</ul>41 42<h3>出力</h3>43<p>44標準出力に，作ることのできるミニ JOIOI の塔の数の最大値を表す整数を 1 行で出力せよ．45</p>46 47<h3>入出力例</h3>48 49<h3>入力例 1</h3>50<pre>51652JOIIOI53</pre>54<h3> 出力例 1</h3>55<pre>56257</pre>58<p>59<span>JOIIOI</span> は <span>JOI</span> および <span>IOI</span> をそれぞれ 1 つずつ部分列として含んでおり，作ることのできるミニ JOIOI の塔は 2 つである．60</p>61<br>62 63 64<h3>入力例 2</h3>65<pre>66567JOIOI68</pre>69 70<h3>出力例 2</h3>71<pre>72173</pre>74<p>75部分列として <span>JOI</span> および <span>IOI</span> を含んでいるが，文字を 2 度以上使うことはできないため同時に取り出すことはできない．76</p>77<br>78 79<h3>入力例 3</h3>80<pre>81682JOIOII83</pre>84<h3> 出力例 3</h3>85<pre>86287</pre>88<p>89この入出力例は問題文中の例に対応している．90</p>91<br>92 93 94 95 96<h3>入力例 4</h3>97<pre>981599JJOIIOOJOJIOIIO100</pre>101 102<h3>出力例 4</h3>103<pre>1044105</pre>106<br>107 108 109 110 111 112 113<div class="source">114<p class="source">115問題文と自動審判に使われるデータは、<a href="http://www.ioi-jp.org">情報オリンピック日本委員会</a>が作成し公開している問題文と採点用テストデータです。116</p>117</div>118