A - BMI

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

ぼく、一目惚れをしました。昨日学内ですれ違った彼女の名前、どうしても知りたいんです。いや、名前だけじゃない……！身長も体重も、彼女の全てが知りたい！
でも、僕には彼女に話しかける勇気なんてない。彼女の体重は何 kg なんだろうか...彼女の身長は何 cm くらいなんだろうか...。結局、一晩中彼女のことだけを考えてぜんぜん寝られていない。
さすがに女性にいきなり体重を聞くのは失礼だろう。そんなことは分かっている。そんなものを聞いたりしたら、間違いなく嫌われてしまうだろう。
「うーむ、どうしたものか……ハッ！」
僕の脳内に稲妻が走った。そうだ、身長とBMI(※)を聞けばいいんだ。そうしたら体重を逆算できる。名前はもうどうでもいいや、これは名案だ。
そうと決まれば、 身長[cm] と BMI[kg/m^2] の2つの値に基づいて 体重[kg] を逆算してくれるプログラムを有能プログラマーである君に作ってもらいたい。


※ BMI[kg/m^2] とは、ボディマス指数と呼ばれるもので、以下の計算式で与えられる。ただし、Height と Weight はそれぞれ身長と体重のことである。

入力

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

Height BMI
  • Height (120.0 ≦ Height ≦ 200.0) は、プログラムに与えられる身長[cm]を表す実数である。小数点第 1 位まで与えられる。
  • BMI (10.0 ≦ BMI ≦ 40.0) は、プログラムに与えられる BMI[kg/m^2] を表す実数である。小数点第 1 位まで与えられる。

出力

入力に基づいて逆算した 体重 [kg] を一行に出力せよ。
出力は絶対誤差が 10^{−2} 以下であれば許容される。
なお、出力の最後には改行を入れること。

入力例１

160.0 23.5

出力例１

60.160
160cm = 1.6m であることに注意せよ。
出力誤差の許容範囲については、出力の項をよく見ること。
出力誤差を満たしている出力ならば、例えば 60.16 や 60.1600001、他にも誤差ギリギリではあるが 60.17 等の出力でも正答として扱われる。

入力例２

199.9 11.1

出力例２

44.356
体重 [kg] を逆算すると、 44.3556111kg となる
B - 格子点と整数

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

諸君、私は整数が好きだ。
私は格子点が好きだ。
私は面積が好きだ。
私は三角形が好きだ。
私は座標平面上の、頂点が全て格子点上にある、面積が整数の三角形が大好きだ。
格子点の集合をみたとき、その中の任意の 3 点を選んで作ることができる面積が整数の三角形の個数を数えるときは心が踊る。
心が踊るが、格子点が多いと数えるのが面倒臭い。
ぜひ有能なプログラマーである諸君に私の代わりに数えてほしい。
N 個の格子点を与えるので、その中の任意の 3 点を選んで作ることができる、面積が整数の三角形の個数を数えるプログラムを作って欲しい。面積が 0 の三角形は三角形とは認めん！
ちなみに、格子点というのは座標平面上の点 (x,y) のうち x も y も整数である点のことである。

入力

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

 N  
 x_1   y_1 
 x_2   y_2 
:
 x_N   y_N
  • 1 行目には、格子点の個数を表す整数 N (3 ≦ N ≦ 100) が与えられる。
  • 2 行目から N 行では、2つの整数が空白区切りで与えられる。
    (x_i, y_i)　(1 ≦ x_i, y_i ≦ 10^9) は i 番目の格子点の位置である。同じ格子点が二度与えられることはない。( i \neq j ならば (x_i, y_i) \neq (x_j, y_j) )

出力

N 個の格子点のうち 3 つを選んで作ることができる面積が正の整数である三角形の個数を一行で出力せよ。
なお、出力の最後には改行を入れること。

入力例１

3
1 1
1 2
3 1

出力例１

1
(1,1), (1, 2), (3, 1) の面積が 1 の三角形が一つだけ作れる。

入力例2

3
1 1
1 2
2 1

出力例2

0
三角形 (1, 1) (1, 2) (2, 1) の面積は 0.5 で整数ではない。これ以外に三角形は作ることができない。

入力例3

3
1 1
2 2
3 3

出力例3

0
3 点は一直線上に並ぶので、三角形を作ることができない。

入力例4

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

出力例4

38
C - 席替え

Time Limit: 2 sec / Memory Limit: 256 MB

お知らせ：この問題には欠陥があることが指摘されております。過去問練習を取り組む際には、別の問題を優先することをおすすめいたします。

問題文

