問題文

かがみずくんはめちゃくちゃ太っています．そのため，近頃，身体に良さそうなことをいろいろ行っています．

かがみずくんは，日光浴のため屋上へ行きたいのですが，その体重のせいで屋上へ行くために必要なはしごを壊してしまいました．

仕方ないので何か代替手段を用いて屋上に行かなければならないのですが，室内には無造作に積まれたコンクリートブロックしかありません．そこで，賢いかがみずくんは，コンクリートブロックを階段状に積み，それらを用いて屋上に行こうとしました．

状況を整理しましょう．今，屋上は高さ N+1 の位置にあります．そして，それぞれ高さ 1 のコンクリートブロックが，合計ちょうど \frac{N(N+1)}{2} (=1+2+...+N)個，N 箇所の位置に無造作に積まれ，ブロック山になっています．

ブロック山は一直線に並んでいます．かがみずくんは高さ 1 の段差しか登ることができないので，屋上から遠いほうから近いほうへ 1 段, 2 段, ..., N 段と階段をつくりたいです．

かがみずくんが，あるブロック山の一番上にあるブロックを，別の位置のブロック山の一番上に置くことを，一回の操作と定義しましょう．

例えば，今 N=4 として，最初ブロック山が遠い方から近い方に「3 段，1 段，5 段，1 段」というふうに段積まれているとしましょう．これらを階段にするために，下図のような操作がひとつの例として考えられます．

あなたの仕事は，無造作に置かれた N 箇所のブロック山の初期状態が与えられるので，かがみずくんが屋上へ行くための階段を構築するのに最低で何回の操作をする必要があるかを数えることです．

課題

N 要素の非負整数列 A が与えられる．A の要素の総和は \frac{N(N+1)}{2} (=1+2+...+N) である．

いま，1 回の操作で A の好きな要素の値を 1 だけ減らし，かわりに他の好きな要素の値を 1 だけ増やすことができる．

i = 1, ..., N に対し A_i = i が成り立つような状態にするために最低限必要な操作の回数を求めよ．

制約

すべての入力データは以下の制約を満たす．

• 1 ≦ N ≦ 100．

入力例 1

3
3
2
1

出力例 1

2

A_1 を減らして A_3 を増やす操作を 2 回行えばよい．

入力例 2

4
3
1
5
1

出力例 2

4

入力例 3

5
7
8
0
0
0

出力例 3

12

問題文

　かがみずくんはかつてめちゃくちゃコミュニケーション能力が低かったため，みんなと友達になるために必要な交友関係を壊してしまいました． それからというもの，かがみずくんはその辛い経験を活かし，コミュニケーション能力を鍛え，みんなと友達になろうとしています．

　かがみず君も含め，かがみずくんが友達になろうとしている人々はそれぞれ自分自身のコミュニケーション能力を把握しており，１つの整数値で表されます． コミュニケーション力が違う人間同士が友達になるのは大変であり，ある人物とある人物が友達になるとき，コミュニケーション能力の差だけ労力がかかります．

　かがみずくんはポジティブなので，友達はもちろんのこと，友達の友達，友達の友達の友達....と，交友関係をたどってたどり着ける人物は等しく友達だと思い込んでいます． ところで，かがみずくんには謎のこだわりがあり，この順番で友達になりたい...という考えがあります．それもちゃんと達成したいです．

かがみずくんは他力本願なので，他人が都合よく友達同士になってくれて，自分も都合よく友達になったときにかかる，全関係構築の労力の差の最小値を知りたいです．

課題

