東京工業大学プログラミングコンテスト2015

A - ぼくの学生証

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

とある大学に所属しているA君はある日記憶喪失になってしまった。

学生証に書かれた学籍番号からA君の入学した年と身分を判定するプログラムを作るのがあなたの仕事である。

A君の所属している大学の学籍番号について、以下のルールがあることが知られている。

長さ8の文字列である。
最初の2字は数字だけで構成されており、入学した年の下2桁を表す。
3文字目がBならば学士課程であることを、Mならば修士課程であることを、Dならば博士課程であることを表す。
残りの5字は数字だけで構成されている。

入力

入力は以下の形式で標準入力から与えられる。

1行目にA君の学生証に書かれた学籍番号を表す文字列Sが与えられる。
Sは以下の制約を満たす。
|S|=8 。ここで|S|は文字列Sの長さを表す。
3文字目はB、M、Dのいずれかである。
3文字目以外は0, 1, 2, 3, 4, 5, 6, 7, 8, 9のいずれかの数字である。

出力

A君の身分と入学年の下2桁を空白区切りで1行に出力せよ。改行を忘れないこと。
身分について、学士課程ならばBachelorを、修士課程ならばMasterを、博士課程ならばDoctorを出力せよ。
詳しくはサンプルを確認すること。

入力例1

12B34567

出力例1

Bachelor 12

A君は12年入学の学士課程の学生であるようです。

入力例2

00M00000

出力例2

Master 00

A君は00年入学の修士課程の学生であるようです。

入力例3

13D10007

出力例3

Doctor 13

A君は13年入学の博士課程の学生であるようです。

B - ラー油

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

東工太郎君はN日間、毎日1食担々麺を食べます。担々麺には好きな量のラー油をかけることが出来ます。太郎君がi日目(1 \leq i \leq N)にラー油をx_iかけた担々麺を食べた時、幸福度をA_i x_i得ることが出来ます。

太郎君はおなかが弱いので、0 \leq x_i \leq B \, (1 \leq i \leq N)かつ\Σ_{1 \leq i \leq N} x_i \leq Cである必要があります。また、ラー油はとてもおいしいのでN \geq 2のとき任意のi(1 \leq i \leq N-1)に対してA_i \leq A_{i+1}が成り立ちます。

太郎君が得られるN日間の幸福度の和の最大値を求めてください。

入力

入力は以下の形式で標準入力から与えられる。

N B C
A_1 ... A_N

1行目に3つの整数N(1 \leq N \leq 100) , \, B(1 \leq B \leq 10000), \, C(1 \leq C \leq 10000)が空白区切りで与えられる。
2行目にN個の整数A_1, …, A_N (0 \leq A_i \leq 100)が空白区切りで与えられる。
N \geq 2のとき任意のi(1 \leq i \leq N-1)に対してA_i \leq A_{i+1}

出力

太郎君が得られるN日間の幸福度の和の最大値を1行に出力してください。出力の末尾に改行を入れること。

入力例1

3 2 5
1 2 3

出力例1

1日目に1だけラー油をかけ、2日目と3日目に2だけラー油をかけるのが最適であり、太郎君は11だけ幸せになれます。

入力例2

3 100 100
1 2 100

出力例2

1日目と2日目にはラー油をかけず3日目に100だけラー油をかけるのが最適であり、太郎君は10000だけ幸せになれます。

入力例3

5 0 10000
1 2 3 7 15

出力例3

太郎君は追加でラー油をかけることはない。

入力例4

6 10000 0
1 2 4 8 16 97

出力例4

太郎君のおなかはとても弱いので追加でラー油をかけることはできない。

入力例5

5 10000 10000
0 0 0 0 0

出力例5

ラー油をどれだけかけても幸せにはなれない。

入力例6

8 5 32
0 1 1 2 3 5 8 13

出力例6

C - おおおかやま

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