僕の学校は各クラスの人数が非常に多い。 1,000,000 人で編成されるクラスもあるくらいだ。
僕のクラスも例外ではない。縦に N 行、横に M 列の長方形状に机が並んでいて、 N \times M 人の生徒が一人一つずつ、自分の机を持っている。
僕の学校は防災意識が高く、もしものときは教室の後ろの壁がはがれてそこから人が避難することができるようになっている。
このたび、避難時には成績のいい人から逃げることができるようにした方がいいという方針になった。というわけで、僕のクラスでは成績の良い人ほど教室の後ろの壁に近いところに座るように席替えをすることになった。 具体的に言うと、教室の一番前の行を第 0 行、 一番左の列を第 0 列として、第 i 行第 j 列の場所にある席のことを (i, j) 、そこに席替え後に座っている人の成績を G[i][j] とすると、ある 2 つの席 (a, b), (c, d) に対して a \gt c ならば b, d の値によらず G[a][b] \geq G[c][d] が常に成り立つように席替えをするということである。
生徒は任意の席へ移動することが可能だが、席替え後に 2 人以上の人が同じ席にいたり、誰も座らない席があってはならない。もちろん、新しく机を増設したり、なくしたりして、 N 行 M 列の形を崩すことも許されない。
席替えをするのは良いが、あいにく人数が非常に大きいので席替えによる各生徒の移動距離の総和を最小限に抑えたい。このとき、生徒の移動距離というのは、移動前後の席の位置のマンハッタン距離である。つまり (a, b) から (c, d) に移動したのならば移動距離は |a - c| + |b - d| である。
席替え前の各席に座っている生徒の成績を与えるので、生徒の総移動距離の最小値を求めてほしい。

入力

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

 N   M 
 x_0   a   p
  • 1 行目には、教室の行の数、列の数をあらわす整数 N , M ( 1 ≦ N, M ≦ 1,000 )が空白区切りで与えられる。
  • 2 行目には、各席に座っている生徒の成績のデータを生成する乱数の種 x_0 ( 0 ≦ x_0 ≦ 10^9 ), a ( 0 ≦ a ≦ 10^9 ), p ( N \times M ≦ p ≦ 10^9 , p は常に素数)が空白区切りで与えられる。 席の数が非常に多いため、席替え前の各席に座っている生徒の成績は上記の3つの変数を種に生成してもらう。 i \geq 1 について x_i = (x_{i-1} + a) mod p の漸化式で与えられる数列 x を考える。 (i, j) に席替え前に座っている生徒の成績は x_{i \times m + j} とする。

出力

席替え時の各生徒の総移動距離の最小値を一行で出力せよ。
なお、出力の最後には改行を入れること。

入力例１

2 3
1 2 59

出力例１

0
席替え前の各席に座っている生徒の成績は以下のようになる。
1  3  5
7  9 11
どの席も自分より後ろ(画面では下)に、自分より成績の悪い人がいないので条件を満たしている。よって席替えの必要はない。

入力例2

2 3
6 55 59

出力例2

2
席替え前の各席に座っている生徒の成績は以下のようになる。
 6  2 57
53 49 45
(0, 2) と (1, 2) が席を交換すれば良い。共に 1 ずつの変化なので総移動距離は 2 である。

入力例3

4 5
15 25 79

出力例3

26
席替え前の各席に座っている生徒の成績は以下のようになる。
15 40 65 11 36
61  7 32 57  3
28 53 78 24 49
74 20 45 70 16
条件を満たす席替えの一例として以下のものがあげられる。
15  7 16 11  3
28 20 32 24 36
53 40 45 57 49
74 61 65 70 78
D - 僕は友達が少ない

Time Limit: 3 sec / Memory Limit: 256 MB

問題文

高橋君の通う大学は、毎年 N 人の新入生を迎え入れています。 N 人の新入生には 1 から N の学籍番号が順番に振られていて、高橋君の学籍番号は 1 です。
さて、4月から大学に通う高橋君は他の N-1 人の新入生全員と友達になりたいと思っています。しかし、それを達成するには非常に費用が掛かることが知られています。
高橋君にとって、"x君と友達である"というのは高橋君の友達の友達の...というふうに交友関係を辿って、x君にたどり着くことが可能な状態のことを指します。

現在、新入生同士はお互いを全く知らず、互いに友達であるような学生はいません。当然、高橋君にも全く友達がいません。しかし、高橋君は特定の2人の学生(高橋君も含むことがあります)について、「少なくともどちらか一方が高橋君の友達もしくは高橋君自身であるような、学籍番号が A の学生と 学籍番号が B の学生を、C 円使って友達同士にする」という形式の手段を M 種類知っています。また、学生によって必要となる費用はバラバラであるため、同じ費用である手段の数はそこまで偏っていません。
最初、高橋君を含めた新入生に友達は全くおらず、高橋君は上記の手段を活用し、新入生全員と友達になることを考えています。また、高橋君はそれ以外の方法で友達を作ることはできません。しかし、高橋君の資金力にも限りがあり、出来るだけ少ない費用で新入生全員と友達になりたいと考えています。高橋君は忙しいので、プログラマーであるあなたに、この企てについての仕事を依頼することにしました。