状況を整理しましょう．かつて -∞ だったかがみずくんのコミュニケーション能力はいまや M です．そして， N 人の人物のコミュニケーション能力は c_1,\ c_2,\ ...,\ c_N と表されます．それぞれの人のコミュニケーション能力は整数値です. 「かがみずくんがある人物と友達である」というのは，直接の友達はもちろんのこと，友達の友達，友達の友達の友達....と，交友関係をたどってたどり着ける人物である状態のことを言います． かがみずくんは N 人と友達になりたいのですが，こだわりがあるので，必ず1 番目の人，2 番目の人，...，N 番目の人，という順番に友達になりたいです． 現在，かがみずくんやその N 人は誰とも友達関係にありません．また，コミュニケーション能力が x の人物とコミュニケーション能力 y の人物が友達になるには |x - y| の労力が必要です. この状況において，かがみずくんが全員と友達になる場合において，全体でかかる労力の総和のありうる最小値を出力しなさい．

制約

• 1 ≦ N ≦ 10^5.
• 1 ≦ M, c_i ≦ 10^{13}.

入力例1

3 3
2
7
1

出力例1

6

制約から，かがみずくんは，1 番目の人物，2 番目の人物，3 番目の人物と順番に友達にならなければならないことに注意せよ．

• まず，1 番目の人物と友達になるには労力 |3 - 2| = 1 が必要である.
• 次に，2 番目の人物と友達になるための労力は, かがみずくんが |3 - 7| = 4 , 人物1 が |2 - 7| = 5 である. そこで, かがみずくんが友達になることで労力 4 で友達になれる.
• 同様にして，1 番目の人物と3 番目の人物が友達になることで，かがみずくんは |2 - 1| = 1の労力で3番目の人物と友達になれる．

この説明を表した図が以下のようになる．

問題文

岩井君はよく山に登る, 山登りのプロです(事実). 今日, 岩井くんは, 奇抜な形状をしていることで有名な窮理山への登山に挑戦します.

岩井君は窮理山の山頂まで登りたいです. また, 頂上で最高の眺めを楽しみ, できるだけ登山時に消耗する体力を減らすため, 岩井君はいつも山頂までたどり着くためのの最短ルートを使い登山をします. しかし窮理山ではよく土砂崩れが発生し, 道を通ることができなくなることがあります. さらにこの山は誰も管理していないので, 一度土砂崩れが起きるとその道を通ることは2度とできなくなります.

岩井君は山に登りに行く際, それまでに得られた土砂崩れの情報から, 登山コースを決めています. 山道の形と時系列順に並んだ土砂崩れの情報が与えられるので, それぞれの情報の後で利用できる最短ルートの距離を, コンピュータサイエンスの力で岩井君に教えてあげてください.

課題

N 頂点からなる根付き木と Q 個のクエリが与えられる. それぞれの頂点には 1 から N の整数の番号が付いており, 頂点 1 がこの木の根である. 頂点 i(≧2) は頂点 p_i(＜i) を親に持ち, p_i と i を繋ぐ辺はコスト w_i を持つ.

最初，全ての辺を使用できる．それぞれのクエリは "辺 (x_i,p_{x_i}) を今後使用してはいけない" というクエリであり, あるクエリの前までに使用できなくなった辺は後のクエリでも使用できないままとする. それぞれのクエリを実行した後に, ある葉の頂点から頂点 1 までのパスのコストの和の最小値を出力せよ. ただし, どの葉の頂点からも頂点 1 に辿りつけない場合は −1 を出力せよ.

制約

すべての入力データは以下の制約を満たす．

• 3≦N≦10^5
• 1≦Q≦N−1
• 1≦w_i≦10^3
• 2≦x_i≦N

また，この問題には部分点が設定されており，1 点分の入力データは追加で以下の制約を満たす．

• N≦10^3

入力例1

10 5
1 5
2 6
2 3
1 2
5 1
5 8
7 2
7 2
2 9
4
6
3
7
2

出力例1

3
11
12
14
-1

図は以下の通りとなる．

問題文

カズマ君は球感波(キュウカンバ)小学校の運動会に来ています. この運動会では N 個の競技が実施され, それぞれの競技には 0 から N - 1 の整数の番号が着いています.

