問題文

DISCO presents ディスカバリーチャンネルプログラミングコンテスト 2016には N 人が参加しました。 順位表は N 行からなり、 i 行目には i 位の人の座席番号 Id_i が表示されています。すなわち、 N 人が取った順位はそれぞれ異なります。

ところでDISCO presents ディスカバリーチャンネルプログラミングコンテスト 2016の賞金は以下のようになっています。

• 1 位: 100,000 円
• 2 位: 50,000 円
• 3 位: 30,000 円
• 4 位: 20,000 円
• 5 位: 10,000 円
• それ以外: 0 円

あなたはDISCO presents ディスカバリーチャンネルプログラミングコンテスト 2016の参加者それぞれが獲得した賞金の金額を知りたくなりました。

入力例 1

5
1
2
3
4
5

出力例 1

100000
50000
30000
20000
10000

• このケースにおいては 5 行にわたって出力が行われます。
• 座席番号が 1 の人は 1 位だったので、 100,000 円を獲得しました。
• 座席番号が 2 の人は 2 位だったので、 50,000 円を獲得しました。
• 座席番号が 3 の人は 3 位だったので、 30,000 円を獲得しました。
• 座席番号が 4 の人は 4 位だったので、 20,000 円を獲得しました。
• 座席番号が 5 の人は 5 位だったので、 10,000 円を獲得しました。

入力例 2

8
8
7
6
5
4
3
2
1

出力例 2

0
0
0
10000
20000
30000
50000
100000

• このケースにおいては 8 行にわたって出力が行われます。
• 座席番号が 1 の人は 8 位だったので、 0 円を獲得しました。
• 座席番号が 2 の人は 7 位だったので、 0 円を獲得しました。
• 座席番号が 3 の人は 6 位だったので、 0 円を獲得しました。
• 座席番号が 4 の人は 5 位だったので、 10,000 円を獲得しました。
• 座席番号が 5 の人は 4 位だったので、 20,000 円を獲得しました。
• 座席番号が 6 の人は 3 位だったので、 30,000 円を獲得しました。
• 座席番号が 7 の人は 2 位だったので、 50,000 円を獲得しました。
• 座席番号が 8 の人は 1 位だったので、 100,000 円を獲得しました。

入力例 3

7
1
5
4
2
7
6
3

出力例 3

100000
20000
0
30000
50000
0
10000

• このケースにおいては 7 行にわたって出力が行われます。
• 座席番号が 1 の人は 1 位だったので、 100,000 円を獲得しました。
• 座席番号が 2 の人は 4 位だったので、 20,000 円を獲得しました。
• 座席番号が 3 の人は 7 位だったので、 0 円を獲得しました。
• 座席番号が 4 の人は 3 位だったので、 30,000 円を獲得しました。
• 座席番号が 5 の人は 2 位だったので、 50,000 円を獲得しました。
• 座席番号が 6 の人は 6 位だったので、 0 円を獲得しました。
• 座席番号が 7 の人は 5 位だったので、 10,000 円を獲得しました。

問題文

DISCO presents ディスカバリーチャンネルプログラミングコンテスト 2016本戦のDDPC特別ビュッフェの時間が始まりました。あなたはこれから料理の載っていないトレーに料理を載せに行くところです。 DDPC特別ビュッフェには N 種類の料理があります。 i 種類目の料理はビュッフェの開始から T_i 秒後になくなり、料理の美味しさは A_i です。

DDPC特別ビュッフェにはいくつかの特別なルールがあります。

• あなたは 1 種類の料理をトレーに載せるのに 1 秒かけなくてはならない。すなわち料理を載せ始めた時刻が s であったとき、料理を載せ終わったときの時刻は s+1 となる。
• あなたは以前にトレーに載せた料理と同じ種類の料理を載せてはならない。
• 現在の時刻 s がs+1≦T_i を満たさないとき、種類 i の料理をトレーに載せることはできない。

あなたはトレーに載っている料理の美味しさの総和が X 以上になったところで席に戻ることにしました。トレーに載っている料理の美味しさの総和を X 以上にすることが可能な最小の時刻 t を求めてください。

入力例 1

4 5
1 2 3 4
3 3 1 1

出力例 1

2

• 以下のような料理の取り方をすることで、時刻 2 にトレーに載っている料理の美味しさの総和が 5 以上にすることが可能です。
• 0 秒目の時点でトレーに載っている料理の美味しさの総和は 0 です。種類 1 の料理をトレーに載せます。
• 1 秒目の時点でトレーに載っている料理の美味しさの総和は 3 です。種類 2 の料理をトレーに載せます。
• 2 秒目の時点でトレーに載っている料理の美味しさの総和は 6 です。
• このケースは部分点の追加制約を満たします。

入力例 2

3 10
1 2 3
3 3 4