okayama国の首都ookayamaでは、ookayamaの先頭に1個以上の任意の個数のoが付加された文字列のことを良い文字列と呼ぶ。

あなたの仕事は文字列Sを次のルールで処理するプログラムを書くことである。

手順1. Sの部分文字列に良い文字列が存在するならば手順2へ、存在しないならば処理を終了する。
手順2. 良い文字列であるようなSの部分文字列のうち、長さが最長のものを選びこれをTとして手順3へ。最長のものが複数ある場合は最も左側にあるものを選ぶ。
手順3. Tにooという部分文字列が存在するならば、そのうち最も左側にあるものをOへ置換して手順4へ、存在しないならば手順1へ。
手順4. TにOOという部分文字列が存在するならば、そのうち最も左側にあるものをoへ置換する。存在するかどうかにかかわらず手順3へ。

処理終了後のSを求めよ。この処理結果が何に用いられるかは機密情報であるため、あなたは知る必要はない。

ある文字列TがSのi (1 \leq i \leq |S|)文字目からj (i \leq j \leq |S|)文字目までを取り出したものであるとき、TはSの部分文字列であると呼ぶ。ここで | S | は文字列Sの長さを表す。

入力

入力は以下の形式で標準入力から与えられる。

1 行目に処理すべき文字列S(1 \leq | S | \leq 100)が与えられる。Sは英小文字のみからなることが保証される。

出力

処理終了後のSを1行に出力せよ。改行を忘れないこと。

入力例1

ooookayama

出力例1

okayama

文字列ooookayamaに対し、処理を行うと、以下のような順序で扱われる。

手順1においてSの部分文字列に良い文字列は存在する。
手順2において良い文字列であってSの部分文字列であるようなもののうち長さが最長のものは1番目のoから始まる部分文字列である、ooookayamaである。これをTとする。
手順3においてTに存在するooという部分文字列のうち、最も左側にあるものをOに置換する。TはOookayamaとなる。
手順4においてTにOOという部分文字列は存在しない。
手順3においてTに存在するooという部分文字列のうち、最も左側にあるものをOに置換する。TはOOkayamaとなる。
手順4においてTに存在するOOという部分文字列のうち、最も左側にあるものをoに置換する。Tはokayamaとなる。
手順3においてTにooという部分文字列は存在しない。
手順1においてSはokayamaである。Sの部分文字列に良い文字列は存在しない。処理を終了する。

入力例2

ooookayamaoooookayama

出力例2

okayamaOkayama

Sの部分文字列には、良い文字列が複数存在することもある。最長のものかつ最も左側にあるものから処理する必要があることに注意せよ。また、与えられる入力には英大文字は含まれないものの、答えや処理の過程には現れる可能性があることに注意せよ。

入力例3

okayama

出力例3

okayama

文字列okayamaの部分文字列には良い文字列は存在しない。

入力例4

ookayama

出力例4

ookayama

文字列ookayamaの部分文字列には良い文字列は存在しない。良い文字列とはookayamaの先頭に1個以上の任意の個数のoが付加された文字列のことであるためookayamaは条件を満たさない。

入力例5

ooookayamakenooooookayamashiookayama

出力例5

okayamakenOokayamashiookayama

D - 文字列と素数

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

文字列 S が与えられる。以下の条件を満たす変換で S からある数への変換を行う。

Sの各文字を 1,3,5,7,9 のいずれかの数字に変換する。
同じ文字は同じ数字に、異なる文字は異なる数字に変換しなくてはならない。

上の条件を満たす変換によって、文字列 S を素数に変換することできるだろうか。

入力

入力は以下の形式で標準入力から与えられる。

1 行で文字列 S(1 \leq | S | \leq 10)が与えられる。
S の各文字は、英小文字である。

出力

素数の変換先を得られる場合は、そのような素数を一つ出力してください。素数の変換先がない場合は、-1 を出力してください。

