A - Right Triangle

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 100 点

問題文

直角三角形 ABC があります。∠ABC=90° です。

三角形 ABC の三辺の長さである |AB|,|BC|,|CA| が与えられるので、直角三角形 ABC の面積を求めて下さい。

ただし、三角形 ABC の面積は整数となることが保証されています。

制約

  • 1 \leqq |AB|,|BC|,|CA| \leqq 100
  • 入力はすべて整数である。
  • 三角形 ABC の面積は整数である。

入力

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

|AB| |BC| |CA|

出力

三角形 ABC の面積を出力してください。

入力例 1

3 4 5

出力例 1

6

tri

この三角形の面積は 6 です。

入力例 2

5 12 13

出力例 2

30

この三角形の面積は 30 です。

入力例 3

45 28 53

出力例 3

630

この三角形の面積は 630 です。

Score : 100 points

Problem Statement

There is a right triangle ABC with ∠ABC=90°.

Given the lengths of the three sides, |AB|,|BC| and |CA|, find the area of the right triangle ABC.

It is guaranteed that the area of the triangle ABC is an integer.

Constraints

  • 1 \leq |AB|,|BC|,|CA| \leq 100
  • All values in input are integers.
  • The area of the triangle ABC is an integer.

Input

Input is given from Standard Input in the following format:

|AB| |BC| |CA|

Output

Print the area of the triangle ABC.

Sample Input 1

3 4 5

Sample Output 1

6

tri

This triangle has an area of 6.

Sample Input 2

5 12 13

Sample Output 2

30

This triangle has an area of 30.

Sample Input 3

45 28 53

Sample Output 3

630

This triangle has an area of 630.
B - Collatz Problem

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 200 点

問題文

数列 a=\{a_1,a_2,a_3,......\} は、以下のようにして定まります。

  • 初項 s は入力で与えられる。

  • 関数 f(n) を以下のように定める: n が偶数なら f(n) = n/2、n が奇数なら f(n) = 3n+1。

  • i = 1 のとき a_i = s、i > 1 のとき a_i = f(a_{i-1}) である。

このとき、次の条件を満たす最小の整数 m を求めてください。

  • a_m = a_n (m > n) を満たす整数 n が存在する。

制約

  • 1 \leqq s \leqq 100
  • 入力はすべて整数である。
  • a のすべての要素、および条件を満たす最小の m は 1000000 以下となることが保証される。

入力

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

s

出力

条件を満たす最小の整数 m を出力してください。

入力例 1

8

出力例 1

5

a=\{8,4,2,1,4,2,1,4,2,1,......\} です。a_5=a_2 なので、答えは 5 です。

入力例 2

7

出力例 2

18

a=\{7,22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1,4,2,1,......\} です。

入力例 3

54

出力例 3

114

Score : 200 points

Problem Statement

A sequence a=\{a_1,a_2,a_3,......\} is determined as follows:

  • The first term s is given as input.

  • Let f(n) be the following function: f(n) = n/2 if n is even, and f(n) = 3n+1 if n is odd.

  • a_i = s when i = 1, and a_i = f(a_{i-1}) when i > 1.

Find the minimum integer m that satisfies the following condition:

  • There exists an integer n such that a_m = a_n (m > n).

Constraints

  • 1 \leq s \leq 100
  • All values in input are integers.
  • It is guaranteed that all elements in a and the minimum m that satisfies the condition are at most 1000000.

Input

Input is given from Standard Input in the following format:

s

Output

Print the minimum integer m that satisfies the condition.

Sample Input 1

8

Sample Output 1

5

a=\{8,4,2,1,4,2,1,4,2,1,......\}. As a_5=a_2, the answer is 5.

Sample Input 2

7

Sample Output 2

18

a=\{7,22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1,4,2,1,......\}.

Sample Input 3

54

Sample Output 3

114
C - Grand Garden

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 300 点

問題文

花壇に N 本の花が咲いており、それぞれ 1,2,......,N と番号が振られています。最初、全ての花の高さは 0 です。 数列 h=\{h_1,h_2,h_3,......\} が入力として与えられます。以下の「水やり」操作を繰り返すことで、すべての k(1 \leqq k \leqq N) に対して花 k の高さを h_k にしたいです。

  • 整数 l,r を指定する。l \leqq x \leqq r を満たすすべての x に対して、花 x の高さを 1 高くする。

条件を満たすための最小の「水やり」操作の回数を求めてください。

制約

  • 1 \leqq N \leqq 100
  • 0 \leqq h_i \leqq 100
  • 入力はすべて整数である。

入力

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

N
h_1 h_2 h_3 ...... h_N

出力

条件を満たすような最小の「水やり」操作の回数を出力してください。

入力例 1

4
1 2 2 1

出力例 1

2

