AtCoder Beginner Contest 103

A - Task Scheduling Problem

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

配点 : 100 点

問題文

3 個のタスクがあり、あなたは全てのタスクを完了させなければなりません。

はじめ、任意の 1 個のタスクをコスト 0 で完了できます。

また、i 番目のタスクを完了した直後にコスト |A_j - A_i| で j 番目のタスクを完了できます。

ここで |x| は x の絶対値を表します。

全てのタスクを完了するのに要する合計コストの最小値を求めてください。

制約

入力は全て整数である
1 \leq A_1, A_2, A_3 \leq 100

入力

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

A_1 A_2 A_3

出力

全てのタスクを完了するのに要する合計コストの最小値を出力せよ。

入力例 1

1 6 3

出力例 1

以下の順番でタスクを完了させたとき、合計コストは 5 となり最小です。

1 番目のタスクをコスト 0 で完了させます
3 番目のタスクをコスト 2 で完了させます
2 番目のタスクをコスト 3 で完了させます

入力例 2

11 5 5

出力例 2

入力例 3

100 100 100

出力例 3

Score : 100 points

Problem Statement

You have three tasks, all of which need to be completed.

First, you can complete any one task at cost 0.

Then, just after completing the i-th task, you can complete the j-th task at cost |A_j - A_i|.

Here, |x| denotes the absolute value of x.

Find the minimum total cost required to complete all the task.

Constraints

All values in input are integers.
1 \leq A_1, A_2, A_3 \leq 100

Input

Input is given from Standard Input in the following format:

A_1 A_2 A_3

Output

Print the minimum total cost required to complete all the task.

Sample Input 1

1 6 3

Sample Output 1

When the tasks are completed in the following order, the total cost will be 5, which is the minimum:

Complete the first task at cost 0.
Complete the third task at cost 2.
Complete the second task at cost 3.

Sample Input 2

11 5 5

Sample Output 2

Sample Input 3

100 100 100

Sample Output 3

B - String Rotation

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

配点 : 200 点

問題文

英小文字からなる文字列 S, T が与えられます。

S を回転させて T に一致させられるか判定してください。

すなわち、以下の操作を任意の回数繰り返して S を T に一致させられるか判定してください。

操作: S = S_1 S_2 ... S_{|S|} のとき、S を S_{|S|} S_1 S_2 ... S_{|S|-1} に変更する

ここで、|X| は文字列 X の長さを表します。

制約

2 \leq |S| \leq 100
|S| = |T|
S, T は英小文字からなる

入力

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

S
T

出力

S を回転させて T に一致させられる場合は Yes、一致させられない場合は No を出力せよ。

入力例 1

kyoto
tokyo

出力例 1

Yes

1 回目の操作で kyoto が okyot になります
2 回目の操作で okyot が tokyo になります

入力例 2

abc
arc

出力例 2

No

何度操作を行っても abc と arc を一致させられません。

入力例 3

aaaaaaaaaaaaaaab
aaaaaaaaaaaaaaab

出力例 3

Yes

Score : 200 points

Problem Statement

You are given string S and T consisting of lowercase English letters.

Determine if S equals T after rotation.

That is, determine if S equals T after the following operation is performed some number of times:

Operation: Let S = S_1 S_2 ... S_{|S|}. Change S to S_{|S|} S_1 S_2 ... S_{|S|-1}.

Here, |X| denotes the length of the string X.

Constraints

2 \leq |S| \leq 100
|S| = |T|
S and T consist of lowercase English letters.

Input

Input is given from Standard Input in the following format:

S
T

Output

If S equals T after rotation, print Yes; if it does not, print No.

Sample Input 1

kyoto
tokyo

Sample Output 1

Yes

In the first operation, kyoto becomes okyot.
In the second operation, okyot becomes tokyo.

Sample Input 2

abc
arc

Sample Output 2

No

abc does not equal arc after any number of operations.

Sample Input 3

aaaaaaaaaaaaaaab
aaaaaaaaaaaaaaab

Sample Output 3

Yes

C - Modulo Summation

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