出力例 2

3

• 以下のような料理の取り方をすることで、時刻 3 にトレーに載っている料理の美味しさの総和が 10 以上にすることが可能です。
• 0 秒目の時点でトレーに載っている料理の美味しさの総和は 0 です。種類 1 の料理をトレーに載せます。
• 1 秒目の時点でトレーに載っている料理の美味しさの総和は 3 です。種類 2 の料理をトレーに載せます。
• 2 秒目の時点でトレーに載っている料理の美味しさの総和は 6 です。種類 3 の料理をトレーに載せます。
• 3 秒目の時点でトレーに載っている料理の美味しさの総和は 10 です。
• このケースは部分点の追加制約を満たしません。

入力例 3

3 5
9 9 4
2 2 6

出力例 3

1

• 以下のような料理の取り方をすることで、時刻 1 にトレーに載っている料理の美味しさの総和が 5 以上にすることが可能です。
• 0 秒目の時点でトレーに載っている料理の美味しさの総和は 0 です。種類 3 の料理をトレーに載せます。
• 1 秒目の時点でトレーに載っている料理の美味しさの総和は 6 です。
• このケースは部分点の追加制約を満たします。

入力例 4

5 101
1 2 3 4 5
20 20 20 20 20

出力例 4

-1

• どのように料理をとっても、トレーに載っている料理の美味しさの総和を 101 以上にすることはできません。
• このケースは部分点の追加制約を満たします。

入力例 5

2 2
1 1
1 1

出力例 5

-1

• 時刻 0 でどちらの料理をとっても、もう片方の料理が時刻 1 でなくなってしまうため、トレーに載っている料理の美味しさを 2 以上にすることはできません。
• このケースは部分点の追加制約を満たします。

入力例 6

4 6
1 1 2 2
3 4 1 2

出力例 6

2

• 以下のような料理の取り方をすることで、時刻 2 にトレーに載っている料理の美味しさの総和が 6 以上にすることが可能です。
• 0 秒目の時点でトレーに載っている料理の美味しさの総和は 0 です。種類 2 の料理をトレーに載せます。
• 1 秒目の時点でトレーに載っている料理の美味しさの総和は 4 です。種類 4 の料理をトレーに載せます。
• 2 秒目の時点でトレーに載っている料理の美味しさの総和は 6 です。
• このケースは部分点の追加制約を満たします。

入力例 7

3 4
1 2 2
1 2 2

出力例 7

2

• 以下のような料理の取り方をすることで、時刻 2 にトレーに載っている料理の美味しさの総和が 4 以上にすることが可能です。
• 0 秒目の時点でトレーに載っている料理の美味しさの総和は 0 です。種類 2 の料理をトレーに載せます。
• 1 秒目の時点でトレーに載っている料理の美味しさの総和は 2 です。種類 3 の料理をトレーに載せます。
• 2 秒目の時点でトレーに載っている料理の美味しさの総和は 4 です。
• このケースは部分点の追加制約を満たしません。

問題文

あなたは特別講演「括弧列と塗り分け」の講演者です。今日は(と)だけからなる文字列 S に対する色の塗り分け方を紹介することにしました。 S は括弧の対応に矛盾がないことが保証されます。

S 中の全ての文字を赤色か青色に塗ることを考えます。 その際 i 番目の文字である(と j 番目の文字である)が対応しているならば、 S の i 文字目から j 文字目までの 部分文字列 S[i,j] に含まれる赤色の文字の数を R、青色の文字の数を B としたときに、 |R-B|≦K を満たすように塗らなくてはなりません。

条件を満たす色の塗り方の総数を 1,000,000,007 で割った余りを求めてください。

この問題において、括弧の対応に矛盾がない文字列とは以下のように定義されます。

1. 空文字列は括弧の対応に矛盾がない文字列である。
2. 括弧の対応に矛盾がない文字列 A,B に対し、 A と B を結合してできる文字列 AB も括弧の対応に矛盾がない文字列である。
3. 括弧の対応に矛盾がない文字列 A に対し、文字列(A) は括弧の対応に矛盾がない文字列である。また、この両端の(と)は対応していると呼ばれる。
4. 上記のいずれも満たさない文字列は括弧の対応に矛盾がある文字列である。

入力例 1

()()
0

出力例 1

4

