Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 100 点
問題文
相違なる整数 A, B があります。
|A - K| = |B - K| となるような整数 K を出力してください。
そのような整数が存在しなければ、代わりに IMPOSSIBLE を出力してください。
制約
- 入力は全て整数である。
- 0 \leq A,\ B \leq 10^9
- A と B は相違なる。
入力
入力は以下の形式で標準入力から与えられる。
A B
出力
条件を満たす整数 K を出力せよ。
そのような整数が存在しなければ、代わりに IMPOSSIBLE を出力せよ。
入力例 1
2 16
出力例 1
9
|2 - 9| = 7, |16 - 9| = 7 であるため、9 は条件を満たす整数です。
入力例 2
0 3
出力例 2
IMPOSSIBLE
条件を満たす整数は存在しません。
入力例 3
998244353 99824435
出力例 3
549034394
Score: 100 points
Problem Statement
We have two distinct integers A and B.
Print the integer K such that |A - K| = |B - K|.
If such an integer does not exist, print IMPOSSIBLE instead.
Constraints
- All values in input are integers.
- 0 \leq A,\ B \leq 10^9
- A and B are distinct.
Input
Input is given from Standard Input in the following format:
A B
Output
Print the integer K satisfying the condition.
If such an integer does not exist, print IMPOSSIBLE instead.
Sample Input 1
2 16
Sample Output 1
9
|2 - 9| = 7 and |16 - 9| = 7, so 9 satisfies the condition.
Sample Input 2
0 3
Sample Output 2
IMPOSSIBLE
No integer satisfies the condition.
Sample Input 3
998244353 99824435
Sample Output 3
549034394
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 200 点
問題文
{1,\ 2,\ ...,\ N} を並び替えた数列 p = {p_1,\ p_2,\ ...,\ p_N} があります。
あなたは一度だけ、整数 \ i,\ j \ (1 \leq i < j \leq N) を選んで \ p_i\ と \ p_j\ を入れ替える操作を行うことができます。操作を行わないことも可能です。
p を昇順にすることができるなら YES を、できないならば NO を出力してください。
制約
- 入力は全て整数である。
- 2 \leq N \leq 50
- p は {1,\ 2,\ ...,\ N} を並び替えた数列である。
入力
入力は以下の形式で標準入力から与えられる。
N p_1 p_2 ... p_N
出力
p を昇順にすることができるなら YES を、できないならば NO を出力せよ。
入力例 1
5 5 2 3 4 1
出力例 1
YES
p_1 と p_5 を入れ替えることで p を昇順にできます。
入力例 2
5 2 4 3 5 1
出力例 2
NO
この場合、どのような操作を行っても p を昇順にすることはできません。
入力例 3
7 1 2 3 4 5 6 7
出力例 3
YES
p が最初から昇順なので、操作を行う必要はありません。
Score : 200 points
Problem Statement
We have a sequence p = {p_1,\ p_2,\ ...,\ p_N} which is a permutation of {1,\ 2,\ ...,\ N}.
You can perform the following operation at most once: choose integers i and j (1 \leq i < j \leq N), and swap p_i and p_j. Note that you can also choose not to perform it.
Print YES if you can sort p in ascending order in this way, and NO otherwise.
Constraints
- All values in input are integers.
- 2 \leq N \leq 50
- p is a permutation of {1,\ 2,\ ...,\ N}.
Input
Input is given from Standard Input in the following format:
N p_1 p_2 ... p_N
Output
Print YES if you can sort p in ascending order in the way stated in the problem statement, and NO otherwise.
Sample Input 1
5 5 2 3 4 1
Sample Output 1
YES
You can sort p in ascending order by swapping p_1 and p_5.
Sample Input 2
5 2 4 3 5 1
Sample Output 2
NO
In this case, swapping any two elements does not sort p in ascending order.
Sample Input 3
7 1 2 3 4 5 6 7
Sample Output 3
YES
p is already sorted in ascending order, so no operation is needed.
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
N+1 個の街があり、i 番目の街は A_i 体のモンスターに襲われています。
N 人の勇者が居て、i 番目の勇者は i 番目または i+1 番目の街を襲っているモンスターを合計で B_i 体まで倒すことができます。
N 人の勇者がうまく協力することで、合計して最大で何体のモンスターを倒せるでしょうか。
制約
- 入力は全て整数である。
- 1 \leq N \leq 10^5
- 1 \leq A_i \leq 10^9
- 1 \leq B_i \leq 10^9
入力
入力は以下の形式で標準入力から与えられる。
N
A_1 A_2 ... A_{N+1}
B_1 B_2 ... B_N
出力
合計して倒せるモンスターの数の最大値を出力せよ。
入力例 1
2 3 5 2 4 5
出力例 1
9
以下のようにモンスターを倒すと、合計 9 体のモンスターを倒すことができ、このときが最大です。
- 1 番目の勇者が 1 番目の街を襲っているモンスターを 2 体、2 番目の街を襲っているモンスターを 2 体倒します。
- 2 番目の勇者が 2 番目の街を襲っているモンスターを 3 体、3 番目の街を襲っているモンスターを 2 体倒します。
入力例 2
3 5 6 3 8 5 100 8
出力例 2
22
入力例 3
2 100 1 1 1 100
出力例 3
3
Score : 300 points
Problem Statement
There are N+1 towns. The i-th town is being attacked by A_i monsters.
We have N heroes. The i-th hero can defeat monsters attacking the i-th or (i+1)-th town, for a total of at most B_i monsters.
What is the maximum total number of monsters the heroes can cooperate to defeat?
Constraints
- All values in input are integers.
- 1 \leq N \leq 10^5
- 1 \leq A_i \leq 10^9
- 1 \leq B_i \leq 10^9
Input
Input is given from Standard Input in the following format:
N
A_1 A_2 ... A_{N+1}
B_1 B_2 ... B_N
Output
Print the maximum total number of monsters the heroes can defeat.
Sample Input 1
2 3 5 2 4 5
Sample Output 1
9
If the heroes choose the monsters to defeat as follows, they can defeat nine monsters in total, which is the maximum result.
- The first hero defeats two monsters attacking the first town and two monsters attacking the second town.
- The second hero defeats three monsters attacking the second town and two monsters attacking the third town.
Sample Input 2
3 5 6 3 8 5 100 8
Sample Output 2
22
Sample Input 3
2 100 1 1 1 100
Sample Output 3
3
Time Limit: 2 sec / Memory Limit: 1024 MB
配点: 400 点
問題文
文字列 S が与えられます。S の各文字は、数字 (0 ～ 9) か ? です。
? を数字に置き換えてできる整数のうち、13 で割って 5 あまる数は何通りあるでしょうか？ただし、頭文字が 0 である場合も整数とみなすものとします。
答えは非常に大きくなる可能性があるため、10^9+7 で割ったあまりを答えてください。
制約
- S は数字 (
0～9) と?からなる文字列。 - 1 \leq |S| \leq 10^5
入力
入力は以下の形式で標準入力から与えられます。
S
出力
条件を満たす整数の個数を 10^9+7 で割ったあまりを出力してください。
入力例 1
??2??5
出力例 1
768
たとえば 482305, 002865, 972665 などが条件を満たします。
入力例 2
?44
出力例 2
1
044 のみが条件を満たします。
入力例 3
7?4
出力例 3
0
条件を満たす整数を作ることが不可能な場合もあります。
入力例 4
?6?42???8??2??06243????9??3???7258??5??7???????774????4?1??17???9?5?70???76???
出力例 4
153716888
Score : 400 points
Problem Statement
Given is a string S. Each character in S is either a digit (0, ..., 9) or ?.
Among the integers obtained by replacing each occurrence of ? with a digit, how many have a remainder of 5 when divided by 13? An integer may begin with 0.
Since the answer can be enormous, print the count modulo 10^9+7.
Constraints
- S is a string consisting of digits (
0, ...,9) and?. - 1 \leq |S| \leq 10^5
Input
Input is given from Standard Input in the following format:
S
Output
Print the number of integers satisfying the condition, modulo 10^9+7.
Sample Input 1
??2??5
Sample Output 1
768
For example, 482305, 002865, and 972665 satisfy the condition.
Sample Input 2
?44
Sample Output 2
1
Only 044 satisfies the condition.
Sample Input 3
7?4
Sample Output 3
0
We may not be able to produce an integer satisfying the condition.
Sample Input 4
?6?42???8??2??06243????9??3???7258??5??7???????774????4?1??17???9?5?70???76???
Sample Output 4
153716888
Time Limit: 2 sec / Memory Limit: 1024 MB
配点: 500 点
問題文
無限に広がる二次元格子があります。ジャンボ高橋君はこの上でゴルフをすることにしました。
ボールははじめ原点 (0, 0) にあり、ゴールは格子点(座標がいずれも整数である点) (X, Y) です。ジャンボ高橋君は 1 打ごとに、次の操作を行えます。
- その時点でボールがある点とのマンハッタン距離が K であるような格子点を 1 つ選び、その点にボールを飛ばす。
ゴールと同じ座標にボールが来た時点でクリアとなり、それまでの打数がスコアとなります。ジャンボ高橋君はできるだけ少ないスコアでクリアしたいと思っています。
クリアが可能かどうか判定し、可能ならばスコアが最小となるボールの動かし方を 1 つ求めてください。
2 つの座標 (x_1, y_1), (x_2, y_2) に対するマンハッタン距離は、|x_1-x_2|+|y_1-y_2| と定義されます。マンハッタン距離の説明
制約
- 入力はすべて整数
- 1 \leq K \leq 10^9
- -10^5 \leq X, Y \leq 10^5
- (X, Y) \neq (0, 0)
入力
入力は以下の形式で標準入力から与えられます。
K X Y
出力
クリアが不可能な場合は -1 と出力してください。
クリアが可能な場合、スコアが最小となるボールの動かし方を次のように出力してください。
s x_1 y_1 x_2 y_2 . . . x_s y_s
ここで、s はスコアの最小値です。また、(x_i, y_i) を i 打目にボールを飛ばす先の座標とします。
入力例 1
11 -1 2
出力例 1
3 7 4 2 10 -1 2
- (0, 0), (7, 4) のマンハッタン距離は |0-7|+|0-4|=11。
- (7, 4), (2, 10) のマンハッタン距離は |7-2|+|4-10|=11。
- (2, 10), (-1, 2) のマンハッタン距離は |2-(-1)|+|10-2|=11。
以上より、このボールの動かし方は正しいです。
また、3 打より少なくクリアする方法は存在しません。
入力例 2
4600 52 149
出力例 2
-1
入力例 3
4 9 9
出力例 3
5 1 3 4 2 4 6 6 8 9 9
Score : 500 points
Problem Statement
Jumbo Takahashi will play golf on an infinite two-dimensional grid.
The ball is initially at the origin (0, 0), and the goal is a grid point (a point with integer coordinates) (X, Y). In one stroke, Jumbo Takahashi can perform the following operation:
- Choose a grid point whose Manhattan distance from the current position of the ball is K, and send the ball to that point.
The game is finished when the ball reaches the goal, and the score will be the number of strokes so far. Jumbo Takahashi wants to finish the game with the lowest score possible.
Determine if the game can be finished. If the answer is yes, find one way to bring the ball to the goal with the lowest score possible.
The Manhattan distance between two points (x_1, y_1) and (x_2, y_2) is defined as |x_1-x_2|+|y_1-y_2|.What is Manhattan distance?
Constraints
- All values in input are integers.
- 1 \leq K \leq 10^9
- -10^5 \leq X, Y \leq 10^5
- (X, Y) \neq (0, 0)
Input
Input is given from Standard Input in the following format:
K X Y
Output
If the game cannot be finished, print -1.
If the game can be finished, print one way to bring the ball to the destination with the lowest score possible, in the following format:
s x_1 y_1 x_2 y_2 . . . x_s y_s
Here, s is the lowest score possible, and (x_i, y_i) is the position of the ball just after the i-th stroke.
Sample Input 1
11 -1 2
Sample Output 1
3 7 4 2 10 -1 2
- The Manhattan distance between (0, 0) and (7, 4) is |0-7|+|0-4|=11.
- The Manhattan distance between (7, 4) and (2, 10) is |7-2|+|4-10|=11.
- The Manhattan distance between (2, 10) and (-1, 2) is |2-(-1)|+|10-2|=11.
Thus, this play is valid.
Also, there is no way to finish the game with less than three strokes.
Sample Input 2
4600 52 149
Sample Output 2
-1
Sample Input 3
4 9 9
Sample Output 3
5 1 3 4 2 4 6 6 8 9 9
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
英小文字からなる二つの文字列 s, t が与えられます。次の条件を満たす非負整数 i の個数が有限であるか判定し、有限である場合はそのような i の最大値を求めてください。
- ある非負整数 j が存在し、t を i 個連結して得られる文字列は、s を j 個連結して得られる文字列の部分文字列である。
注記
-
文字列 a が文字列 b の部分文字列であるとは、ある整数 x (0 \leq x \leq |b| - |a|) が存在して任意の整数 y (1 \leq y \leq |a|) に対して a_y = b_{x+y} であることです。
-
任意の文字列に対し、それを 0 個連結して得られる文字列は空文字列であるとします。また、上記の定義より、空文字列は任意の文字列の部分文字列です。したがって、任意の二つの文字列 s, t に対して i = 0 は問題文中の条件を満たします。
制約
- 1 \leq |s| \leq 5 \times 10^5
- 1 \leq |t| \leq 5 \times 10^5
- s, t は英小文字からなる。
入力
入力は以下の形式で標準入力から与えられる。
s t
出力
条件を満たす非負整数 i の個数が有限である場合はそのような i の最大値を、無限である場合は -1 を出力せよ。
入力例 1
abcabab ab
出力例 1
3
t を 3 個連結して得られる文字列 ababab は、s を 2 個連結して得られる文字列 abcabababcabab の部分文字列であるため、i = 3 は条件を満たします。
一方で、t を 4 個連結して得られる文字列 abababab は、s を何個連結しても部分文字列として現れないため、i = 4 は条件を満たしません。
同様に、5 以上の任意の整数も条件を満たしません。よって条件を満たす非負整数 i の個数は有限で、その最大値は 3 です。
入力例 2
aa aaaaaaa
出力例 2
-1
任意の非負整数 i に対し、t を i 個連結して得られる文字列は、s を 4i 個連結して得られる文字列の部分文字列です。したがって条件を満たす非負整数 i は無限に存在します。
入力例 3
aba baaab
出力例 3
0
注記で述べたように、i = 0 は必ず条件を満たします。
Score : 600 points
Problem Statement
Given are two strings s and t consisting of lowercase English letters. Determine if the number of non-negative integers i satisfying the following condition is finite, and find the maximum value of such i if the number is finite.
- There exists a non-negative integer j such that the concatenation of i copies of t is a substring of the concatenation of j copies of s.
Notes
-
A string a is a substring of another string b if and only if there exists an integer x (0 \leq x \leq |b| - |a|) such that, for any y (1 \leq y \leq |a|), a_y = b_{x+y} holds.
-
We assume that the concatenation of zero copies of any string is the empty string. From the definition above, the empty string is a substring of any string. Thus, for any two strings s and t, i = 0 satisfies the condition in the problem statement.
Constraints
- 1 \leq |s| \leq 5 \times 10^5
- 1 \leq |t| \leq 5 \times 10^5
- s and t consist of lowercase English letters.
Input
Input is given from Standard Input in the following format:
s t
Output
If the number of non-negative integers i satisfying the following condition is finite, print the maximum value of such i; if the number is infinite, print -1.
Sample Input 1
abcabab ab
Sample Output 1
3
The concatenation of three copies of t, ababab, is a substring of the concatenation of two copies of s, abcabababcabab, so i = 3 satisfies the condition.
On the other hand, the concatenation of four copies of t, abababab, is not a substring of the concatenation of any number of copies of s, so i = 4 does not satisfy the condition.
Similarly, any integer greater than 4 does not satisfy the condition, either. Thus, the number of non-negative integers i satisfying the condition is finite, and the maximum value of such i is 3.
Sample Input 2
aa aaaaaaa
Sample Output 2
-1
For any non-negative integer i, the concatenation of i copies of t is a substring of the concatenation of 4i copies of s. Thus, there are infinitely many non-negative integers i that satisfy the condition.
Sample Input 3
aba baaab
Sample Output 3
0
As stated in Notes, i = 0 always satisfies the condition.