素数の変換先が複数ある場合は、いずれを出力しても正解として扱われる。

入力例1

tit

出力例1

他にも、151,171,191,313,… のいずれかを出力しても正解として扱われる。

入力例2

titech

出力例2

入力例3

tokyotech

出力例3

-1

文字の種類が多すぎるため、条件を満たす変換を構成することができません。

E - マス目色ぬり

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

N × N のマス目が与えられます。上から i(1 \leq i \leq N) 番目、左から j(1 \leq j \leq N) 番目のマスを (i,\ j) とします。

マスそれぞれを、i+j が偶数ならば赤色、奇数ならば青色に塗ります。

次に、K 個のマスについて、そのマスが赤色に塗られていたら青色、青色に塗られていたら赤色に塗り直します。

その後、あなたはいくつかのマスを選びます。ただし、選んだマスたちは1つの穴のない長方形とならなければいけません。

そして、選んだマスたちのうち赤色のマスの数と青色のマスの数の差の絶対値ができる限り大きくなるようにしたいです。最大でいくつになるでしょうか。

入力

入力は以下の形式で標準入力から与えられる。

N K
Y_1 X_1
Y_2 X_2
:
Y_K X_K

1 行目には整数 N(1 \leq N \leq 2000)、K(1 \leq K \leq 10) が空白区切りで与えられる。
そのあと K 行には色を塗り直すマスの情報が与えられる。このうち i 行目には整数 Y_i(1 \leq Y_i \leq N)、X_i(1 \leq X_i \leq N) が空白区切りで与えられ、これは (Y_i,\ X_i) の色を塗り直すことを表す。
i \neq j ならば、Y_i \neq Y_j または X_i \neq X_j を満たす。

出力

赤色のマスの数と青色のマスの数の差の絶対値の最大値を出力せよ。出力は標準出力に行い、末尾に改行を入れること。

入力例1

3 1
1 1

出力例1

この場合、(1, 1) と (1, 2) を選んだ場合に答えは最大になり、2 になります。他にも、(1, 1) と (2, 1) を選んだ場合や (1,1),(1,2),(2,1),(2,2) を選んだ場合も答えは 2 になります。

入力例2

出力例2

この場合、すべてのマス目が赤色に塗られます。なのですべてのマスを選ぶときが最大で答えは 9 です。

入力例3

出力例3

この場合、真ん中のマス目以外が青色に塗られます。なのでこの場合もすべてのマスを選ぶときが最大で答えは 7 です。

F - レシート

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

太郎君はA円の買い物をした。太郎君はX \geq Aを満たす任意のX円を支払うことができる。買い物の金額A、支払額X、お釣り(X-A)の3つの整数について10進数表記にしたとき、3つの数字が揃う桁の数を最大にしたい。

例えば、A=1980,X=2970の時、百の位の9と一の位の0の2箇所が揃う。

  A = 1980
  X = 2970
X-A =  990

また、A=1080,X=1080の時、一の位のみが揃う。十の位から千の位については、X-Aがその桁に数字がないため揃っていないものとする。

  A = 1080
  X = 1080
X-A =    0

Aが与えられるので、太郎君が揃えられる桁の数の最大値を求めよ。

入力

入力は以下の形式で標準入力から与えられる。

1 行目に整数A(1 \leq A \leq 10^{100})が与えられる。

出力

太郎君が揃えられる桁の数の最大値を1行で出力せよ。出力の末尾に改行を入れること。

入力例1

出力例1

問題文の最初のケースである。

入力例2

出力例2

例えばX=2080とすると百の位と一の位の2つの桁が揃い、これが最大。問題文の2つめのケースのようにX=1080とすると一の位しか揃わないことに注意。

入力例3

出力例3

太郎君がどのような支払いをしても、いずれの桁も揃えることができない。

G - titech分離

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

英小文字(a-z)からなる文字列Sが与えられる。