i 番目の競技は時刻 A_i に始まって時刻 B_i に終わり, カズマ君はこの競技に参加すると F_i の楽しさを得ることができます.

球感波小学校の校庭は広いため, 複数の競技を同時に行うことができます. つまり, N 種類の競技のうち複数個の競技時間が重複することがあります.

カズマ君は開催時間が重なっている競技には参加出来ません. ただし, ある競技が終わった直後に始まる別の競技には参加できます. すなわち, 終了時間と開始時間が同じ競技に参加することは可能です.

カズマ君はできるだけ運動会を楽しみたいと思っていますが, 真夏の炎天下では長い時間運動会に参加するほど体力が消耗され, その分楽しさも減ってしまいます. 具体的には, 1 単位時間運動会に参加すると C だけカズマ君の楽しさは減少します. また, このとき競技に参加していなくても体力は減少し続けます.

カズマ君はインドア派なので, 効率的に運動会に参加して暑さを免れたいです. すなわち, カズマ君は好きな時刻から運動会に参加し始めても良いし, 好きな時間に帰っても良いです.

このとき, カズマ君が得られる楽しさの最大値を求めて下さい.

課題

N 個の区間が整数列 A, B によって与えられる．i 番目の区間は半開区間 [A_i, B_i) （A_i は含むが B_i は含まない）である．また，各区間には非負整数の重みがついており，i 番目の区間の重みは F_i である．

与えられた区間の中から, 互いに重なっていない 0 個以上の区間を選ぶことを考え, 選ばれた区間の番号の集合を G としよう.

このとき, L = min \{A_i | i \in G \}, R = max\{B_i | i \in G\} としたときに,　非負整数の定数 C を用いた値 (Σ _{i \in G} F_i) - C \times (R - L) を G のスコアと呼ぶことにする. ただし G が空集合のときのスコアは 0 とする.

うまく G の要素を選んだときのスコアを最大化せよ.

制約

すべての入力データは以下の制約を満たす．

• 1 ≦ N ≦ 10^5.
• 0 ≦ C ≦ 10^4.
• 0 ≦ A_i ＜ B_i ≦ 10^5.
• 0 ≦ F_i ≦ 10^4.

また，この問題には部分点が設定されており，1 点分の入力データは追加で以下の制約を満たす．

• N ≦ 1000.

入力例 1

5 3
1 4 12
3 6 7
2 3 6
4 8 8
8 9 10

出力例 1

7

5 番目の区間を選ぶと, その集合のスコアは 7 となり, スコアの最大値を達成できる.

入力例 2

5 2
1 4 12
3 6 7
2 3 6
4 8 8
8 9 10

出力例 2

14

問題文

狐のジャップルさんは, 日々 K4PC (Kool code for Programming Contest) に出題する問題を考えています.

今日, 彼はこのような問題を思いつきました.

Do use Dynamic Programming

問題文

スーパーの生鮮食品コーナーには N 本の胡瓜が売られています. レジで会計をするときに, 生鮮食品コーナーで買った胡瓜の重さの合計が W 以下だと, 生産者のミカミさん直筆のサインが貰えます.

ケンスケくんはミカミさんの作る胡瓜が大好きなので, 出来るだけ多くのサインが欲しいです. ケンスケくんの為に, ミカミさんからサインを貰う方法の個数を求めて挙げて下さい.

課題

N 個の荷物があって, それぞれの荷物には正整数の重さ a_i (1 ≦ i ≦ N) が付いている.

重さの和が W 以下となるような荷物の集合の個数を求めよ.

---

制約

• 1 ≦ N ≦ 1000.
• 1 ≦ W ≦ 1000.
• 1 ≦ a_i ≦ 1000.

---

入力

N W
a_1
a_2
…
a_N

出力

問題の解を 1 行に出力せよ.

---

入力例 1

4 4
1
1
2
3

出力例 1

11

