AtCoder Daily Training EASY 2025/10/30 16:30start

A - Buildings

実行時間制限: 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

左から 1 番目のビルより高いビルは、左から 3 番目のビルです。

入力例 2

3
4 3 2

出力例 2

-1

左から 1 番目のビルより高いビルは存在しません。

入力例 3

7
10 5 10 2 10 13 15

出力例 3

左から 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

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

The buildings taller than the first one from the left are the sixth and seventh ones. Among them, the leftmost is the sixth one.

B - Stage Clear

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 100 点

問題文

高橋くんはゲームで遊んでいます。このゲームにはワールドが 8 つあり、それぞれのワールドにはステージが 8 つずつあります。ステージには順番があり、最初のステージは 1 個めのワールドにある 1 個めのステージです。 i 個め (1\le i\le 8) のワールドにある j 個め (1\le j\le 8) のステージの次のステージは、以下のようになっています。

j\lt8 のとき、次のステージは i 個めのワールドにある j+1 個めのステージです。
i\lt8,j=8 のとき、次のステージは i+1 個めのワールドにある 1 個めのステージです。
i=8,j=8 のとき、次のステージはありません。このステージが最後のステージです。

i 個め (1\le i\le 8) のワールドにある j 個め (1\le j\le 8) のステージの名前は i-j です。たとえば、最初のステージ名は 1-1 で、最後のステージ名は 8-8 です。

高橋くんが現在遊んでいるステージのステージ名 S が与えられるので、次のステージのステージ名を出力してください。

制約

S はいずれかのステージのステージ名である。
S は 8-8 ではない。

入力

入力は以下の形式で標準入力から与えられる。

出力

次のステージのステージ名を出力せよ。

入力例 1

4-2

出力例 1

4-3

4 個めのワールドの 2 個めのステージの次のステージは、同じワールドの 3 個めのステージです。

入力例 2

1-8

出力例 2

2-1

1-8 は 1 個めのワールドの最後のステージなので、次のステージは 2 個めのワールドの 1 個めのステージです。

入力例 3

3-3

出力例 3

3-4

Score : 100 points

Problem Statement

Takahashi is playing a game. This game has eight worlds, and each world has eight stages. The stages have an order, and the first stage is the 1st stage in the 1st world. The next stage after the j-th stage (1\le j\le 8) in the i-th world (1\le i\le 8) is as follows:

When j\lt8, the next stage is the (j+1)-th stage in the i-th world.
When i\lt8,j=8, the next stage is the 1st stage in the (i+1)-th world.
When i=8,j=8, there is no next stage. This stage is the last stage.

The name of the j-th stage (1\le j\le 8) in the i-th world (1\le i\le 8) is i-j. For example, the name of the first stage is 1-1, and the name of the last stage is 8-8.

Given the stage name S of the stage Takahashi is currently playing, output the stage name of the next stage.

Constraints

S is the stage name of one of the stages.
S is not 8-8.

Input

The input is given from Standard Input in the following format:

Output

Output the stage name of the next stage.

Sample Input 1

4-2

Sample Output 1

4-3

The next stage after the 2nd stage in the 4th world is the 3rd stage in the same world.

Sample Input 2

1-8

Sample Output 2

2-1

1-8 is the last stage in the 1st world, so the next stage is the 1st stage in the 2nd world.

Sample Input 3

3-3

Sample Output 3

3-4

C - Seek Grid

実行時間制限: 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

D - Caesar Cipher

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 200 点

問題文

高橋君は英小文字からなる文字列 S を持っています。

高橋君は文字列 S に対して、下記の操作をちょうど 1 回行います。

まず、非負整数 K を選ぶ。
その後、S の各文字を K 個後ろの英小文字に変更する。

ただし、

a の 1 個後ろの英小文字は b であり、
b の 1 個後ろの英小文字は c であり、
c の 1 個後ろの英小文字は d であり、
\cdots
y の 1 個後ろの英小文字は z であり、
z の 1 個後ろの英小文字は a です。

例えば、b の 4 個後ろの英小文字は f であり、y の 3 個後ろの英小文字は b です。

文字列 T が与えられます。高橋君が上記の操作によって S を T に一致させることができるかを判定してください。

制約

S と T はそれぞれ英小文字からなる長さ 1 以上 10^5 以下の文字列
S の長さと T の長さは等しい

入力

入力は以下の形式で標準入力から与えられる。

S
T

出力

高橋君が S を T に一致させることができる場合は Yes と出力し、できない場合は No と出力せよ。

入力例 1

abc
ijk

出力例 1

Yes

高橋君が K=8 を選ぶと、

a は 8 個後ろの i に
b は 8 個後ろの j に
c は 8 個後ろの k に

それぞれ変更され、S と T が一致します。
高橋君が S を T に一致させることができるため Yes と出力します。

入力例 2

z
a

出力例 2

Yes