Sをいくつかの(連続とは限らない)部分文字列に分解する。つまり、Sの各文字がちょうど1つの部分文字列に含まれるように、Sから複数の部分文字列を選ぶ。

分解した結果の部分文字列が全てtitechになるような分解方法があるかどうか判定せよ。

入力

入力は以下の形式で標準入力から与えられる。

1 行目に文字列S(1 ≦ | S | ≦ 100)が与えられる。

出力

分解が可能ならYes、不可能ならNoを出力せよ。出力の末尾に改行を入れること。

入力例1

titech

出力例1

Yes

1つのtitechに分解できる。

入力例2

tititechtech

出力例2

Yes

例えば、1,2,5,6,7,8文字目と3,4,9,10,11,12文字目に分解すれば2つのtitechに分解できる。

入力例3

titecg

出力例3

No

入力例4

tttiiittteeeccchhh

出力例4

Yes

3つのtitechに分解できる。

H - 包囲

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

2次元平面上に存在する格子点のうちN個の格子点は色が塗られている。色が塗られた格子点のいくつかを選んで、選んだ点たちを頂点とする単純多角形を作る。そのような単純多角形のうち、原点を内部に含み面積が最小のものの面積を求めよ。

ここで単純多角形とは自己交差のない多角形のことである。

入力

入力は以下の形式で標準入力から与えられる。

N
X_1 Y_1
X_2 Y_2
:
X_N Y_N

1 行目に格子点の数を表す整数N(1 \leq N \leq 200)が与えられる。
1+i 行目にはi番目の格子点の座標(X_i, Y_i)が与えられる。
与えられる格子点は以下の制約を満たす。
-100000 \leq X_i, Y_i \leq 100000
(X_i, Y_i) \neq (X_j, Y_j) (i \neq j)
(X_i, Y_i) \neq (0, 0)

出力

原点を内部に含む単純多角形が存在しないならばImpossibleのみを1行に出力せよ。
原点を内部に含む単純多角形が存在するならばPossibleを1行目に出力し、2行目に面積の最小値を出力せよ。
改行を忘れないこと。また、面積については想定解答との絶対誤差または相対誤差が、10^{-8}以下であれば、正解として扱われる。

入力例1

出力例1

Possible
3.0000000000

1番目の点と2番目の点と3番目の点をつないだ三角形が原点を内部に含む面積最小の単純多角形である。

入力例2

出力例2

Possible
4.0000000000

1番目の点と2番目の点と3番目の点と4番目の点をつないだ四角形が原点を内部に含む単純多角形のうち面積が最小のものである。点をつなぐ順番によっては単純多角形にならないことに注意せよ。

入力例3

出力例3

Impossible

1番目の点と2番目の点と3番目の点をつないだ三角形は原点を境界上に含むものの、内部には含んでいないため条件を満たさない。よって原点を内部に含む単純多角形は存在しない。

I - そーっとソート

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

(1,\ 2,\ …,\ N) の順列として、数列 a_1,\ a_2,\ …,\ a_N が与えられます。

あなたは、以下の操作を 100,000 回まで行うことができます。

a_i と a_j の値を入れ替える。ただし、|i-j| = a_i または |i-j| = a_j を満たしていなければならない。

数列を 1,\ 2,\ …,\ N へと並び変えることが出来るか判定し、また、出来るならばその手順を 1 つ示してください。

入力

入力は以下の形式で標準入力から与えられる。

N
a_1 a_2 … a_N

1 行目には数列の要素数 N(1 \leq N \leq 50) が与えられる。
2 行目には、数列の要素 a_i が空白区切りで与えられる。
a_1,\ a_2,\ ,…,\ a_N は (1,\ 2,\ …,\ N) の順列である。

出力

出力は標準出力に行い、末尾に改行を入れること。

もしどのような手順でも 100,000 回以内の操作では数列がソート出来ないならば、MuriyarokonnNaN と出力すること。

