実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 100 点
問題文
N 個のビルが横一列に並んでいて、左から i 番目のビルの高さは H_i です。
左から 1 番目のビルより高いビルが存在するか判定し、存在する場合その内最も左のビルは左から何番目か求めてください。
制約
- 1\leq N\leq 100
- 1\leq H_i \leq 100
- 入力される数値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N H_1 H_2 \ldots H_N
出力
左から 1 番目のビルより高いビルが存在しない場合 -1 を出力せよ。
存在する場合、その内最も左のビルは左から何番目か出力せよ。
入力例 1
4 3 2 5 2
出力例 1
3
左から 1 番目のビルより高いビルは、左から 3 番目のビルです。
入力例 2
3 4 3 2
出力例 2
-1
左から 1 番目のビルより高いビルは存在しません。
入力例 3
7 10 5 10 2 10 13 15
出力例 3
6
左から 1 番目のビルより高いビルは、左から 6 番目のビルと左から 7 番目のビルです。その内最も左のビルは左から 6 番目のビルです。
Score: 100 points
Problem Statement
There are N buildings aligned in a row. The i-th building from the left has a height of H_i.
Determine if there is a building taller than the first one from the left. If such a building exists, find the position of the leftmost such building from the left.
Constraints
- 1 \leq N \leq 100
- 1 \leq H_i \leq 100
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N H_1 H_2 \ldots H_N
Output
If no building is taller than the first one from the left, print -1.
If such a building exists, print the position (index) of the leftmost such building from the left.
Sample Input 1
4 3 2 5 2
Sample Output 1
3
The building taller than the first one from the left is the third one from the left.
Sample Input 2
3 4 3 2
Sample Output 2
-1
No building is taller than the first one from the left.
Sample Input 3
7 10 5 10 2 10 13 15
Sample Output 3
6
The buildings taller than the first one from the left are the sixth and seventh ones. Among them, the leftmost is the sixth one.
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 100 点
問題文
英小文字からなる文字列 S が与えられます。
S から a, e, i, o, u をすべて取り除いて得られる文字列を出力してください。
なお、S は a, e, i, o, u 以外の文字を一つ以上含みます。
制約
- S は英小文字からなる長さ 1 以上 100 以下の文字列
- S は
a,e,i,o,u以外の文字を一つ以上含む
入力
入力は以下の形式で標準入力から与えられる。
S
出力
答えを出力せよ。
入力例 1
atcoder
出力例 1
tcdr
S = atcoder のとき、1, 4, 6 文字目を取り除いて tcdr を得ます。
入力例 2
xyz
出力例 2
xyz
入力例 3
aaaabbbbcccc
出力例 3
bbbbcccc
Score : 100 points
Problem Statement
You are given a string S consisting of lowercase English letters.
Remove all occurrences of a, e, i, o, u from S and print the resulting string.
S contains at least one character other than a, e, i, o, u.
Constraints
- S is a string of length between 1 and 100, inclusive, consisting of lowercase English letters.
- S contains at least one character other than
a,e,i,o,u.
Input
The input is given from Standard Input in the following format:
S
Output
Print the answer.
Sample Input 1
atcoder
Sample Output 1
tcdr
For S = atcoder, remove the 1-st, 4-th, and 6-th characters to get tcdr.
Sample Input 2
xyz
Sample Output 2
xyz
Sample Input 3
aaaabbbbcccc
Sample Output 3
bbbbcccc
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 200 点
問題文
英小文字からなる長さ N の文字列 S が与えられます。 S の x 文字目 (1 \le x \le N) は S_x です。
i=1,2,\dots,N-1 それぞれについて、以下の条件を全て満たす最大の非負整数 l を求めてください。
- l+i \le N である。
- 全ての 1 \le k \le l を満たす整数 k について、 S_{k} \neq S_{k+i} を満たす。
なお、 l=0 は常に条件を満たすことに注意してください。
制約
- N は 2 \le N \le 5000 を満たす整数
- S は英小文字からなる長さ N の文字列
入力
入力は以下の形式で標準入力から与えられる。
N S
出力
N-1 行にわたって出力せよ。そのうち x 行目 (1 \le x < N) には i=x とした場合の答えを整数として出力せよ。
入力例 1
6 abcbac
出力例 1
5 1 2 0 1
この入力では、 S= abcbac です。
- i=1 のとき、 S_1 \neq S_2, S_2 \neq S_3, \dots ,S_5 \neq S_6 であるため、 最大値は l=5 です。
- i=2 のとき、 S_1 \neq S_3 ですが S_2 = S_4 であるため、 最大値は l=1 です。
- i=3 のとき、 S_1 \neq S_4, S_2 \neq S_5 ですが S_3 = S_6 であるため、 最大値は l=2 です。
- i=4 のとき、 S_1 = S_5 であるため、 最大値は l=0 です。
- i=5 のとき、 S_1 \neq S_6 であるため、 最大値は l=1 です。
Score : 200 points
Problem Statement
You are given a string S of length N consisting of lowercase English letters. The x-th (1 \le x \le N) character of S is S_x.
For each i=1,2,\dots,N-1, find the maximum non-negative integer l that satisfies all of the following conditions:
- l+i \le N, and
- for all integers k such that 1 \le k \le l, it holds that S_{k} \neq S_{k+i}.
Note that l=0 always satisfies the conditions.
Constraints
- N is an integer such that 2 \le N \le 5000.
- S is a string of length N consisting of lowercase English letters.
Input
The input is given from Standard Input in the following format:
N S
Output
Print (N-1) lines. The x-th (1 \le x < N) line should contain the answer as an integer when i=x.
Sample Input 1
6 abcbac
Sample Output 1
5 1 2 0 1
In this input, S= abcbac.
- When i=1, we have S_1 \neq S_2, S_2 \neq S_3, \dots, and S_5 \neq S_6, so the maximum value is l=5.
- When i=2, we have S_1 \neq S_3 but S_2 = S_4, so the maximum value is l=1.
- When i=3, we have S_1 \neq S_4 and S_2 \neq S_5 but S_3 = S_6, so the maximum value is l=2.
- When i=4, we have S_1 = S_5, so the maximum value is l=0.
- When i=5, we have S_1 \neq S_6, so the maximum value is l=1.
実行時間制限: 2 sec / メモリ制限: 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
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 300 点
問題文
上下左右に広がる N\times N のマス目があり、最初全てのマスは白く塗られています。このマス目の上から i 行目、左から j 列目のマスを (i,j) で表します。
高橋君は 1 以上 N 以下の整数 A, B を持っており、次のような操作を行います。
- \max(1-A,1-B)\leq k\leq \min(N-A,N-B) をみたす全ての整数 k について、(A+k,B+k) を黒く塗る。
- \max(1-A,B-N)\leq k\leq \min(N-A,B-1) をみたす全ての整数 k について、(A+k,B-k) を黒く塗る。
この操作を行った後のマス目について、P\leq i\leq Q かつ R\leq j\leq S をみたす各マス (i,j) がそれぞれ何色で塗られているか求めてください。
制約
- 1 \leq N \leq 10^{18}
- 1 \leq A \leq N
- 1 \leq B \leq N
- 1 \leq P \leq Q \leq N
- 1 \leq R \leq S \leq N
- (Q-P+1)\times(S-R+1)\leq 3\times 10^5
- 入力は全て整数である。
入力
入力は以下の形式で標準入力から与えられる。
N A B P Q R S
出力
Q-P+1 行出力せよ。
各行は # と . のみからなる長さ S-R+1 の文字列であり、
i 行目の文字列の j 番目の文字が
# であることは (P+i-1,R+j-1) が黒く塗られていることを、
. であることは (P+i-1,R+j-1) が白く塗られていることをさす。
入力例 1
5 3 2 1 5 1 5
出力例 1
...#. #.#.. .#... #.#.. ...#.
1 つめの操作で (2,1), (3,2), (4,3), (5,4) の 4 マスが、
2 つめの操作で (4,1), (3,2), (2,3), (1,4) の 4 マスが黒く塗られます。
よって、P=1, Q=5, R=1, S=5 より、上のように出力します。
入力例 2
5 3 3 4 5 2 5
出力例 2
#.#. ...#
操作によって、
(1,1), (1,5), (2,2), (2,4), (3,3), (4,2), (4,4), (5,1), (5,5) の 9 マスが
黒く塗られます。
P=4, Q=5, R=2, S=5 より、上のように出力します。
入力例 3
1000000000000000000 999999999999999999 999999999999999999 999999999999999998 1000000000000000000 999999999999999998 1000000000000000000
出力例 3
#.# .#. #.#
入力が 32 bit 整数型に収まらないことがあることに注意してください。
Score : 300 points
Problem Statement
There is an N\times N grid with horizontal rows and vertical columns, where all squares are initially painted white. Let (i,j) denote the square at the i-th row and j-th column.
Takahashi has integers A and B, which are between 1 and N (inclusive). He will do the following operations.
- For every integer k such that \max(1-A,1-B)\leq k\leq \min(N-A,N-B), paint (A+k,B+k) black.
- For every integer k such that \max(1-A,B-N)\leq k\leq \min(N-A,B-1), paint (A+k,B-k) black.
In the grid after these operations, find the color of each square (i,j) such that P\leq i\leq Q and R\leq j\leq S.
Constraints
- 1 \leq N \leq 10^{18}
- 1 \leq A \leq N
- 1 \leq B \leq N
- 1 \leq P \leq Q \leq N
- 1 \leq R \leq S \leq N
- (Q-P+1)\times(S-R+1)\leq 3\times 10^5
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N A B P Q R S
Output
Print Q-P+1 lines.
Each line should contain a string of length S-R+1 consisting of # and ..
The j-th character of the string in the i-th line should be # to represent that (P+i-1, R+j-1) is painted black, and . to represent that (P+i-1, R+j-1) is white.
Sample Input 1
5 3 2 1 5 1 5
Sample Output 1
...#. #.#.. .#... #.#.. ...#.
The first operation paints the four squares (2,1), (3,2), (4,3), (5,4) black, and the second paints the four squares (4,1), (3,2), (2,3), (1,4) black.
Thus, the above output should be printed, since P=1, Q=5, R=1, S=5.
Sample Input 2
5 3 3 4 5 2 5
Sample Output 2
#.#. ...#
The operations paint the nine squares (1,1), (1,5), (2,2), (2,4), (3,3), (4,2), (4,4), (5,1), (5,5).
Thus, the above output should be printed, since P=4, Q=5, R=2, S=5.
Sample Input 3
1000000000000000000 999999999999999999 999999999999999999 999999999999999998 1000000000000000000 999999999999999998 1000000000000000000
Sample Output 3
#.# .#. #.#
Note that the input may not fit into a 32-bit integer type.