Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
英小文字からなる文字列 S, T が与えられます。S の長さは N、T の長さは M です。(N \leq M が制約で保証されています)
S が T の 接頭辞 であるとは、T のはじめ N 文字からなる文字列が S と一致することを言います。
S が T の 接尾辞 であるとは、T の後ろ N 文字からなる文字列が S と一致することを言います。
S が T の接頭辞であり、かつ接尾辞でもある場合は 0 を、
S が T の接頭辞であるが、接尾辞でない場合は 1 を、
S が T の接尾辞であるが、接頭辞でない場合は 2 を、
S が T の接頭辞でも接尾辞でもない場合は 3 を出力してください。
制約
- 1 \leq N \leq M \leq 100
- S は英小文字からなる長さ N の文字列
- T は英小文字からなる長さ M の文字列
入力
入力は以下の形式で標準入力から与えられる。
N M S T
出力
問題文の指示に従って答えを出力せよ。
入力例 1
3 7 abc abcdefg
出力例 1
1
S は T の接頭辞ですが接尾辞ではありません。よって 1 を出力します。
入力例 2
3 4 abc aabc
出力例 2
2
S は T の接尾辞ですが接頭辞ではありません。
入力例 3
3 3 abc xyz
出力例 3
3
S は T の接頭辞でも接尾辞でもありません。
入力例 4
3 3 aaa aaa
出力例 4
0
S と T が完全に一致する場合もあります。この場合、S は T の接頭辞であり、かつ接尾辞でもあります。
Score : 200 points
Problem Statement
You are given two strings S and T consisting of lowercase English letters. The lengths of S and T are N and M, respectively. (The constraints guarantee that N \leq M.)
S is said to be a prefix of T when the first N characters of T coincide S.
S is said to be a suffix of T when the last N characters of T coincide S.
If S is both a prefix and a suffix of T, print 0;
If S is a prefix of T but not a suffix, print 1;
If S is a suffix of T but not a prefix, print 2;
If S is neither a prefix nor a suffix of T, print 3.
Constraints
- 1 \leq N \leq M \leq 100
- S is a string of length N consisting of lowercase English letters.
- T is a string of length M consisting of lowercase English letters.
Input
The input is given from Standard Input in the following format:
N M S T
Output
Print the answer according to the instructions in the problem statement.
Sample Input 1
3 7 abc abcdefg
Sample Output 1
1
S is a prefix of T but not a suffix, so you should print 1.
Sample Input 2
3 4 abc aabc
Sample Output 2
2
S is a suffix of T but not a prefix.
Sample Input 3
3 3 abc xyz
Sample Output 3
3
S is neither a prefix nor a suffix of T.
Sample Input 4
3 3 aaa aaa
Sample Output 4
0
S and T may coincide, in which case S is both a prefix and a suffix of T.
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
整数 B が与えられます。
A^A = B であるような正の整数 A が存在するならばその値を、存在しないならば -1 を出力してください。
制約
- 1 \leq B \leq 10^{18}
- B は整数
入力
入力は以下の形式で標準入力から与えられる。
B
出力
A^A = B であるような正の整数 A が存在するならばその値を、存在しないならば -1 を出力せよ。
A^A = B を満たす正の整数 A が複数ある場合は、どれを出力しても正解とみなされる。
入力例 1
27
出力例 1
3
3^3 = 27 なので 3 を出力します。
入力例 2
100
出力例 2
-1
A^A = B を満たす A は存在しません。
入力例 3
10000000000
出力例 3
10
Score : 200 points
Problem Statement
You are given an integer B.
If there exists a positive integer A such that A^A = B, print its value; otherwise, output -1.
Constraints
- 1 \leq B \leq 10^{18}
- B is an integer.
Input
The input is given from Standard Input in the following format:
B
Output
If there exists a positive integer A such that A^A = B, print its value; otherwise, print -1.
If there are multiple positive integers A such that A^A = B, any of them will be accepted.
Sample Input 1
27
Sample Output 1
3
3^3 = 27, so print 3.
Sample Input 2
100
Sample Output 2
-1
There is no A such that A^A = B.
Sample Input 3
10000000000
Sample Output 3
10
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
# と . からなる H 行 W 列の図形 S,T が与えられます。
図形 S は H 個の文字列として与えられ、 S_i の j 文字目は S の i 行 j 列にある要素を表します。 T についても同様です。
S の列を並べ替えて T と等しくできるか判定してください。
但し、図形 X の列を並べ替えるとは、以下の操作を言います。
- (1,2,\dots,W) の順列 P=(P_1,P_2,\dots,P_W) をひとつ選択する。
- その後、全ての 1 \le i \le H を満たす整数 i について、以下の操作を同時に行う。
- 1 \le j \le W を満たす全ての整数 j について同時に、 X の i 行 j 列にある要素を i 行 P_j 列にある要素に置き換える。
制約
- H,W は整数
- 1 \le H,W
- 1 \le H \times W \le 4 \times 10^5
- S_i,T_i は
#と.からなる長さ W の文字列
入力
入力は以下の形式で標準入力から与えられる。
H W S_1 S_2 \vdots S_H T_1 T_2 \vdots T_H
出力
S を T と等しくできるなら Yes 、 そうでないなら No と出力せよ。
入力例 1
3 4 ##.# ##.. #... .### ..## ...#
出力例 1
Yes
例えば S の 3,4,2,1 列目をこの順に左から並べ替えた場合、 S を T と等しくできます。
入力例 2
3 3 #.# .#. #.# ##. ##. .#.
出力例 2
No
この入力では、 S を T と等しくすることができません。
入力例 3
2 1 # . # .
出力例 3
Yes
S=T である場合もあります。
入力例 4
8 7 #..#..# .##.##. #..#..# .##.##. #..#..# .##.##. #..#..# .##.##. ....### ####... ....### ####... ....### ####... ....### ####...
出力例 4
Yes
Score : 300 points
Problem Statement
You are given patterns S and T consisting of # and ., each with H rows and W columns.
The pattern S is given as H strings, and the j-th character of S_i represents the element at the i-th row and j-th column. The same goes for T.
Determine whether S can be made equal to T by rearranging the columns of S.
Here, rearranging the columns of a pattern X is done as follows.
- Choose a permutation P=(P_1,P_2,\dots,P_W) of (1,2,\dots,W).
- Then, for every integer i such that 1 \le i \le H, simultaneously do the following.
- For every integer j such that 1 \le j \le W, simultaneously replace the element at the i-th row and j-th column of X with the element at the i-th row and P_j-th column.
Constraints
- H and W are integers.
- 1 \le H,W
- 1 \le H \times W \le 4 \times 10^5
- S_i and T_i are strings of length W consisting of
#and..
Input
The input is given from Standard Input in the following format:
H W S_1 S_2 \vdots S_H T_1 T_2 \vdots T_H
Output
If S can be made equal to T, print Yes; otherwise, print No.
Sample Input 1
3 4 ##.# ##.. #... .### ..## ...#
Sample Output 1
Yes
If you, for instance, arrange the 3-rd, 4-th, 2-nd, and 1-st columns of S in this order from left to right, S will be equal to T.
Sample Input 2
3 3 #.# .#. #.# ##. ##. .#.
Sample Output 2
No
In this input, S cannot be made equal to T.
Sample Input 3
2 1 # . # .
Sample Output 3
Yes
It is possible that S=T.
Sample Input 4
8 7 #..#..# .##.##. #..#..# .##.##. #..#..# .##.##. #..#..# .##.##. ....### ####... ....### ####... ....### ####... ....### ####...
Sample Output 4
Yes
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
高橋くんは数直線上に N 個のプレゼントを置きました。そのうち i 個目のプレゼントは座標 A_i に置かれました。
あなたは数直線上の長さ M の半開区間 [x,x+M) を選び、そこに含まれるプレゼントを全て獲得します。
より詳しくは、以下の手順でプレゼントを獲得します。
- まず、実数 x をひとつ選択する。
- その後、プレゼントのうち置かれている座標が x \le A_i < x+M を満たすものを全て獲得する。
最大でいくつのプレゼントを獲得することができますか?
制約
- 入力は全て整数
- 1 \le N \le 3 \times 10^5
- 1 \le M \le 10^9
- 0 \le A_i \le 10^9
入力
入力は以下の形式で標準入力から与えられる。
N M A_1 A_2 \dots A_N
出力
答えを整数として出力せよ。
入力例 1
8 6 2 3 5 7 11 13 17 19
出力例 1
4
例えば、半開区間 [1.5,7.5) を指定します。
このとき、座標 2,3,5,7 にある 4 つのプレゼントを全て獲得することができ、これが獲得可能な最大の個数です。
入力例 2
10 1 3 1 4 1 5 9 2 6 5 3
出力例 2
2
同一の座標に複数のプレゼントが置いてあることもあります。
入力例 3
10 998244353 100000007 0 1755647 998244353 495 1000000000 1755648 503 1755649 998244853
出力例 3
7
Score : 300 points
Problem Statement
Takahashi has placed N gifts on a number line. The i-th gift is placed at coordinate A_i.
You will choose a half-open interval [x,x+M) of length M on the number line and acquire all the gifts included in it.
More specifically, you acquire gifts according to the following procedure.
- First, choose one real number x.
- Then, acquire all the gifts whose coordinates satisfy x \le A_i < x+M.
What is the maximum number of gifts you can acquire?
Constraints
- All input values are integers.
- 1 \le N \le 3 \times 10^5
- 1 \le M \le 10^9
- 0 \le A_i \le 10^9
Input
The input is given from Standard Input in the following format:
N M A_1 A_2 \dots A_N
Output
Print the answer as an integer.
Sample Input 1
8 6 2 3 5 7 11 13 17 19
Sample Output 1
4
For example, specify the half-open interval [1.5,7.5).
In this case, you can acquire the four gifts at coordinates 2,3,5,7, the maximum number of gifts that can be acquired.
Sample Input 2
10 1 3 1 4 1 5 9 2 6 5 3
Sample Output 2
2
There may be multiple gifts at the same coordinate.
Sample Input 3
10 998244353 100000007 0 1755647 998244353 495 1000000000 1755648 503 1755649 998244853
Sample Output 3
7
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 400 点
問題文
長さ N の数列 A=(A_0,\ldots,A_{N-1}) があります。
次の条件を全て満たす整数の組 (x,y,z,w) が存在するか判定してください。
- 0 \leq x < y < z < w \leq N
- A_x + A_{x+1} + \ldots + A_{y-1} = P
- A_y + A_{y+1} + \ldots + A_{z-1} = Q
- A_z + A_{z+1} + \ldots + A_{w-1} = R
制約
- 3 \leq N \leq 2\times 10^5
- 1 \leq A_i \leq 10^9
- 1 \leq P,Q,R \leq 10^{15}
- 入力に含まれる値は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
N P Q R
A_0 A_1 \ldots A_{N-1}
出力
条件を満たす組が存在するなら Yes、存在しないなら No を出力せよ。
入力例 1
10 5 7 5 1 3 2 2 2 3 1 4 3 2
出力例 1
Yes
(x,y,z,w)=(1,3,6,8) が条件を満たします。
入力例 2
9 100 101 100 31 41 59 26 53 58 97 93 23
出力例 2
No
入力例 3
7 1 1 1 1 1 1 1 1 1 1
出力例 3
Yes
Score : 400 points
Problem Statement
There is a sequence A=(A_0,\ldots,A_{N-1}) of length N.
Determine if there exists a tuple of integers (x,y,z,w) that satisfies all of the following conditions:
- 0 \leq x < y < z < w \leq N
- A_x + A_{x+1} + \ldots + A_{y-1} = P
- A_y + A_{y+1} + \ldots + A_{z-1} = Q
- A_z + A_{z+1} + \ldots + A_{w-1} = R
Constraints
- 3 \leq N \leq 2\times 10^5
- 1 \leq A_i \leq 10^9
- 1 \leq P,Q,R \leq 10^{15}
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N P Q R
A_0 A_1 \ldots A_{N-1}
Output
If there exists a tuple that satisfies the conditions, print Yes; otherwise, print No.
Sample Input 1
10 5 7 5 1 3 2 2 2 3 1 4 3 2
Sample Output 1
Yes
(x,y,z,w)=(1,3,6,8) satisfies the conditions.
Sample Input 2
9 100 101 100 31 41 59 26 53 58 97 93 23
Sample Output 2
No
Sample Input 3
7 1 1 1 1 1 1 1 1 1 1
Sample Output 3
Yes