ソートすることが出来る場合は、以下の形式に従い出力すること。

R
X_1 Y_1
X_2 Y_2
:
X_R Y_R

1 行目には操作の回数 R(0 \leq R \leq 100,000) を出力する。
2 行目から R 行には操作の詳細を出力する。このうち i 行目には整数 X_i(1 \leq X_i \leq N),\ Y_i(1 \leq Y_i \leq N) を空白区切りで出力する。これは、i 回目の操作では a_{X_i} と a_{Y_i} の値を入れ替えることを表す。(修正,15:41)

入力例1

5
4 2 3 1 5

出力例1

(13:55)1行目の値に誤りがあり、修正しました。

J - 指さし

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

N人がいて、それぞれ自分以外の誰か1人を指さしています。このとき、誰からも指さされていない人は一人もいませんでした。

各人が指さされている指を何回辿ったときにはじめて自分自身に戻ってくるか報告したところ、その最大値はK回でした。

このような指さし方がいくつあるか数えてみましょう。指さし方を数える際、人はそれぞれ区別するものとします。

指さし方の通り数は非常に大きくなりうるので、1,000,000,007(=10^{9}+7)で割った余りを求めなさい。

入力

入力は以下の形式で標準入力から与えられる。

N K

1 行目に整数N(2 \leq N \leq 1000)、K(1 \leq K \leq N)が空白区切りで与えられる。

出力

指さし方の通り数を1,000,000,007で割った余りを1行で出力せよ。出力の末尾に改行を入れること。

部分点

この問題には部分点が設定されている。

2 \leq N \leq 8を満たすデータセットに正解した場合10点が得られる。
全てのデータセットに正解した場合はさらに140点が得られる。合計で150点となる。

入力例1

3 3

出力例1

それぞれの人を1、2、3としたとき、1→2→3→1となる指さし方と、1→3→2→1となる指さし方の2通りが存在します。

入力例2

4 2

出力例2

それぞれの人を1、2、3、4としたとき、1→2→1、3→4→3となる指さし方と、1→3→1、2→4→2となる指さし方と、1→4→1、2→3→2となる指さし方の3通りが存在します。

入力例3

3 2

出力例3

条件を満たす指さし方が存在しないこともあります。

入力例4

1000 1000

出力例4

756641425

答えは非常に大きくなりうるので、1,000,000,007で割った余りを出力してください。

K - 麻雀

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

N人で麻雀をすることにした。麻雀とは4人で行うテーブルゲームである。

総当り戦を行ったところ、各対戦で誰か1人が勝利した。すなわち引き分けや同着1位は存在しなかった。ただし、N人の総当り戦とは1からNの番号を各人につけたときに 1 ≦ p ＜ q ＜ r ＜ s ≦ N をみたすp,q,r,sの4人の対戦 C(N,4) 通りを行う対戦形式のことである。

順位表が紛失してしまったため、それぞれの対局結果が分からなくなってしまった。

各人の自身が何回勝利したかという証言から、そのような条件を満たす全体の対局結果が存在するか調べることにした。

入力

入力は以下の形式で標準入力から与えられる。

N
A_1
A_2
A_3
.
.
.
A_N

1行目に麻雀を行った人数N(4 ≦ N ≦ 10^{4})が与えられる。
続くN行に各人の勝利数が与えられる。i行目にはi番目の人の勝利数A_i(0 ≦ A_i ≦ 10^{12})が与えられる。

出力

各人の勝利数が全て正しくなるような、それぞれの対局における勝利結果が存在するならば'YES'を、存在しないならば'NO'を1行に出力せよ。改行を忘れないこと。

入力例1

出力例1

YES

入力例2

出力例2

NO

L - グラフ色ぬり

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

N 頂点 A+B 辺からなる単純有向グラフ G が与えられます。頂点には 1,\ 2,\ …,\ N の番号が振られています。