高橋君からあなたに与えられた仕事を説明します。
まず、あなたには、大学に在籍する高橋君を含む新入生の数 N 、手段の数 M と、 M 種類の手段の情報が与えられます。 N 人の新入生には 1 から N の学籍番号が順番に振られていて、高橋君の学籍番号は 1 です。
あなたの仕事は、高橋君が新入生全員と友達になるために必要な合計の費用と、最小限の費用を達成する手段の選び方が何通りあるかを出力することです。手段を実行する順番のみが異なるものは同じ手段の選び方とみなします。正確には、選び方の数は非常に大きくなってしまうことがあるので、選び方の数を 1,000,000,007 で割った余りを出力してください。

入力

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

N　M
A_1　B_1　C_1
A_2　B_2　C_2
:
A_M B_M C_M
  • 1 行目には、大学に在籍する高橋君を含む新入生の数 N (2 ≦ N ≦ 10,000) と、手段の数 M (1 ≦ M ≦ 100,000) が与えられる。
  • 2 行目から M 行では、手段の情報が与えられる。このうち i (1 ≦ i ≦ M) 行目では、i 番目の手段における 2 人の学生の学籍番号とその費用を表す 3 つの整数 A_i,B_i,C_i (1 ≦ A_i < B_i ≦ N, 1 ≦ C_i ≦ 100,000) が空白区切りで与えられる。M 個の手段は以下の条件を満たす。
    • ある学生の組を直接友達にする手段は1つ以下である。つまり、 i \neq j ならば (A_i, B_i) \neq (A_j, B_j) である。
    • 任意の費用 K について、 (C_i = K であるような手段の数) ≦ 100 が成り立つ。
    • 高橋君が新入生全員と友達になる方法は必ず存在する。

部分点

この問題には部分点が設定されている。
  • 下記の条件を満たすテストケースのみで構成された、 10 点分のセットがある。
    • 手段に必要な費用は全て相異なる。つまり 、 i,j (1≦i,j≦M) において、 i \neq j なら C_i \neq C_j が成立する。
  • 上記のセットを含む全てのテストケースに正解することで、残りの 90 点を得られる。

出力

高橋君が新入生全員と友達となるために必要な最小の費用と、最小の費用を達成する手段の選び方の数を 1,000,000,007 で割った余りを、半角スペース区切りで一行に出力せよ。
なお、出力の最後には改行を入れること。

入力例1

4 4
1 2 4000
2 3 3000
3 4 2000
1 4 1000

出力例1

6000 1
この入力は「手段に必要な費用は全て相異なる」という部分点( 10 点分)の制約を満たしている。
1 番目～ 4 番目の合計 4 種類の手段が存在する。高橋君が全ての新入生と友達になるために必要な最小費用は 6,000 円で、それを達成する手段の組み合わせは次の 1 通りである。
  • 2,3,4 番目の手段を適切な順番で用いる。

    • 具体的に、どのようにして高橋君が学生全員と友達になるのかを説明する。
    1. まず最初に、高橋君には友達がいないので、高橋君(学籍番号 1)が含まれる手段しか用いることができない。したがって、手段 4 を使い、高橋君(学籍番号 1)と学籍番号 4 の学生を友達同士にする。
    2. 次に、この時点で学籍番号 4 の学生は既に高橋君の友達であるため、手段 3 を用いることができる。したがって、手段 3 を用いて、学籍番号 3 の学生と学籍番号 4 の学生を友達同士にする。
    3. 最後に、手段 2 を用いて、学籍番号 2 の学生と学籍番号 3 の学生を友達同士にする。

    以上の順番で手段を用いれば、高橋君は 6,000 円の費用で新入生全員と友達になることができる。

    入力例2

    4 5
1 2 1000
1 3 1000
2 3 2000
2 4 1000
3 4 1000

    出力例2

    3000 4
    1 番目～ 5 番目の合計 5 種類の手段が存在する。高橋君が全ての新入生と友達になるために必要な最小費用は 3,000 円で、それを達成する手段の組み合わせは次の 4 通りである。
  • 2,4,5 番目の手段を適切な順番で用いる。
  • 1,4,5 番目の手段を適切な順番で用いる。
  • 1,2,5 番目の手段を適切な順番で用いる。
  • 2,2,4 番目の手段を適切な順番で用いる。

    • 以下の図は、入力例2と、その答えを視覚的に表したものである。新入生同士を結ぶ線が手段に対応する。
    考えられる手段の選び方は、以下の 4 通りである。

    入力例3

    6 8
1 3 1
1 2 1
2 3 1
2 4 2
3 4 2
3 6 2
4 5 2
5 6 1

    出力例3

    7 15

    入力例4

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

    出力例4

    11 917363797