\{\},\ \{a_1\},\ \{a_2\},\ \{a_3\},\ \{a_4\},\ \{a_1,\ a_2\},\ \{a_1,\ a_3\},\ \{a_2,\ a_3\},\ \{a_1,\ a_4\},\ \{a_2,\ a_4\},\ \{a_1,\ a_2,\ a_3\} が条件を満たす荷物の集合である.

ジャップルさんはこの問題が簡単過ぎる気がしてきたため, 次のような問題を思いつきました.

課題

問題 " Do use Dynamic Programming " (問題文を参照) の入力であって, 答えが x となるようなものを 1 つ出力せよ.

制約

すべての入力データは以下の制約を満たす．

• 1 ≦ x ≦ 10^{18}.

この制約条件のもとで，条件を満たすような答が存在することが保証されている．(13:51 追記)

また，この問題には部分点が設定されており，2 点分の入力データは追加で以下の制約を満たす．

• x ≦ 1000.

入力例 1

11

出力例 1

4 4
1
1
2
3

問題文

カガミズさんは息子のキュウリ君にあげるクリスマスプレゼントを考えています．

カガミズさんにはある懸念があります．キュウリ君は競技プログラミングが大好きなので，コンテストでよくある変な問題文に触発されて，プレゼントに配列が欲しいとかグラフが欲しいとか言われてしまうおそれがあるのです．

急に言われて慌てるよりは，早い内に聞いておくほうがよいと考えたカガミズさんは，クリスマスプレゼントにほしいものをキュウリ君に尋ねました．すると，キュウリ君は次のように答えました．

「今から言う問題に対する自然な問題設定がほしい！」

課題

1 次元空間上に N 個の点があり，i 番目の点 P_i の座標は X_i である．

いま，新たにいくつかの点を加えることで N 個の点がある条件を満たすようにしたい．その条件は N 要素の整数列 K, D によって次のように表される．

• 条件: i = 1, ..., N に対し，点 P_i から K_i 番目に近い点までの距離が D_i である．ただし，2 点間の距離はその座標の差の絶対値とする．

距離を考える点の対象は新たに加えた点だけではなく，元からある N 個の点も考慮する．つまり，ある点から 1 番近い点は自分自身と考えられる．

いくつかの点を加えることで上の条件を満たすことができるかどうかを判定せよ．もし可能な場合は，加える点の個数を 10^5 個以下にできるかどうかも判定し，それも可能な場合は加える点の座標の具体例を 1 つ求めよ．

ただし，X_i, D_i および加える点の座標はすべて整数であるとする．また，加える点の座標は 32 ビット符号付き整数の表現できる範囲内に収まっていなければならない．

元からある N 個の点や加える点については，同じ座標に複数の点があってもよいことに注意せよ．

制約

すべての入力データは以下の制約を満たす．

• 1 ≦ N ≦ 10^3．
• -10^9 ≦ X_i ≦ 10^9．
• 1 ≦ K_i ≦ 10^9．
• 0 ≦ D_i ≦ 10^9．

また，この問題には部分点が設定されており，2 点分の入力データは追加で以下の制約を満たす．

• N ≦ 10．
• K_i = 2．

入力例1

2
0 2 1
2 2 1

出力例1

1
1

加える点の個数は 10^5 以下でありさえすれば最小である必要はないので，以下のような出力もこの問題では許可される．

2
-1 1

入力例2

2
0 2 1
3 2 1

出力例2

2
-1 2

入力例3

1
1 1 1

出力例3

impossible

ある点に最も近い点は自分自身であり，その距離は 0 であることに注意せよ．

入力例4

1
1 114514 1

出力例4

too many

たとえば座標 2 に 114,513 個の点を置けば条件を満たすことはできる．ただし，10^5 個以内では条件を満たすことができないため too many を出力する．

入力例5

1
1 1 0

出力例5

0