高橋君が K=1 を選ぶと S と T が一致します。
z の 1 個後ろの英小文字は a であることに注意してください。

入力例 3

ppq
qqp

出力例 3

No

高橋君は非負整数 K をどのように選んでも S を T に一致させることができません。よって、No と出力します。

入力例 4

atcoder
atcoder

出力例 4

Yes

高橋君が K=0 を選ぶと S と T が一致します。

Score : 200 points

Problem Statement

Takahashi has a string S consisting of lowercase English letters.

On this string, he will do the operation below just once.

First, choose a non-negative integer K.
Then, shift each character of S to the right by K (see below).

Here,

a shifted to the right by 1 is b;
b shifted to the right by 1 is c;
c shifted to the right by 1 is d;
\cdots
y shifted to the right by 1 is z;
z shifted to the right by 1 is a.

For example, b shifted to the right by 4 is f, and y shifted to the right by 3 is b.

You are given a string T. Determine whether Takahashi can make S equal T by the operation above.

Constraints

Each of S and T is a string of length between 1 and 10^5 (inclusive) consisting of lowercase English letters.
The lengths of S and T are equal.

Input

Input is given from Standard Input in the following format:

S
T

Output

If Takahashi can make S equal T, print Yes; if not, print No.

Sample Input 1

abc
ijk

Sample Output 1

Yes

When Takahashi chooses K=8,

a is shifted to the right by 8 and becomes i,
b is shifted to the right by 8 and becomes j,
c is shifted to the right by 8 and becomes k,

and now S and T are equal.
Therefore, he can make S equal T, so Yes should be printed.

Sample Input 2

z
a

Sample Output 2

Yes

Choosing K=1 makes S and T equal.
Note that the letter on the right of z is a.

Sample Input 3

ppq
qqp

Sample Output 3

No

There is no non-negative integer K that he can choose to make S equal T, so No should be printed.

Sample Input 4

atcoder
atcoder

Sample Output 4

Yes

Choosing K=0 makes S and T equal.

E - Security 2

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 300 点

問題文

AtCoder 社の入口には特殊なパスコード入力装置があり、この装置は文字列を 1 つ表示する画面と 2 つのボタンからなります。

画面に表示される文字列を t とします。 t ははじめ空文字列であり、ボタンを押すことで t に以下の変化が起きます。

ボタン A を押すと、t の末尾に 0 が追加される。
ボタン B を押すと、t に含まれるすべての数字が、それぞれ次の数字に置き換わる。ここで、0 から 8 までの数字については次の数字は 1 大きな数を表す数字とし、9 の次の数字は 0 とする。

たとえば、t が 1984 のときにボタン A を押すと t は 19840 に変化し、さらにボタン B を押すと t は 20951 に変化します。

文字列 S が与えられます。t が空文字列である状態からボタンを 0 回以上押して t を S に一致させるとき、ボタンを最少で何回押す必要があるかを求めてください。

制約

S は 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 からなる文字列
1 \leq |S| \leq 5 \times 10^5 (|S| は S の長さをあらわす)

入力

入力は以下の形式で標準入力から与えられる。

出力

答えを出力せよ。

入力例 1

出力例 1

以下の順にボタンを押せば、t が 21 になります。

ボタン A を押す。t は 0 になる。
ボタン B を押す。t は 1 になる。
ボタン A を押す。t は 10 になる。
ボタン B を押す。t は 21 になる。

4 回より少ない回数ボタンを押して t を 21 にすることはできないので、4 を出力します。

入力例 2

出力例 2

入力例 3

2025524202552420255242025524

出力例 3

Score : 300 points

Problem Statement

At the entrance of AtCoder Inc., there is a special pass-code input device. The device consists of a screen displaying one string, and two buttons.

Let t be the string shown on the screen. Initially, t is the empty string. Pressing a button changes t as follows:

Pressing button A appends 0 to the end of t.
Pressing button B replaces every digit in t with the next digit: for digits 0 through 8 the next digit is the one whose value is larger by 1; the next digit after 9 is 0.

For example, if t is 1984 and button A is pressed, t becomes 19840; if button B is then pressed, t becomes 20951.

You are given a string S. Starting from the empty string, press the buttons zero or more times until t coincides with S. Find the minimum number of button presses required.

Constraints

S is a string consisting of 0, 1, 2, 3, 4, 5, 6, 7, 8, and 9.
1 \le |S| \le 5 \times 10^{5}, where |S| is the length of S.

Input

The input is given from Standard Input in the following format:

Output

Output the answer.

Sample Input 1

Sample Output 1

The following sequence of presses makes t equal to 21.

Press button A. t becomes 0.
Press button B. t becomes 1.
Press button A. t becomes 10.
Press button B. t becomes 21.

It is impossible to obtain 21 with fewer than four presses, so output 4.

Sample Input 2

Sample Output 2

Sample Input 3

2025524202552420255242025524