「水やり」操作の回数は 2 回が最小です。 以下が一つの例です。

  • (l,r)=(1,3) の「水やり」操作を行う。
  • (l,r)=(2,4) の「水やり」操作を行う。

入力例 2

5
3 1 2 3 1

出力例 2

5

入力例 3

8
4 23 75 0 23 96 50 100

出力例 3

221

Score : 300 points

Problem Statement

In a flower bed, there are N flowers, numbered 1,2,......,N. Initially, the heights of all flowers are 0. You are given a sequence h=\{h_1,h_2,h_3,......\} as input. You would like to change the height of Flower k to h_k for all k (1 \leq k \leq N), by repeating the following "watering" operation:

  • Specify integers l and r. Increase the height of Flower x by 1 for all x such that l \leq x \leq r.

Find the minimum number of watering operations required to satisfy the condition.

Constraints

  • 1 \leq N \leq 100
  • 0 \leq h_i \leq 100
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
h_1 h_2 h_3 ...... h_N

Output

Print the minimum number of watering operations required to satisfy the condition.

Sample Input 1

4
1 2 2 1

Sample Output 1

2

The minimum number of watering operations required is 2. One way to achieve it is:

  • Perform the operation with (l,r)=(1,3).
  • Perform the operation with (l,r)=(2,4).

Sample Input 2

5
3 1 2 3 1

Sample Output 2

5

Sample Input 3

8
4 23 75 0 23 96 50 100

Sample Output 3

221
D - Various Sushi

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 400 点

問題文

N 個の寿司があり、それぞれの寿司には「ネタ」t_i と「おいしさ」d_i のパラメータが設定されています。 あなたはこの N 個の寿司の中から K 個を選んで食べようとしています。 この時のあなたの「満足ポイント」は、以下のようにして計算されます。

  • 「満足ポイント」は、「おいしさ基礎ポイント」と、「種類ボーナスポイント」の和である。
  • 「おいしさ基礎ポイント」は、食べた寿司の「おいしさ」の総和である。
  • 「種類ボーナスポイント」は、食べた寿司の「ネタ」の種類数を x としたとき、x*x である。

あなたは、「満足ポイント」をできるだけ大きくしたいです。 この時の「満足ポイント」の値を求めてください。

制約

  • 1 \leqq K \leqq N \leqq 10^5
  • 1 \leqq t_i \leqq N
  • 1 \leqq d_i \leqq 10^9
  • 入力はすべて整数である。

入力

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

N K
t_1 d_1
t_2 d_2
.
.
.
t_N d_N

出力

あなたの得られる「満足ポイント」の最大値を出力してください。

入力例 1

5 3
1 9
1 7
2 6
2 5
3 1

出力例 1

26

寿司 1,2,3 を食べた時、

  • 「おいしさ基礎ポイント」は、9+7+6=22
  • 「種類ボーナスポイント」は、2*2=4

で、得られる「満足ポイント」は 26 となり、これが最適です。

入力例 2

7 4
1 1
2 1
3 1
4 6
4 5
4 5
4 5

出力例 2

25

寿司 1,2,3,4 を食べるのが最適です。

入力例 3

6 5
5 1000000000
2 990000000
3 980000000
6 970000000
6 960000000
4 950000000

出力例 3

4900000016

出力が 32 bit型整数に収まらない場合もあることに注意して下さい。

Score : 400 points

Problem Statement

There are N pieces of sushi. Each piece has two parameters: "kind of topping" t_i and "deliciousness" d_i. You are choosing K among these N pieces to eat. Your "satisfaction" here will be calculated as follows:

  • The satisfaction is the sum of the "base total deliciousness" and the "variety bonus".
  • The base total deliciousness is the sum of the deliciousness of the pieces you eat.
  • The variety bonus is x*x, where x is the number of different kinds of toppings of the pieces you eat.

You want to have as much satisfaction as possible. Find this maximum satisfaction.

Constraints

  • 1 \leq K \leq N \leq 10^5
  • 1 \leq t_i \leq N
  • 1 \leq d_i \leq 10^9
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N K
t_1 d_1
t_2 d_2
.
.
.
t_N d_N

Output

Print the maximum satisfaction that you can obtain.

Sample Input 1

5 3
1 9
1 7
2 6
2 5
3 1

Sample Output 1

26

If you eat Sushi 1,2 and 3:

  • The base total deliciousness is 9+7+6=22.
  • The variety bonus is 2*2=4.

Thus, your satisfaction will be 26, which is optimal.

Sample Input 2

7 4
1 1
2 1
3 1
4 6
4 5
4 5
4 5

Sample Output 2

25

It is optimal to eat Sushi 1,2,3 and 4.

Sample Input 3

6 5
5 1000000000
2 990000000
3 980000000
6 970000000
6 960000000
4 950000000

Sample Output 3

4900000016

Note that the output may not fit into a 32-bit integer type.