16:05 部分点のテストデータは全て正しいのですが, テストデータが不完全であるかもしれないという情報を先に提示していたので, G 問題の部分点もコンテストの得点の対象外とさせていただきます.誤解を招く表記をしてしまい申し訳ありません.

15:46 現在のデータにミスが有ることが発覚しました. 部分点のケースの投稿は可能ですが, G 問題はコンテストの得点対象外とさせてください. 報告が遅くなってしまい, 大変申し訳ありませんでした.

13:55 現在のデータは「昨日の深夜に問題が発覚した後，japlj が寝ぼけ眼で必死に作りなおして一切チェックされていないデータ」です．今はこのデータの正当性をチェックしているところですが，ほぼ眠りかけの japlj の書いたコードを信じる人は提出してもいいかもしれません．（オススメしません）

13:00 開催前日の夜になって G 問題のテストデータの不備が発覚した運営！果たしてコンテスト中に正しいテストデータに差し替えることはできるのか！？！？スタッフの活躍に乞うご期待！！！！！（すみません，データ直るまで提出しないでください）

問題文

ミズゴロ王国のカガミズ王は出る杭を打つのが大好きです．毎日のように家来を一列に並べては，渾身のハイドロポンプで出っぱっている人の身長を縮めて楽しんでいます．

カガミズ王の側近であるあなたは，王がハイドロポンプの餌食とする家来を選ぶときに，単に身長が高い人を選んでいるわけではないことに気がつきました．

王いわく，「何につけてもこの世は中庸が肝心である．端にいない者は誰でも，その身長が両隣の者の身長の平均と同じでなければならないのだ」と．

こうしてカガミズ王はひとしきりハイドロポンプを放った後，皆の身長がその両隣の人の身長の平均と等しくなっているような家来の列を見て悦に入るのでした．

さて，あなたはこの様子を毎日のように見ていてあることを考えました．王が満足するような身長の並びとは何通りぐらいあるのだろうか．条件がこれだけだと無尽蔵に場合があると考えたあなたは，それぞれの場所にいる家来の身長に上限と下限を設けて数えることにしました．

ちなみにミズゴロ王国では人の身長はなぜか必ず整数で，よくわかりませんが身長が 0 だったり負だったりする人もいます．

課題

N 要素の整数列 A, B が与えられる．以下の条件を満たす N 要素の整数列 X は何通りあるか．答えを 1,000,000,007 (= 10^9 + 7) で割ったあまりを求めよ．

• i = 1, ..., N に対し A_i ≦ X_i ≦ B_i．
• i = 2, ..., N - 1 に対し X_i = \frac{X_{i-1} + X_{i+1}}{2}．

制約

すべての入力データは以下の制約を満たす．

• 3 ≦ N ≦ 10^5．
• -10^9 ≦ A_i ≦ B_i ≦ 10^9．

また，この問題には部分点が設定されており，2 点分の入力データは追加で以下の制約を満たす．

• N ≦ 100．
• -100 ≦ A_i ≦ B_i ≦ 100．

入力例 1

3
0 0 0
2 2 2

出力例 1

5

• X_1 = 0,\ X_2 = 0,\ X_3 = 0
• X_1 = 0,\ X_2 = 1,\ X_3 = 2
• X_1 = 1,\ X_2 = 1,\ X_3 = 1
• X_1 = 2,\ X_2 = 1,\ X_3 = 0
• X_1 = 2,\ X_2 = 2,\ X_3 = 2

の 5 つが条件を満たす数列である.

入力例 2

8
-9 -8 -7 -6 -8 -20 -9 -1
6 8 10 16 42 18 14 20

出力例 2

42

入力例 3

3
-1000000000 -1000000000 -1000000000
1000000000 1000000000 1000000000

出力例 3

85

この条件を満たす数列は 2,000,000,002,000,000,001 通りある. 通り数を1,000,000,007 で割ったあまりを出力することに注意せよ.