このグラフは、辺のうち A 本が赤色に、残りの B 本が青色に塗られています。

ここから青色の辺を全て削除したグラフを G' とします。

以下の条件を満たすグラフ G'' のうち、辺数の最大は何本かを求めてください。

G'' は G から、青色の辺を 0 本以上任意の本数選び、削除したものである。
頂点 1 を始点、頂点 N を終点としたときの G' と G'' の最大流の値が等しい。ただし辺の容量は全て 1 とする。

最大流についてはここを参考にすること。

入力

入力は以下の形式で標準入力から与えられる。

N A B
X_1 Y_1
X_2 Y_2
:
X_{A+B} Y_{A+B}

1 行目には整数 N(2 \leq N \leq 100)、A(1 \leq A \leq 200)、B(1 \leq B \leq 200) が空白区切りで与えられる。
そのあと A+B 行には、グラフの辺の情報が与えられる。このうち i 行目には整数 X_i(1 \leq X_i \leq N),\ Y_i(1 \leq Y_i \leq N) が空白区切りで与えられ、これは辺 (X_i,\ Y_i) が存在することを表す。
(X_1,\ Y_1), (X_2,\ Y_2), …,(X_A,\ Y_A) は赤く塗られた辺であり、(X_{A+1},\ Y_{A+1}), (X_{A+2},\ Y_{A+2}), ..., (X_{A+B},\ Y_{A+B}) は青く塗られた辺である。
X_i = Y_i なる i は存在しない。また、i \neq j ならば、Y_i \neq Y_j または X_i \neq X_j を満たす。

出力

G'' の辺数の最大を出力せよ。出力は標準出力に行い、末尾に改行を入れること。

入力例1

出力例1

入力例2

出力例2

入力例3

出力例3

この場合すべての青色の辺を追加することができる。

入力例4

出力例4

この場合もすべての青色の辺を追加することができる。

入力例5

出力例5

この場合は一本も青色の辺を追加することができない。

M - コインと無向グラフ

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

頂点数 N で辺の数 M の無向グラフが与えられる。グラフの各頂点 i (0 ≦ i < N) にはコインが C_i 枚乗っている。また、辺の長さは全て 1 とする。

プレイヤー1 とプレイヤー2 は、頂点 0 にコインを集めるゲームをする。プレイヤー1 とプレイヤー2 は、交互に以下の手続きを繰り返す。

1. 頂点を 1つ選んでそれを j とする。
1. 頂点 j に隣接する頂点のうち、頂点 j よりも頂点 0 に距離が近い頂点を 1つ選んでそれを k とする。
1. 頂点 j から頂点 k にコインを 1 枚以上移動させる。

（注意）頂点 0 や頂点 0 に到達出来ない頂点を j として選択することはできない。

プレイヤー1 が先手でプレイして、コインを移動できなくなった方が負けとする。

プレイヤー1 とプレイヤー2 がともに最善を尽くす時、どちらが勝つか判定してください。

入力

入力は以下の形式で標準入力から与えられる。

N M
C_0 ... C_{N-1}
v_0 w_0
...
v_{M-1} w_{M-1}

1 行目に頂点数を表すN(1 ≦ N ≦ 10^5)と辺の数を表すM(0 ≦ M ≦ 2*10^5)が与えられる。
2 行目に頂点 i(0 ≦ i < N)にあるコインの枚数 C_i(0 ≦ C_i ≦ 10^8) が空白区切りで与えられる。
3+i 行目(0 ≦ i < M)には、v_i(0 ≦ v_i < N) w_i(0 ≦ w_i < N) が空白区切りで与えられる。これは無向辺が頂点 v_i と頂点 w_i の間に張られていることを表す。

部分点

N ≦ 7 かつ C_0 + ... + C_{N-1} ≦ 7 を満たすテストケースに正解した場合、 50 点が与えられる。
全てのケースに正解した場合、 200 点が与えられる。

合計 250 点

