prithivMLmods/Coder-Stat

1 2 3 4<script type="text/x-mathjax-config">5  MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }});6</script>7<script type="text/javascript" src="https://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-MML-AM_CHTML">8</script>9 10<h2>縄張り(Territory)</h2>11 12<p>13あなたは南北方向にとても長く伸びたたくさんの道路と，東西方向にとても長く伸びたたくさんの道路が交わった形をした街に住んでいる．隣り合う2 つの南北方向の道路の間隔は 1 km である．また，隣り合う 2 つの東西方向の道路の間隔も 1 km である．14</p>15 16<p>17この街には市役所が 1 つある．市役所のある交差点を $(0,0)$ と表す．この街の交差点は 2 つの整数 $i, j$ を用いて交差点 $(i, j)$ と表される．すなわち，交差点 $(i, j)$ とは，交差点 $(0,0)$ から東に $i$ km ($i < 0$ のときは西に $-i$ km)，北に $j$ km ( $j < 0$ のときは南に $-j$ km) 進んだ位置の交差点を表す．18</p>19 20<p>21市役所ではジョイ君という名の 1 匹の犬を飼っている．ジョイ君は $K$ 日間の散歩の計画を立てた．散歩の計画は以下の通りである．22</p>23 24<ul>25<li> $K$ 日のうち最初の日の朝にはジョイ君は交差点 $(0,0)$ にいる．ジョイ君は交差点 $(0,0)$ に印を付ける．$(0,0)$ 以外にはジョイ君が印を付けた交差点はない．</li>26<li> $K$ 日のそれぞれの日の昼に散歩を行う．1 日の散歩は $N$ 回のステップからなる．各ステップでは交差点から隣の交差点へと移動し，移動先に印を付ける．ジョイ君がそれぞれの日の昼にどう移動するかは日によらず一定である．</li>27<li> 昼の移動が終わった後は，現在いる交差点で次の日の朝まで寝る．</li>28</ul>29 30<p>31市役所では $K$ 日間の散歩によってできるジョイ君の縄張りについて話題になっている．4 つの交差点 $(a,b),(a + 1,b),(a + 1,b + 1),(a,b + 1)$ のいずれにもジョイ君が 1 回以上印を付けているとき，4 つの交差点で囲まれた区画はジョイ君の縄張りに属する．32</p>33 34<p>35あなたは，ジョイ君の散歩計画から，ジョイ君の縄張りに属する区画の個数を計算するプログラムを作成することとなった．36</p>37 38<p>39この街の道路はとても長く，また，南北方向にも東西方向にも十分たくさんの道路があるため，散歩の途中でジョイ君が道路の端や街の端に到達することはない．40</p>41 42<h2>課題</h2>43<p>44ジョイ君の散歩計画が与えられると，ジョイ君の縄張りに属する区画の個数を求めるプログラムを作成せよ．45</p>46 47<h2>入力</h2>48<p>49標準入力から以下の入力を読み込め．50</p>51 52<ul>53<li> 1 行目には 2 個の整数 $N, K$ が空白を区切りとして書かれている．これはそれぞれの日の散歩が $N$ 回のステップからなり，散歩計画が $K$ 日間に渡ることを表している．</li>54<li> 2 行目には長さ $N$ の文字列 $S$ が書かれている．文字列 $S$ のうち左から $p$ 文字目 $(1 \leq p \leq N)$ の文字 $C_p$ は E，N，W，S のいずれかである．これらの文字は以下のことを表す．<br>55&nbsp;&nbsp;&nbsp;&nbsp; 文字 $C_p$ が E であるならば，$p$ 番目のステップで東隣の交差点に移動することを表す．<br>56&nbsp;&nbsp;&nbsp;&nbsp; 文字 $C_p$ が N であるならば，$p$ 番目のステップで北隣の交差点に移動することを表す．<br>57&nbsp;&nbsp;&nbsp;&nbsp; 文字 $C_p$ が W であるならば，$p$ 番目のステップで西隣の交差点に移動することを表す．<br>58&nbsp;&nbsp;&nbsp;&nbsp; 文字 $C_p$ が S であるならば，$p$ 番目のステップで南隣の交差点に移動することを表す．<br>59 60ここで，交差点$(i, j)$ に対して東隣，北隣，西隣，南隣の交差点はそれぞれ，交差点 $(i + 1, j)$，交差点$(i, j + 1)$，交差点$(i - 1, j)$，交差点$(i, j - 1)$ である．61</li>62</ul>63 64<h2>出力</h2>65<p>66標準出力に，ジョイ君の縄張りに属する区画の個数を 1 行で出力せよ．67</p>68 69<h2>制限</h2>70<p>71すべての入力データは以下の条件を満たす．72</p>73<ul>74<li> $1 \leq N \leq 100 000$</li>75<li> $1 \leq K \leq 1 000 000 000$</li>76</ul>77 78 79<h2>入出力例</h2>80 81<h3>入力例1</h3>82<pre>8312 184EENWSEEESWWS85</pre>86 87<h3>出力例1</h3>88<pre>89390</pre>91 92<p>93この入力例では，散歩は 1 日間で行われる．1 日目にジョイ君は市役所から出発して下図のように移動する．黒丸はジョイ君が印を付けた交差点，白丸はジョイ君が印を付けていない交差点，二重丸は市役所のある交差点，数字は各ステップを表す．94</p>95 96 97<center>98<img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE2_JOI2015_territory1"><br>99ジョイ君の移動経路100</center>101 102<p>103入力例 1 において，下図の斜線部分で示された 3 個の区画がジョイ君の縄張りに属する．</p>104 105<center>106<img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE2_JOI2015_territory2"><br>107入力例1 におけるジョイ君の縄張り108</center>109 110<h3>入力例2</h3>111<pre>11212 2113EENWSEEESWWS114</pre>115 116<h3>出力例2</h3>117<pre>1187119</pre>120 121<p>122入力例 2 では，散歩が 2 日間に渡り行われる．それぞれの日の移動経路は入力例 1 と同一である．散歩が完了したとき，下図の斜線部分で示された 7 個の区画がジョイ君の縄張りに属する．123</p>124 125<center>126<img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE2_JOI2015_territory3"><br>127入力例2 におけるジョイ君の縄張り128</center>129 130<!--131<p>132入力例 2 は，小課題 1 および小課題 2 の制約を満たさないことに注意せよ．133</p>134-->135 136<h3>入力例3</h3>137<pre>1387 1139ENNWNNE140</pre>141 142<h3>出力例3</h3>143<pre>1440145</pre>146<p>147入力例 3 では，ジョイ君の縄張りに属する区画は存在しない．148</p>149 150<h3>入力例4</h3>151<pre>15216 5153WSESSSWWWEEENNNW154</pre>155 156<h3>出力例4</h3>157<pre>15821159</pre>160<!--161<p>162入力例 4 は，小課題1 および小課題 2 の制約を満たさないことに注意せよ．163</p>164-->165 166 167 168 169<div class="source">170<p class="source">171<a rel="license" href="http://creativecommons.org/licenses/by-sa/4.0/"><img alt="クリエイティブ・コモンズ・ライセンス" style="border-width:0" src="https://i.creativecommons.org/l/by-sa/4.0/80x15.png"/></a>172</p>173<p class="source">174<a href="https://www.ioi-jp.org/joi/2015/2016-ho/2016-ho.pdf">第15回 日本情報オリンピック本選 課題 &nbsp; 2016 年 2 月 14 日</a>175</p>176</div>177