問題文

n 個のブロックが一列に並んでいます。前から数えて x 個目のブロックだけが青色で、残りはすべて赤色です。

高橋君は、隣り合うブロックを交換する操作を何度か行って、青いブロックが列の端 (前から 1 番目かもしくは n 番目) に来るようにしようとしています。

最小で何回の操作が必要かを求めてください。

制約

• 1 ≦ n ≦ 100
• 1 ≦ x ≦ n

入力例1

5 2

出力例1

1

はじめ、前から 2 番目のブロックが青いので、1 番目と 2 番目のブロックを交換すると青いブロックが端に来ます。

入力例2

6 4

出力例2

2

• まず、4 番目と 5 番目のブロックを交換します。
• 次に 5 番目と 6 番目のブロックを交換すると青いブロックが端に来ます。

入力例3

90 30

出力例3

29

問題文

高橋君は大きさ 1 メートル四方のタイルを n 枚持っています。

高橋君はこれらのタイルのうちいくつかを、重ならないように隙間なく並べて大きな長方形を作ろうとしています。

出来上がる長方形はできるだけ正方形に近いほうがよいですが、同時に、使わずに余るタイルの枚数ができるだけ少なくなるようにしたいと考えています。

長方形の縦と横の長さの差の絶対値と、余ったタイルの枚数の和を最小でいくつにできるでしょうか。

制約

• 1 ≦ n ≦ 100,000

入力例1

26

出力例1

1

5 \times 5 の正方形になるように並べると、縦横の長さの差が 0 で、余るタイルの枚数が 1 となり、その和は 1 です。

26 枚のタイルを余らせることなく使い正方形を作ることはできないので、答えは 1 となります。

入力例2

41

出力例2

4

この場合、5 \times 8 の長方形を作ってタイルを 1 枚余らせるのが最適です。

入力例3

100000

出力例3

37

問題文

N 本の木の柱が左から右へ一列に並んだアスレチックがあります。左から i 本目の柱の高さは a_i センチメートルです。

高橋君は左から 1 本目の柱からスタートし、右へ柱を渡っていき N 本目の柱まで行こうとしています。

高橋君がある柱にいるとき、次には現在の柱から 1 個もしくは 2 個右にある柱のどちらかへ移動することができます。

移動するときには、現在いる柱の高さと、移動後の柱の高さの差の絶対値のぶんだけコストがかかります。

N 本目の柱まで行くとき、コストの合計の最小値はいくらになるでしょうか。

制約

• 2 ≦ N ≦ 100,000
• 0 ≦ a_i ≦ 10,000
• a_i はすべて整数である。

入力例1

4
100 150 130 120

出力例1

40

このケースでは以下のような移動によって最小コストを達成できる。

• 1 本目の柱から 3 本目の柱へ移動する。(コスト 30)
• 3 本目の柱から 4 本目の柱へ移動する。(コスト 10)

合計コストは 40 となる。

入力例2

4
100 125 80 110

出力例2

40

このケースでは以下のような移動によって最小コストを達成できる。

• 1 本目の柱から 2 本目の柱へ移動する。(コスト 25)
• 2 本目の柱から 4 本目の柱へ移動する。(コスト 15)

合計コストは 40 となる。

入力例3

9
314 159 265 358 979 323 846 264 338

出力例3

310

問題文

ある国には N 個の都市があり、それぞれ 1 から N までの番号がつけられています。これらの都市間を結ぶ M 本の道路があり、i 本目の道路は都市 a_i と都市 b_i を結ぶもので、y_i 年に造られたものです。

この国の国民はとても心配性なので、あまりに古い道は事故の危険性が高いと考えて使わないことがあります。そこであなたは、この国の交通状況を調査することにしました。

Q 人の国民の情報が与えられます。j 人目の国民について、都市 v_j に住んでおり、造られた年が w_j 年以前 (w_j 年ちょうども含む) であるような道路を使わないことがわかっています。

それぞれの国民に対し、その人が住んでいる都市から道路のみを使って行き来できるような都市の個数を求めてください。

制約

• 1 ≦ N ≦ 100,000
• 0 ≦ M ≦ 200,000
• 1 ≦ a_i,b_i ≦ N
• a_i ≠ b_i
• 1 ≦ y_i ≦ 200,000
• 1 ≦ Q ≦ 100,000
• 1 ≦ v_j ≦ N
• 0 ≦ w_j ≦ 200,000

部分点

• 50 点分のテストケースでは、N ≦ 1,000, M ≦ 2,000, Q ≦ 1,000 をみたす。

入力例1

5 4
1 2 2000
2 3 2004
3 4 1999
4 5 2001
3
1 2000
1 1999
3 1995

出力例1

1
3
5

Q 人それぞれの国民について、答えは以下のようになります。

• 1 人目は都市 1 に住んでおり、2000 年以前に造られた道を使いません。都市 1 につながる唯一の道は 2000 年に造られているので、都市 1 以外へ行くことができません。したがって答えは 1 となります。
• 2 人目は都市 1 に住んでおり、都市 2 や 3 へ行くことができます。しかし、1999 年以前に造られた道を使わないので都市 4 へ行くことはできません。したがって答えは 3 となります。
• 3 人目は 1995 年以前に造られた道を使いませんが、すべての道はそれより新しいため、すべての道をつかってすべての都市へ行くことができます。したがって答えは 5 となります。

入力例2

4 5
1 2 2005
3 1 2001
3 4 2002
1 4 2004
4 2 2003
5
1 2003
2 2003
1 2001
3 2003
4 2004

出力例2

3
3
4
1
1

入力例3

4 5
1 2 10
1 2 1000
2 3 10000
2 3 100000
3 1 200000
4
1 0
2 10000
3 100000
4 0

出力例3

3
3
2
1

同じふたつの都市間を結ぶ道が 2 本以上あることや、すべての道を使っても辿り着けない都市がありうることに注意してください。