prithivMLmods/Coder-Stat

1 2 3 4<h1>学食</h1>5 6<p>7今日はＺ大学のオープンキャンパスです。毎年この日の昼休みには、大勢の高校生たちが学食に列をつくります。そこでＺ大学の事務局は、行列の長さが最大でどのくらいの距離になるかを予測することにしました。事前調査の結果で、以下のことが分かっています。8</p>9 10<ul>11<li> 行列にはそれぞれ 1 から <var>N</var> までの番号が振られた <var>N</var> 人が並びます。</li>12<li> <var>C</var> 個の高校生のペア (<var>a<sub>i</sub></var>, <var>b<sub>i</sub></var>) それぞれについて、以下の２種類の制約があります：13     <ul>14     <li>１つ目の制約は順序に関するもので以下のいずれかです：<br>15         <var>a<sub>i</sub></var> は <var>b<sub>i</sub></var> よりも先、または同じ位置に並ばなくてはならない<br>16	 <var>a<sub>i</sub></var> は <var>b<sub>i</sub></var> よりも後、または同じ位置に並ばなくてはならない<br>17	 <var>a<sub>i</sub></var> は <var>b<sub>i</sub></var> より先でも、同じ位置でも、後でもよい<br>18	 </li>19     <li>２つ目の制約は距離に関するもので以下のいずれかです：<br>20	<var>a<sub>i</sub></var> と <var>b<sub>i</sub></var> は <var>d<sub>i</sub></var> メートル以上離れなければならない<br>21	<var>a<sub>i</sub></var> と <var>b<sub>i</sub></var> は <var>d<sub>i</sub></var> メートル以内に並ばなければならない<br>22	</li>23</li>24</ul>25</ul>26 27<p>28また、先頭から同じ距離の場所に複数の人が並ぶことができ、行列の先頭には常に番号 1 の人が並ぶことが分かっています。29</p>30 31<p>32与えられた <var>C</var> 個の制約をすべて満たす行列について、先頭から最後尾までの距離が最大となるような並び方をした場合の距離を求めるプログラムを作成してください。ただし、どこまでも離れることができる場合は <span>inf</span> と、制約を満たす並び方が不可能な場合は <span>-1</span> と出力してください。33</p>34 35<h2>入力</h2>36<p>37入力は以下の形式で与えられる。 38</p>39 40<pre>41<var>N</var> <var>C</var>42<var>constraint<sub>1</sub></var>43<var>constraint<sub>2</sub></var>44:45<var>constraint<sub>C</sub></var>46</pre>47 48<p>491 行目に行列に並ぶ高校生の人数 <var>N</var> (2 &le; <var>N</var> &le; 100) と制約の数 <var>C</var> (0 &le; <var>C</var> &le; 200) が与えられる。続く <var>C</var> 行に各制約 <var>constraint<sub>i</sub></var> が次の形式で与えられる。 50</p>51 52<pre>53<var>a<sub>i</sub>o<sub>i</sub>b<sub>i</sub>s<sub>i</sub>d<sub>i</sub></var>54</pre>55 56<p>57制約には空白は含まれない。<var>a<sub>i</sub></var>, <var>o<sub>i</sub></var>, <var>b<sub>i</sub></var>, <var>s<sub>i</sub></var>, <var>d<sub>i</sub></var> の意味を以下に示す。58</p>59 60<ul>61<li> <var>a<sub>i</sub></var> と <var>b<sub>i</sub></var> (1 &le; <var>a<sub>i</sub></var>, <var>b<sub>i</sub></var> &le; <var>N</var> かつ <var>a<sub>i</sub></var> &ne; <var>b<sub>i</sub></var> ) は高校生の番号、<var>d<sub>i</sub></var> は距離 (0 &le; <var>d</var> &le; 10000) を表す整数である。</li>62<li> <var>o<sub>i</sub></var> は順序の制約を指定する <span><=</span>、<span>>=</span>、<span>*</span> のいずれかの文字列であり、<span><=</span> の場合「<var>a<sub>i</sub></var> は <var>b<sub>i</sub></var> よりも先、または同じ位置に並ばなくてはならない」、<span>>=</span> の場合「<var>a<sub>i</sub></var> は <var>b<sub>i</sub></var> よりも後、または同じ位置に並ばなくてはならない」、<span>*</span> の場合「<var>a<sub>i</sub></var> は <var>b<sub>i</sub></var> より先でも、同じ位置でも、後でもよい」ことを意味する。ただし <var>o<sub>i</sub></var> が <span>*</span> となる制約は７個以上与えられることはない。</li>63<li> <var>s<sub>i</sub></var> は距離の制約を指定する <span>+</span> または <span>-</span> の文字であり、<span>+</span> の場合「<var>a<sub>i</sub></var> と <var>b<sub>i</sub></var> は <var>d<sub>i</sub></var> メートル以上離れなければならない」、<span>-</span> の場合「<var>a<sub>i</sub></var> と <var>b<sub>i</sub></var> は <var>d<sub>i</sub></var> メートル以内に並ばなければならない」ことを意味する。64</li>65</ul>66 67<p>68ただし、あるペアに対して複数の制約が与えられることはないものとする。69</p>70 71<h2>出力</h2>72 73<p>74先頭から最後尾までの距離を１行に出力する。 75</p>76 77<h2>入出力例 </h2>78<br>79 80 81<h2>入力例１</h2>82<pre>833 2841<=2-1852<=3-286</pre>87 88<h2> 出力例１</h2>89<pre>90391</pre>92<br>93 94<h2>入力例２ </h2>95<pre>963 3971<=2-1982<=3-2991<=3+4100</pre>101 102<h2>出力例２</h2>103<pre>104-1105</pre>106<br>107 108 109<h2>入力例３ </h2>110<pre>1113 21121<=2-21132*3+1114</pre>115<h2>出力例３</h2>116<pre>117inf 118</pre>119 120 121