• 1 文字目の(と 2 文字目の)が、3 文字目の(と 4 文字目の)が対応関係にあります。
• 便宜上赤色で塗られた括弧を<>、青色で塗られた括弧を[]で表すことにします。
• 答えは<]<]、<][>、[><]、[>[>の 4 通りです。
• <><]のような塗り方は、S[1,2] において |R-B|≦K の制約を満たしません。
• このケースは 1 つ目の部分点制約を満たします。

入力例 2

()()
2

出力例 2

16

• 答えは<><>、<><]、<>[]、<>[>、<]<>、<]<]、<][]、<][>、[><>、[><]、[>[]、[>[>、[]<>、[]<]、[][]、[][>の 16 通りです。
• このケースは 1 つ目の部分点制約を満たします。

入力例 3

(()())
2

出力例 3

50

• 1 文字目の(と 6 文字目の)、2 文字目の(と 3 文字目の)、4 文字目の(と 5 文字目の)が対応関係にあります。
• このケースは 1 つ目の部分点制約を満たします。

入力例 4

()()()()()()()()()()()()()()()()
2

出力例 4

294967268

• 塗り分け方の総数は 4,294,967,296 ですが、 1,000,000,007 で割った余りである 294,967,268 を出力してください。
• このケースは 2 つ目の部分点制約を満たします。

問題文

あなたはDISCO presents ディスカバリーチャンネルプログラミングコンテスト 2016本戦のディスコ社内ツアーの案内人です。

ディスコ本社は N 頂点、 M 本の辺からなる単純有向グラフで表されます。 i 番目の辺は from_i から to_i に向かう辺であり、OあるいはEのどちらかのラベルがついています。

社内ツアーはある頂点 s から出発し、グラフのすべての辺について以下の条件を満たした状態で、ある頂点 t にいるとき終了することが可能です。

• O のラベルがついているならば、その辺は奇数回通った
• E のラベルがついているならば、その辺は偶数回( 0 でも構わない)通った

社内ツアーを無事に終了することが可能な (s,t) の組み合わせの数はいったいいくつあるでしょうか？

入力例 1

2 1
1 2 O

出力例 1

1

• このケースにおいては頂点 1 から頂点 2 に向かって移動したとき、条件を満たします。答えは (1,2) の 1 通りであり、それ以外には存在しません。

入力例 2

2 1
1 2 E

出力例 2

2

• このケースにおいては出発直後に条件を満たしています。答えは (1,1), (2,2) の 2 通りであり、それ以外には存在しません。
• Eのラベルがついた辺は 0 回通ってもよいことに注意してください。

入力例 3

4 2
1 2 O
3 4 E

出力例 3

1

• このケースにおいては頂点 1 から頂点 2 に向かって移動したとき、条件を満たします。答えは (1,2) の 1 通りであり、それ以外には存在しません。
• Eのラベルがついた辺は 0 回通ってもよいことに注意してください。

入力例 4

4 2
1 2 O
3 4 O

出力例 4

0

• このケースにおいては、どのように移動しても条件を満たすことはできません。
• Oのラベルがついているような辺はそれぞれ奇数回通らなくてはならないこと、Eのラベルがついているような辺はそれぞれ偶数回通らなくてはならないことに注意してください。

入力例 5

3 3
1 2 O
2 3 O
3 1 O

出力例 5

3

入力例 6

4 5
1 2 O
2 1 O
2 3 O
3 1 E
2 4 O

出力例 6

1

入力例 7

4 3
1 2 O
2 1 O
3 4 E

出力例 7

2

入力例 8

2 2
1 2 O
2 1 E

出力例 8

2

入力例 9

4 3
1 2 O
1 3 O
1 4 O

出力例 9

0

問題文

あなたはDISCO社の面接を受けています。面接前に 0 個のノードからなる二分探索木 T をあなたは与えられました。

あなたは面接官から以下の Q 個のクエリを与えられた順序で処理しなさいというお題を与えられました。あなたは、 Q 個のクエリを高速に処理して面接官を驚かせることにしました。

クエリの種類を以下に示します。

1. 1 v : T に値が v であるようなノードを適切な位置に挿入せよ。
2. 2 v : T に含まれる値が v であるようなノード u の左部分木 lst と右部分木 rst について、高さの差 h(lst) - h(rst) を出力せよ。
3. 3 v : T に含まれる値が v であるようなノード u に左の子ノードが存在したならば、 u を右回転せよ。左の子ノードが存在しなかったならば-1を出力せよ。
4. 4 v : T に含まれる値が v であるようなノード u に右の子ノードが存在したならば、 u を左回転せよ。右の子ノードが存在しなかったならば-1を出力せよ。

上記の種類 1 のクエリにおいて、値が v であるようなノードが T に存在しないことが保証されます。 上記の種類 2,3,4 のクエリにおいて、値が v であるようなノードが T に存在することが保証されます。

• ここで、二分探索木 T の高さは以下のように定義される。

  • あるノード u を根とする二分探索木の高さ h(u) は u の左部分木 lst と u の右部分木 rst としたとき、 h(u) = max(h(lst), h(rst))+1 で表される。
  • ここで、 u に左部分木 lst が存在しないときは h(lst) = 0 として扱う。
  • 同様に、 u に右部分木 rst が存在しないときは h(rst) = 0 として扱う。

• 二分探索木 T へノード u を挿入する操作は以下のようにして行われる。なお、この操作の結果は T と u が与えられたとき一意に定まることが保証されている。

  1. T が 0 個のノードからなるとき、 T を u を根とする二分探索木にし処理を終了する。

  2. T が 1 個以上のノードからなるとき、以下の条件を満たすように u をあるノードの子にし、処理を終了する。

     • あるノード w が持つ直接の子の数は最大でもたかだか 2 つである(これはそれぞれ左の子、右の子と呼ばれる)。
     • あるノード w の左の子孫であるようなノードが持つ値はどれも w の値未満である。
     • あるノード w の右の子孫であるようなノードが持つ値はどれも w の値以上である。

• 二分探索木 T に含まれるノード u の右回転は以下のようにして行われる。この操作は u に左の子が存在しないとき行うことはできない。

  1. u の左の子を l とする。
  2. u と l をつなぐ辺を削除する。また、 u に親 p が存在するとき、 u と p をつなぐ辺を削除し、 p を l の親となるように接続する。
  3. l に右の子 r が存在するならば、 l と r をつなぐ辺を削除し、 r を u の左の子となるように接続する。
  4. u を l の右の子となるように接続する。

• 二分探索木 T に含まれるノード u の左回転は以下のようにして行われる。この操作は u に右の子が存在しないとき行うことはできない。

  1. u の右の子を r とする。
  2. u と r をつなぐ辺を削除する。また、 u に親 p が存在するとき、 u と p をつなぐ辺を削除し、 p を r の親となるように接続する。
  3. r に左の子 l が存在するならば、 r と l をつなぐ辺を削除し、 l を u の右の子となるように接続する。
  4. u を r の左の子となるように接続する。

入力例 1

13
1 4
1 2
1 1
1 3
1 6
1 5
1 7
1 8
2 1
2 2
2 4
2 6
2 7

出力例 1

0
0
-1
-1
-1

• 1 番目から 8 番目までのクエリにおいて T にノードをクエリで与えられた順序に従って挿入します。挿入の際、回転操作は行われないことに注意してください。
• 以下の図に 8 番目のクエリが行われた後の T を示します。
• ノード内に書かれた値は、ノードが持つ値を、ノードの横に書かれた値はそのノードを根とする部分木の高さを示します。
• 与えられたクエリによって T の形状は一意に定まることが保証されます。
• 9 番目のクエリにおいて、値が 1 であるようなノードの左部分木の高さ h(lst) と右部分木の高さ h(rst) はともに 0 なので h(lst)-h(rst)は 0 です。
• 10 番目のクエリにおいて、 h(lst) と h(rst) はともに 1 なので h(lst)-h(rst)は 0 です。
• 11 番目のクエリにおいて、 h(lst) は 2 、 h(rst) は 3 なので h(lst)-h(rst)は -1 です。
• 12 番目のクエリにおいて、 h(lst) は 1 、 h(rst) は 2 なので h(lst)-h(rst)は -1 です。
• 13 番目のクエリにおいて、 h(lst) は 0 、 h(rst) は 1 なので h(lst)-h(rst)は -1 です。
• 子が存在しないような部分木の高さは 0 となることに注意してください。
• このケースは 2 つの部分点制約の両方の部分点制約を満たします。

図 1 : 8 番目のクエリ終了時点での T の様子

入力例 2

14
1 4
1 2
1 1
1 3
1 6
1 5
1 7
1 8
3 4
2 2
2 4
2 6
2 7
3 7

出力例 2

-3
-2
-1
-1
-1

• 以下の図に 9 番目のクエリにより右回転が行われる前の T を左に、回転後の T を右に示します。
• ノード同士の位置関係の変化に注意してください。
• 14 番目のクエリにおいて、 値が 7 であるようなノードに左の子は存在しないため、-1を出力してください。
• 与えられたクエリによって T の形状は一意に定まることが保証されます。
• このケースは 1 つ目の部分点制約を満たします。

図 2 : 9 番目のクエリによる T の変形の様子

入力例 3

14
1 4
1 2
1 1
1 3
1 6
1 5
1 7
1 8
4 6
2 2
2 4
2 6
2 7
4 6

出力例 3

0
-1
1
1
-1

• 以下の図に 9 番目のクエリにより左回転が行われる前の T を左に、回転後の T を右に示します。
• ノード同士の位置関係の変化に注意してください。
• 14 番目のクエリにおいて、 値が 6 であるようなノードに右の子は存在しないため、-1を出力してください。
• 与えられたクエリによって T の形状は一意に定まることが保証されます。
• このケースは 1 つ目の部分点制約を満たします。

図 3 : 9 番目のクエリによる T の変形の様子