Time Limit: 2 sec / Memory Limit: 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
以下の順番でタスクを完了させたとき、合計コストは 5 となり最小です。
- 1 番目のタスクをコスト 0 で完了させます
- 3 番目のタスクをコスト 2 で完了させます
- 2 番目のタスクをコスト 3 で完了させます
入力例 2
11 5 5
出力例 2
6
入力例 3
100 100 100
出力例 3
0
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
5
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
6
Sample Input 3
100 100 100
Sample Output 3
0
Time Limit: 2 sec / Memory Limit: 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
becomesokyot
. - In the second operation,
okyot
becomestokyo
.
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
Time Limit: 2 sec / Memory Limit: 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
10
f(11) = (11\ mod\ 3) + (11\ mod\ 4) + (11\ mod\ 6) = 10 が f の最大値です。
入力例 2
5 7 46 11 20 11
出力例 2
90
入力例 3
7 994 518 941 851 647 2 581
出力例 3
4527
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
10
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
90
Sample Input 3
7 994 518 941 851 647 2 581
Sample Output 3
4527
Time Limit: 2 sec / Memory Limit: 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
1
西から 2 番目の島と 3 番目の島を接続する橋を取り除くことで達成できます。
入力例 2
9 5 1 8 2 7 3 5 4 6 7 9
出力例 2
2
入力例 3
5 10 1 2 1 3 1 4 1 5 2 3 2 4 2 5 3 4 3 5 4 5
出力例 3
4
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
1
The requests can be met by removing the bridge connecting the second and third islands from the west.
Sample Input 2
9 5 1 8 2 7 3 5 4 6 7 9
Sample Output 2
2
Sample Input 3
5 10 1 2 1 3 1 4 1 5 2 3 2 4 2 5 3 4 3 5 4 5
Sample Output 3
4