出力

プレイヤー1が勝つ場合には、 First を出力してください。

プレイヤー2が勝つ場合には、 Second を出力してください。

入力例1

出力例1

Second

頂点 0 に近づけるようにコインを動かすことが出来ないので、プレイヤー1 が負ける。

入力例2

出力例2

First

頂点 1 のコインを頂点 0 に動かして、プレイヤー1 が勝つ。

入力例3

出力例3

Second

プレイヤー1 がどのように動かしても、プレイヤー2 が勝つ。

入力例4

7 0
1 1 1 1 1 1 1

出力例4

Second

N - 何かグラフの問題

Time Limit: 5 sec / Memory Limit: 256 MB

問題文

太郎くんにN頂点M辺の有向グラフが与えられた。このグラフには多重辺があるかもしれないが、自己ループとなる辺は張られていない。また、辺eに対してc_eが与えられている。

太郎くんは各頂点vに対して定められるN個の変数a_vと変数Tに実数値を割り当てることができる。このとき、次の条件を満たしつつTを最小化することを考えたい。

条件 : 任意の辺eに対してその始点をu, 終点をwとすればa_u + c_e \leq a_w + Tを満たす。

さらに、先ほど与えられたa_vはいくつかの頂点vに対しては既に値が固定されており、この変数には例外的に値を割り当てることができない。

Tとして取りうる最小値を実数で出力せよ。どこまでも小さくできるときは"#"の1文字を出力せよ。

入力

入力は以下の形式で標準入力から与えられる。

N M K
v_1 val_1
v_2 val_2
:
v_K val_K
u_1 w_1 c_1
u_2 w_2 c_2
:
u_M w_M c_M

入力における数はすべて整数である
1 行目には N(1 \leq N \leq 2,000),M(1 \leq M \leq 2,000),K(0 \leq K \leq N) が空白区切りで与えられる。N,Mはそれぞれ与えられるグラフの頂点数と辺数を表している。 Kはaの値が既に決定されている頂点数を表す。
次の K 行には、既にaの値が決まっている頂点の情報が与えられる。このK行のうちi行目にはv_i (1 \leq v_i \leq N), val_i (-10^5 \leq val_i \leq 10^5)が空白区切りで与えられる。これはa_{v_i} = val_iであることを表している。また、v_i は相異なると仮定してよい
次の M 行にはグラフの辺情報が与えられる。このM行のうちi行目にはu_i(1 \leq u_i \leq N) w_i(1 \leq w_i \leq N) c_i(-10^5 \leq c_i \leq 10^5)　が空白区切りで与えられる。また、u_i \neq v_iをみたす。これは有向辺が頂点u_iからw_iへ張られていることを表している。

出力

問題文にしたがってTの最小値を実数で出力せよ。無限に小さくできるときは"#"の1文字を出力せよ。

答えが実数であるときには誤差は絶対誤差または相対誤差で10^{-5}の差まで許容される

出力は標準出力に行い、末尾に改行を入れること。

入力例1

出力例1

4.000000

aはa_1=0, a_2=-1, a_3=-1 と割り当てれば良い

入力例2

出力例2

3.000000

aの値がすべて決まっているので条件を満たすTの最小値はすぐに決まる。

入力例3

出力例3

多重辺を持つ場合もあるので注意すること

O - 数列色ぬり

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

(1,\ 2,\ …,\ N) の順列として数列 a_1,\ a_2,\ …,\ a_N が与えられます。

あなたは、この数列のうちいくつかの要素を、以下の条件を満たすように赤色または青色に塗ることができます。

すべての i,\ j(1 \leq i < j \leq N) について、a_i,\ a_j がともに赤色に塗られているならば a_i < a_j
すべての i,\ j(1 \leq i < j \leq N) について、a_i,\ a_j がともに青色に塗られているならば a_i > a_j

あなたは色を塗る要素を出来る限り多くしたいです。

