Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 100 点
問題文
あなたはアイドルグループ Bit♡Beat のプロデューサーです。
Bit♡Beat の事務所に N 個のファンレターが届きました。 i 個目のファンレターは A_i 月 B_i 日に届いたものです。
これら N 個のファンレターの日付を早い順（1 月 1 日から始めて、先に訪れる順）に出力してください。
制約
- 1\le N\le 365
- A_i 月 B_i 日は平年（うるう年ではない年）において正しい日付である。
- (A_i , B_i) \neq (A_j , B_j) (i \neq j)
- 入力される値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N A_1 B_1 A_2 B_2 \vdots A_N B_N
出力
N 行出力せよ。
i 行目 (1\le i\le N) には、届いた日付が i 番目に早いファンレターの日付の月と日を半角スペース区切りで出力せよ。
入力例 1
3 3 15 1 15 3 8
出力例 1
1 15 3 8 3 15
事務所には 3 月 15 日、 1 月 15 日、 3 月 8 日にファンレターが届きました。
これらの日付を早い順に並べると 1 月 15 日、 3 月 8 日、 3 月 15 日となります。したがって、上記のように出力してください。
入力例 2
5 1 1 1 2 1 3 1 4 1 5
出力例 2
1 1 1 2 1 3 1 4 1 5
入力例 3
10 9 21 8 22 10 28 6 22 6 26 7 10 5 3 8 31 9 4 11 21
出力例 3
5 3 6 22 6 26 7 10 8 22 8 31 9 4 9 21 10 28 11 21
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 100 点
問題文
A を N 個、B を N 個、…、Z を N 個この順に繋げて得られる文字列の先頭から X 番目の文字を求めてください。
制約
- 1 \leq N \leq 100
- 1 \leq X \leq N\times 26
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N X
出力
答えを出力せよ。
入力例 1
1 3
出力例 1
C
得られる文字列は ABCDEFGHIJKLMNOPQRSTUVWXYZ です。先頭から 3 番目の文字は C です。
入力例 2
2 12
出力例 2
F
得られる文字列は AABBCCDDEEFFGGHHIIJJKKLLMMNNOOPPQQRRSSTTUUVVWWXXYYZZ です。先頭から 12 番目の文字は F です。
Score : 100 points
Problem Statement
Find the X-th character from the beginning of the string that is obtained by concatenating these characters: N copies of A's, N copies of B's, …, and N copies of Z's, in this order.
Constraints
- 1 \leq N \leq 100
- 1 \leq X \leq N\times 26
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N X
Output
Print the answer.
Sample Input 1
1 3
Sample Output 1
C
We obtain the string ABCDEFGHIJKLMNOPQRSTUVWXYZ, whose 3-rd character from the beginning is C.
Sample Input 2
2 12
Sample Output 2
F
We obtain the string AABBCCDDEEFFGGHHIIJJKKLLMMNNOOPPQQRRSSTTUUVVWWXXYYZZ, whose 12-th character from the beginning is F.
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 250 点
問題文
. および # からなる文字列 S が与えられます。
以下の条件を全て満たす文字列 T のうち、 o の文字数が最大となるものを一つ求めてください。
- T の長さは S の長さと等しい。
- T は
.、#、oからなる。 - S_i=
#であるとき、またそのときに限り T_i=#である。 - T_i=T_j=
o(i < j) ならば、 T_{i+1},\ldots,T_{j-1} の中に#が 1 つ以上存在する。
制約
- S は
.および#からなる長さ 1 以上 100 以下の文字列
入力
入力は以下の形式で標準入力から与えられる。
S
出力
条件を全て満たす文字列 T のうち、 o の文字数が最大となるものを一つ出力せよ。
そのような文字列が複数ある場合、どれを出力しても正答となる。
入力例 1
#..#.
出力例 1
#o.#o
T= #o.#o とすると全ての条件を満たすことが確認できます。
全ての条件を満たす T であって、 o の文字数が 2 より多い文字列は存在しないので #o.#o を出力すると正答となります。
この他にも #.o#o を出力しても正答となります。
入力例 2
#
出力例 2
#
入力例 3
.....
出力例 3
..o..
この他にも o....、.o...、...o.、....o を出力しても正答となります。
入力例 4
...#..#.##.#.
出力例 4
o..#.o#o##o#o
Score : 250 points
Problem Statement
You are given a string S consisting of . and #.
Among all strings T that satisfy all of the following conditions, find one with the maximum number of os.
- The length of T is equal to the length of S.
- T consists of
.,#, oro. - T_i=
#if and only if S_i=#. - If T_i=T_j=
o(i < j), then there exists at least one#among T_{i+1},\ldots,T_{j-1}.
Constraints
- S is a string consisting of
.and#with length between 1 and 100, inclusive.
Input
The input is given from Standard Input in the following format:
S
Output
Output one string with the maximum number of os among all strings T that satisfy all conditions.
If there are multiple such strings, printing any of them will be considered correct.
Sample Input 1
#..#.
Sample Output 1
#o.#o
Setting T= #o.#o satisfies all conditions.
There is no string T that satisfies all conditions and has more than two os, so outputting #o.#o is correct.
Outputting #.o#o is also correct.
Sample Input 2
#
Sample Output 2
#
Sample Input 3
.....
Sample Output 3
..o..
Outputting o...., .o..., ...o., or ....o is also correct.
Sample Input 4
...#..#.##.#.
Sample Output 4
o..#.o#o##o#o
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
N \times N のグリッド S と M\times M のグリッド T が与えられます。上から i 行目、左から j 列目のマス目をマス (i,j) と表します。
S,T の各マスの色はそれぞれ N^2個の文字 S_{i,j} \; (1\leq i,j\leq N) および M^2 個の文字 T_{i,j} \; (1\leq i,j\leq M) によって表されます。
S_{i,j} が . のとき S のマス (i,j) は白色、S_{i,j} が # のとき S のマス (i,j) は黒色で塗られています。T についても同様です。
S の中から T を探してください。具体的には、以下の条件を満たす a,b \; (1 \leq a,b \leq N-M+1) を出力してください。
- すべての i,j \; (1\leq i,j \leq M) について、S_{a+i-1,b+j-1} = T_{i,j}
制約
- 1 \leq M \leq N \leq 50
- N,M は整数
- S_{i,j},T_{i,j} は
.または# - 条件を満たす a,b はちょうど 1 組存在する。
入力
入力は以下の形式で標準入力から与えられる。
N M
S_{1,1}S_{1,2}\dots S_{1,N}
S_{2,1}S_{2,2}\dots S_{2,N}
\vdots
S_{N,1}S_{N,2}\dots S_{N,N}
T_{1,1}T_{1,2}\dots T_{1,M}
T_{2,1}T_{2,2}\dots T_{2,M}
\vdots
T_{M,1}T_{M,2}\dots T_{M,M}
出力
a,b をこの順に空白区切りで 1 行に出力せよ。
入力例 1
3 2 #.# ..# ##. .# #.
出力例 1
2 2
S の 2 行目から 3 行目、2 列目から 3 列目の 2 \times 2 マスが T と一致します。
入力例 2
2 1 #. ## .
出力例 2
1 2
Score : 200 points
Problem Statement
You are given an N \times N grid S and an M \times M grid T. The cell at the i-th row from the top and the j-th column from the left is denoted by (i,j).
The colors of the cells in S and T are represented by N^2 characters S_{i,j} (1\leq i,j\leq N) and M^2 characters T_{i,j} (1\leq i,j\leq M), respectively. In grid S, cell (i,j) is white if S_{i,j} is ., and black if S_{i,j} is #. The same applies for grid T.
Find T within S. More precisely, output integers a and b (1 \leq a,b \leq N-M+1) that satisfy the following condition:
- S_{a+i-1,b+j-1} = T_{i,j} for every i,j (1\leq i,j \leq M).
Constraints
- 1 \leq M \leq N \leq 50
- N and M are integers.
- Each of S_{i,j} and T_{i,j} is
.or#. - There is exactly one pair (a,b) satisfying the condition.
Input
The input is given from Standard Input in the following format:
N M
S_{1,1}S_{1,2}\dots S_{1,N}
S_{2,1}S_{2,2}\dots S_{2,N}
\vdots
S_{N,1}S_{N,2}\dots S_{N,N}
T_{1,1}T_{1,2}\dots T_{1,M}
T_{2,1}T_{2,2}\dots T_{2,M}
\vdots
T_{M,1}T_{M,2}\dots T_{M,M}
Output
Print a and b in this order, separated by a space on one line.
Sample Input 1
3 2 #.# ..# ##. .# #.
Sample Output 1
2 2
The 2 \times 2 subgrid of S from the 2nd to the 3rd row and from the 2nd to the 3rd column matches T.
Sample Input 2
2 1 #. ## .
Sample Output 2
1 2
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
文字列 S,T が与えられます。S は英小文字からなり、T は S に英小文字を 1 つ挿入して作られたことがわかっています。
挿入された文字は T の先頭から何番目の文字であるか求めてください。
複数の候補が考えられる場合はいずれか 1 つを求めてください。
制約
- 1 \leq |S| \leq 5\times 10^5
- S は英小文字からなる
- T は S に英小文字を 1 つ挿入して作られた文字列である
入力
入力は以下の形式で標準入力から与えられる。
S T
出力
答えを出力せよ。なお、答えが複数考えられる場合はどれを出力しても正解となる。
入力例 1
atcoder atcorder
出力例 1
5
T の先頭から 5 番目の文字 r が挿入された文字です。
入力例 2
million milllion
出力例 2
5
T の先頭から 3,4,5 番目の文字のいずれかが挿入された文字です。
よって、3,4,5 のいずれかを出力すると正解となります。
入力例 3
vvwvw vvvwvw
出力例 3
3
Score : 300 points
Problem Statement
You are given strings S and T. S consists of lowercase English letters, and T is obtained by inserting a lowercase English letter into S.
Find the position of the inserted character in T.
If there are multiple candidates, find any of them.
Constraints
- 1 \leq |S| \leq 5\times 10^5
- S consists of lowercase English letters.
- T is obtained by inserting a lowercase English letter into S.
Input
The input is given from Standard Input in the following format:
S T
Output
Print an integer i, representing that the inserted character is the i-th character from the beginning of T. If there are multiple possible answers, printing any of them is accepted.
Sample Input 1
atcoder atcorder
Sample Output 1
5
The 5-th character from the beginning of T, r, is inserted.
Sample Input 2
million milllion
Sample Output 2
5
One of the 3-rd, 4-th, and 5-th characters from the beginning of T is inserted. Thus, printing any one of 3, 4, and 5 is accepted.
Sample Input 3
vvwvw vvvwvw
Sample Output 3
3