Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 100 点
問題文
2 つの正整数 a, b が与えられます。 a, b の平均値を x とします。 x の小数点以下を切り上げて得られる整数を出力してください。
制約
- a, b は整数である。
- 1 \leq a, b \leq 100
入力
入力は以下の形式で標準入力から与えられる。
a b
出力
x の小数点以下を切り上げて得られる整数を出力せよ。
入力例 1
1 3
出力例 1
2
1, 3 の平均値は 2.0 であり、小数点以下を切り上げて得られる整数は 2 です。
入力例 2
7 4
出力例 2
6
7, 4 の平均値は 5.5 であり、小数点以下を切り上げて得られる整数は 6 です。
入力例 3
5 5
出力例 3
5
Score : 100 points
Problem Statement
You are given two positive integers a and b. Let x be the average of a and b. Print x rounded up to the nearest integer.
Constraints
- a and b are integers.
- 1 \leq a, b \leq 100
Input
Input is given from Standard Input in the following format:
a b
Output
Print x rounded up to the nearest integer.
Sample Input 1
1 3
Sample Output 1
2
The average of 1 and 3 is 2.0, and it will be rounded up to the nearest integer, 2.
Sample Input 2
7 4
Sample Output 2
6
The average of 7 and 4 is 5.5, and it will be rounded up to the nearest integer, 6.
Sample Input 3
5 5
Sample Output 3
5
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 200 点
問題文
英小文字のみからなる文字列 s, t が与えられます。 あなたは、s の文字を好きな順に並べ替え、文字列 s' を作ります。 また、t の文字を好きな順に並べ替え、文字列 t' を作ります。 このとき、辞書順で s' < t' となるようにできるか判定してください。
注釈
長さ N の文字列 a = a_1 a_2 ... a_N および長さ M の文字列 b = b_1 b_2 ... b_M について、辞書順で a < b であるとは、次の 2 つの条件のいずれかが成り立つことをいう;
- N < M かつ a_1 = b_1, a_2 = b_2, ..., a_N = b_N である。
- ある i (1 \leq i \leq N, M) が存在して、a_1 = b_1, a_2 = b_2, ..., a_{i - 1} = b_{i - 1} かつ a_i < b_i である。 ただし、文字どうしはアルファベット順で比較される。
例えば、xy < xya であり、atcoder < atlas である。
制約
- s, t の長さは 1 以上 100 以下である。
- s, t は英小文字のみからなる。
入力
入力は以下の形式で標準入力から与えられる。
s t
出力
辞書順で s' < t' となるようにできるならば Yes を、できないならば No を出力せよ。
入力例 1
yx axy
出力例 1
Yes
例えば、yx を xy と並べ替え、axy を yxa と並べ替えれば、xy < yxa となります。
入力例 2
ratcode atlas
出力例 2
Yes
例えば、ratcode を acdeort と並べ替え、atlas を tslaa と並べ替えれば、acdeort < tslaa となります。
入力例 3
cd abc
出力例 3
No
cd, abc をそれぞれどのように並べ替えても、目標を達成できません。
入力例 4
w ww
出力例 4
Yes
入力例 5
zzz zzz
出力例 5
No
Score : 200 points
Problem Statement
You are given strings s and t, consisting of lowercase English letters. You will create a string s' by freely rearranging the characters in s. You will also create a string t' by freely rearranging the characters in t. Determine whether it is possible to satisfy s' < t' for the lexicographic order.
Notes
For a string a = a_1 a_2 ... a_N of length N and a string b = b_1 b_2 ... b_M of length M, we say a < b for the lexicographic order if either one of the following two conditions holds true:
- N < M and a_1 = b_1, a_2 = b_2, ..., a_N = b_N.
- There exists i (1 \leq i \leq N, M) such that a_1 = b_1, a_2 = b_2, ..., a_{i - 1} = b_{i - 1} and a_i < b_i. Here, letters are compared using alphabetical order.
For example, xy < xya and atcoder < atlas.
Constraints
- The lengths of s and t are between 1 and 100 (inclusive).
- s and t consists of lowercase English letters.
Input
Input is given from Standard Input in the following format:
s t
Output
If it is possible to satisfy s' < t', print Yes; if it is not, print No.
Sample Input 1
yx axy
Sample Output 1
Yes
We can, for example, rearrange yx into xy and axy into yxa. Then, xy < yxa.
Sample Input 2
ratcode atlas
Sample Output 2
Yes
We can, for example, rearrange ratcode into acdeort and atlas into tslaa. Then, acdeort < tslaa.
Sample Input 3
cd abc
Sample Output 3
No
No matter how we rearrange cd and abc, we cannot achieve our objective.
Sample Input 4
w ww
Sample Output 4
Yes
Sample Input 5
zzz zzz
Sample Output 5
No
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 300 点
問題文
長さ N の正整数の列 a = (a_1, a_2, ..., a_N) が与えられます。 あなたの目標は、a のうちいくつかの要素を取り除き、a を 良い数列 にすることです。
ここで、数列 b が 良い数列 であるとは、次の条件が成り立つことです。
- b の各要素 x について、b に値 x はちょうど x 個含まれる。
例えば、(3, 3, 3), (4, 2, 4, 1, 4, 2, 4), () (空の数列) は良い数列です。 一方、(3, 3, 3, 3), (2, 4, 1, 4, 2) は良い数列ではありません。
a を良い数列にするために取り除くべき要素の個数の最小値を求めてください。
制約
- 1 \leq N \leq 10^5
- a_i は整数である。
- 1 \leq a_i \leq 10^9
入力
入力は以下の形式で標準入力から与えられる。
N a_1 a_2 ... a_N
出力
a を良い数列にするために取り除くべき要素の個数の最小値を出力せよ。
入力例 1
4 3 3 3 3
出力例 1
1
例えば、要素 3 を 1 個取り除くと、(3, 3, 3) は良い数列になります。
入力例 2
5 2 4 1 4 2
出力例 2
2
例えば、要素 4 を 2 個取り除くと、(2, 1, 2) は良い数列になります。
入力例 3
6 1 2 2 3 3 3
出力例 3
0
入力例 4
1 1000000000
出力例 4
1
要素 10^9 を 1 個取り除くと、() は良い数列になります。
入力例 5
8 2 7 1 8 2 8 1 8
出力例 5
5
Score : 300 points
Problem Statement
You are given a sequence of positive integers of length N, a = (a_1, a_2, ..., a_N). Your objective is to remove some of the elements in a so that a will be a good sequence.
Here, an sequence b is a good sequence when the following condition holds true:
- For each element x in b, the value x occurs exactly x times in b.
For example, (3, 3, 3), (4, 2, 4, 1, 4, 2, 4) and () (an empty sequence) are good sequences, while (3, 3, 3, 3) and (2, 4, 1, 4, 2) are not.
Find the minimum number of elements that needs to be removed so that a will be a good sequence.
Constraints
- 1 \leq N \leq 10^5
- a_i is an integer.
- 1 \leq a_i \leq 10^9
Input
Input is given from Standard Input in the following format:
N a_1 a_2 ... a_N
Output
Print the minimum number of elements that needs to be removed so that a will be a good sequence.
Sample Input 1
4 3 3 3 3
Sample Output 1
1
We can, for example, remove one occurrence of 3. Then, (3, 3, 3) is a good sequence.
Sample Input 2
5 2 4 1 4 2
Sample Output 2
2
We can, for example, remove two occurrences of 4. Then, (2, 1, 2) is a good sequence.
Sample Input 3
6 1 2 2 3 3 3
Sample Output 3
0
Sample Input 4
1 1000000000
Sample Output 4
1
Remove one occurrence of 10^9. Then, () is a good sequence.
Sample Input 5
8 2 7 1 8 2 8 1 8
Sample Output 5
5
Time Limit: 2 sec / Memory Limit: 512 MB
配点 : 500 点
問題文
二次元平面の原点にロボットが置かれています。 最初、ロボットは x 軸の正の向きを向いています。
このロボットに命令列 s が与えられます。 s は次の 2 文字のみからなり、先頭から末尾まで順に実行されます。
F: 今向いている向きに長さ 1 だけ移動する。T: 時計回りまたは反時計回りの好きな方向に 90 度だけ向きを変える。
ロボットの目標は、命令列をすべて実行し終わった後に座標 (x, y) にいることです。 この目標が達成可能か判定してください。
制約
- s は
F,Tのみからなる。 - 1 \leq |s| \leq 8\ 000
- x, y は整数である。
- |x|, |y| \leq |s|
入力
入力は以下の形式で標準入力から与えられる。
s x y
出力
目標が達成可能ならば Yes を出力し、達成不可能ならば No を出力せよ。
入力例 1
FTFFTFFF 4 2
出力例 1
Yes
1 番目の T で反時計周りに 90 度だけ向きを変え、2 番目の T で時計周りに 90 度だけ向きを変えればよいです。
入力例 2
FTFFTFFF -2 -2
出力例 2
Yes
1 番目の T で時計周りに 90 度だけ向きを変え、2 番目の T で時計周りに 90 度だけ向きを変えればよいです。
入力例 3
FF 1 0
出力例 3
No
入力例 4
TF 1 0
出力例 4
No
入力例 5
FFTTFF 0 0
出力例 5
Yes
例えば、1 番目の T で反時計周りに 90 度だけ向きを変え、2 番目の T で反時計周りに 90 度だけ向きを変えればよいです。
入力例 6
TTTT 1 0
出力例 6
No
Score : 500 points
Problem Statement
A robot is put at the origin in a two-dimensional plane. Initially, the robot is facing in the positive x-axis direction.
This robot will be given an instruction sequence s. s consists of the following two kinds of letters, and will be executed in order from front to back.
F: Move in the current direction by distance 1.T: Turn 90 degrees, either clockwise or counterclockwise.
The objective of the robot is to be at coordinates (x, y) after all the instructions are executed. Determine whether this objective is achievable.
Constraints
- s consists of
FandT. - 1 \leq |s| \leq 8 000
- x and y are integers.
- |x|, |y| \leq |s|
Input
Input is given from Standard Input in the following format:
s x y
Output
If the objective is achievable, print Yes; if it is not, print No.
Sample Input 1
FTFFTFFF 4 2
Sample Output 1
Yes
The objective can be achieved by, for example, turning counterclockwise in the first T and turning clockwise in the second T.
Sample Input 2
FTFFTFFF -2 -2
Sample Output 2
Yes
The objective can be achieved by, for example, turning clockwise in the first T and turning clockwise in the second T.
Sample Input 3
FF 1 0
Sample Output 3
No
Sample Input 4
TF 1 0
Sample Output 4
No
Sample Input 5
FFTTFF 0 0
Sample Output 5
Yes
The objective can be achieved by, for example, turning counterclockwise in the first T and turning counterclockwise in the second T.
Sample Input 6
TTTT 1 0
Sample Output 6
No