色を塗る要素の個数の最大値を求めてください。

入力

入力は以下の形式で標準入力から与えられる。

N
a_1 a_2 … a_N

1 行目には整数 N(1 \leq N \leq 10^5) が与えられる。
2 行目には数列 a_i が空白区切りで与えられる。
a_1,\ a_2,\ ,…,\ a_N は (1,\ 2,\ …,\ N) の順列である。

出力

色を塗る要素の個数の最大値を一行に出力せよ。出力は標準出力に行い、末尾には改行を入れること。

入力例1

5
3 4 1 5 2

出力例1

塗り方の一例として、a_1, a_4 を赤色に塗り a_2, a_3 を青色に塗るという方法があります。

入力例2

7
1 2 3 4 5 6 7

出力例1

すべての要素を赤色に塗ることができます

入力例3

4
3 1 4 2

出力例3

a_2, a_3 を赤色に塗り a_1, a_4 を青色に塗ればよいです

入力例3

20
18 13 16 20 10 8 15 2 11 19 3 5 1 4 9 7 14 12 17 6

出力例3

P - Dancing stars on regular expression!

Time Limit: 1 sec / Memory Limit: 256 MB

問題文

ここでは、以下の構文で表される文字列を "正規表現" と呼ぶ。

e ::= a...a | (e_1+e_2) | (e_1;e_2) | *(e_1) | !(e_1)

ただし、a...a は文字 a の 1 回以上の繰り返しによって表せるようなある文字列を表す。

正規表現 e が表現する文字列の集合 L(e) は以下で帰納的に定義される。

L(a...a) = \{a...a\}
       - 例えば、L(aa) = \{aa\}, L(aaa) = \{aaa\}。
L((e_1+e_2)) = L(e_1) ∪ L(e_2)
       - L(e_1) に属する または L(e_2) に属する 文字列 の集合。
L((e_1;e_2)) = L(e_1)L(e_2) = \{ w_1 w_2 | w_1 \in L(e_1), w_2 \in L(e_2) \}
       - L(e_1) に属する文字列 と L(e_2) に属する文字列 をつなげた文字列の集合。
L(*(e_1)) = L(e_1)^* = \{ε\} ∪ \{w_1 | w_1 \in L(e_1)\} ∪ ... ∪ \{w_1 ... w_n | w_1,...,w_n \in L(e_1)\} ∪ ...
       - L(e_1) に属する文字列 を 有限回つなげた (0 回の場合も含む) 文字列の集合。
L(!(e_1)) = Σ^* - L(e_1)
       - L(e_1) に属さない文字列 の集合。

ただし、Σ^* は文字列の全体集合 \{ε(空の文字列),a,aa,aaa,...\} = ( a を有限個つなげた文字列の集合) を表す。

また、以下の文中で"!なし正規表現" とは ! が出現しない正規表現を指し、 "*なし正規表現" とは * が出現しない正規表現を指します。

さて、!なし正規表現 S が与えられます。

L(S) = L(T) を満たす *なし正規表現 T が存在するかどうか判定してください。

入力

入力は以下の形式で標準入力から与えられる。

N
S

1 行目には、2 行目に入力される S の文字列の長さ N(1 ≦ N ≦ 4000) が与えられる。
2 行目には、ある !なし正規表現を表す文字列 S が与えられる。

出力

L(S) = L(T) を満たす *なし正規表現 T が存在する場合、 YES を出力してください。

L(S) = L(T) を満たす *なし正規表現 T が存在しない場合、 NO を出力してください。

入力例1

6
(a+aa)

出力例1

YES

T = (a+aa) とすればよい。

入力例2

17
(*(aa)+(*(aa);a))

出力例2

YES

T = (!(a)+a) とすればよい。

入力例3

14
(*(aa)+*(aaa))

出力例3

NO

L(S) = L(T) を満たす *なし正規表現 T は存在しません。