配点 : 300 点

問題文

N 個の正整数 a_1, a_2, ..., a_N が与えられます。

非負整数 m に対して、f(m) = (m\ mod\ a_1) + (m\ mod\ a_2) + ... + (m\ mod\ a_N) とします。

ここで、X\ mod\ Y は X を Y で割った余りを表します。

f の最大値を求めてください。

制約

入力は全て整数である
2 \leq N \leq 3000
2 \leq a_i \leq 10^5

入力

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

N
a_1 a_2 ... a_N

出力

f の最大値を出力せよ。

入力例 1

3
3 4 6

出力例 1

f(11) = (11\ mod\ 3) + (11\ mod\ 4) + (11\ mod\ 6) = 10 が f の最大値です。

入力例 2

5
7 46 11 20 11

出力例 2

入力例 3

7
994 518 941 851 647 2 581

出力例 3

Score : 300 points

Problem Statement

You are given N positive integers a_1, a_2, ..., a_N.

For a non-negative integer m, let f(m) = (m\ mod\ a_1) + (m\ mod\ a_2) + ... + (m\ mod\ a_N).

Here, X\ mod\ Y denotes the remainder of the division of X by Y.

Find the maximum value of f.

Constraints

All values in input are integers.
2 \leq N \leq 3000
2 \leq a_i \leq 10^5

Input

Input is given from Standard Input in the following format:

N
a_1 a_2 ... a_N

Output

Print the maximum value of f.

Sample Input 1

3
3 4 6

Sample Output 1

f(11) = (11\ mod\ 3) + (11\ mod\ 4) + (11\ mod\ 6) = 10 is the maximum value of f.

Sample Input 2

5
7 46 11 20 11

Sample Output 2

Sample Input 3

7
994 518 941 851 647 2 581

Sample Output 3

D - Islands War

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

配点 : 400 点

問題文

東西一列に並んだ N 個の島と N-1 本の橋があります。

i 番目の橋は、西から i 番目の島と西から i+1 番目の島を接続しています。

ある日、いくつかの島同士で争いが起こり、島の住人たちから M 個の要望がありました。

要望 i: 西から a_i 番目の島と西から b_i 番目の島の間で争いが起こったために、これらの島をいくつかの橋を渡って行き来できないようにしてほしい

あなたは橋をいくつか取り除くことでこれら M 個の要望全てを叶えることにしました。

取り除く必要のある橋の本数の最小値を求めてください。

制約

入力は全て整数である
2 \leq N \leq 10^5
1 \leq M \leq 10^5
1 \leq a_i < b_i \leq N
組 (a_i, b_i) は全て異なる

入力

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

N M
a_1 b_1
a_2 b_2
:
a_M b_M

出力

取り除く必要のある橋の本数の最小値を出力せよ。

入力例 1

5 2
1 4
2 5

出力例 1

西から 2 番目の島と 3 番目の島を接続する橋を取り除くことで達成できます。

入力例 2

出力例 2

入力例 3

出力例 3

Score : 400 points

Problem Statement

There are N islands lining up from west to east, connected by N-1 bridges.

The i-th bridge connects the i-th island from the west and the (i+1)-th island from the west.

One day, disputes took place between some islands, and there were M requests from the inhabitants of the islands:

Request i: A dispute took place between the a_i-th island from the west and the b_i-th island from the west. Please make traveling between these islands with bridges impossible.

You decided to remove some bridges to meet all these M requests.

Find the minimum number of bridges that must be removed.

Constraints

All values in input are integers.
2 \leq N \leq 10^5
1 \leq M \leq 10^5
1 \leq a_i < b_i \leq N
All pairs (a_i, b_i) are distinct.

Input

Input is given from Standard Input in the following format:

N M
a_1 b_1
a_2 b_2
:
a_M b_M

Output

Print the minimum number of bridges that must be removed.

Sample Input 1

5 2
1 4
2 5

Sample Output 1

The requests can be met by removing the bridge connecting the second and third islands from the west.

Sample Input 2

Sample Output 2

Sample Input 3