AtCoder Daily Training EASY 2026/06/10 18:00start

A - Edge Checker 2

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

下の画像で示す図において、a 番の点と b 番の点が線で直接結ばれているかを答えてください。

制約

1 \leq a \lt b \leq 15
a,b は整数

入力

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

a b

出力

a 番の点と b 番の点が線で直接結ばれているなら Yes、結ばれていないなら No を出力せよ。

入力例 1

1 2

出力例 1

Yes

問題文で示した図において、1 番の点と 2 番の点は線で直接結ばれています。よって、Yes を出力します。

入力例 2

2 8

出力例 2

No

問題文で示した図において、2 番の点と 8 番の点は線で直接結ばれていません。よって、No を出力します。

入力例 3

14 15

出力例 3

No

Score : 100 points

Problem Statement

Determine if there is a segment that directly connects the points numbered a and b in the figure below.

Constraints

1 \leq a \lt b \leq 15
a and b are integers.

Input

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

a b

Output

Print Yes if there is a segment that directly connects the points numbered a and b; print No otherwise.

Sample Input 1

1 2

Sample Output 1

Yes

In the figure in the Problem Statement, there is a segment that directly connects the points numbered 1 and 2, so Yes should be printed.

Sample Input 2

2 8

Sample Output 2

No

In the figure in the Problem Statement, there is no segment that directly connects the points numbered 2 and 8, so No should be printed.

Sample Input 3

14 15

Sample Output 3

No

B - AtCoder Language

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

高橋君は、AtCoder 語を勉強しています。

高橋君は英単語に対して AtCoder 語の単語を対応させて覚えています。

高橋君は英語における red, blue, green は AtCoder 語ではそれぞれ SSS, FFF, MMM に対応していることを覚えており、他の単語は覚えていません。

英小文字からなる文字列 S が与えられます。S が高橋君が AtCoder 語との対応を覚えている英単語の表記と一致しているならば S に対応している AtCoder 語の単語を、そうでないならば文字列 Unknown を出力してください。

制約

S は長さ 1 以上 10 以下の英小文字からなる文字列

入力

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

出力

問題文中の指示に従い、文字列を出力せよ。

入力例 1

red

出力例 1

SSS

英語における red は AtCoder 語における SSS に対応します。

入力例 2

atcoder

出力例 2

Unknown

Score : 100 points

Problem Statement

Takahashi is learning AtCoderish Language.

He memorizes AtCoderish words corresponding to English words.

He knows that red, blue, and green in English respectively correspond to SSS, FFF, and MMM in AtCoderish, and he knows no other words.

You are given a string S consisting of lowercase English letters. If S equals an English word that Takahashi knows corresponds to an AtCoderish word, output the AtCoderish word corresponding to S; otherwise, output the string Unknown.

Constraints

S is a string of length between 1 and 10, inclusive, consisting of English letters.

Input

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

Output

Output a string according to the instructions in the problem statement.

Sample Input 1

red

Sample Output 1

SSS

red in English corresponds to SSS in AtCoderish.

Sample Input 2

atcoder

Sample Output 2

Unknown

C - Hit and Blow

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

長さ N の整数列 A = (A_1, A_2, \dots, A_N), B = (B_1, B_2, \dots, B_N) が与えられます。
A の要素はすべて異なります。B の要素もすべて異なります。

次の 2 つを出力してください。

A にも B にも含まれ、その位置も一致している整数の個数。言い換えると、A_i = B_i を満たす整数 i の個数。
A にも B にも含まれるが、その位置は異なる整数の個数。言い換えると、A_i = B_j, i \neq j を満たす整数の組 (i, j) の個数。

制約

1 \leq N \leq 1000
1 \leq A_i \leq 10^9
1 \leq B_i \leq 10^9
A_1, A_2, \dots, A_N はすべて異なる。
B_1, B_2, \dots, B_N はすべて異なる。
入力はすべて整数である。

入力

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

N
A_1 A_2 \dots A_N
B_1 B_2 \dots B_N

出力

答えを 2 行出力せよ。1 行目には 1. の個数、2 行目には 2. の個数を出力せよ。

入力例 1

4
1 3 5 2
2 3 1 4

出力例 1

1
2

A にも B にも含まれ、その位置も一致している整数は A_2 = B_2 = 3 の 1 個です。
A にも B にも含まれるが、その位置は異なる整数は A_1 = B_3 = 1 と A_4 = B_1 = 2 の 2 個です。

入力例 2

3
1 2 3
4 5 6

出力例 2

0
0

1., 2. ともに条件を満たす整数は存在しません。

入力例 3

7
4 8 1 7 9 5 6
3 5 1 7 8 2 6

出力例 3

3
2

Score : 200 points

Problem Statement

You are given integer sequences, each of length N: A = (A_1, A_2, \dots, A_N) and B = (B_1, B_2, \dots, B_N).
All elements of A are different. All elements of B are different, too.

Print the following two values.

The number of integers contained in both A and B, appearing at the same position in the two sequences. In other words, the number of integers i such that A_i = B_i.
The number of integers contained in both A and B, appearing at different positions in the two sequences. In other words, the number of pairs of integers (i, j) such that A_i = B_j and i \neq j.

Constraints

1 \leq N \leq 1000
1 \leq A_i \leq 10^9
1 \leq B_i \leq 10^9
A_1, A_2, \dots, A_N are all different.
B_1, B_2, \dots, B_N are all different.
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 \dots A_N
B_1 B_2 \dots B_N

Output

Print the answers in two lines: the answer to1. in the first line, and the answer to2. in the second line.

Sample Input 1

4
1 3 5 2
2 3 1 4

Sample Output 1

1
2

There is one integer contained in both A and B, appearing at the same position in the two sequences: A_2 = B_2 = 3.
There are two integers contained in both A and B, appearing at different positions in the two sequences: A_1 = B_3 = 1 and A_4 = B_1 = 2.

Sample Input 2

3
1 2 3
4 5 6

Sample Output 2

0
0

In both 1. and 2., no integer satisfies the condition.

Sample Input 3

7
4 8 1 7 9 5 6
3 5 1 7 8 2 6

Sample Output 3

3
2

D - Longest Palindrome

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

文字列 S が与えられます。 S の連続する部分文字列のうち、回文であるものの長さの最大値を求めてください。
ただし、S の連続する部分文字列であって回文であるものは常に存在します。

制約

S は長さ 2 以上 100 以下の英大文字からなる文字列

入力

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

出力

答えを出力せよ。

入力例 1

TOYOTA

出力例 1

TOYOTA の連続する部分文字列 TOYOT は長さ 5 の回文です。
TOYOTA の唯一の長さ 6 の連続する部分文字列 TOYOTA は回文でないので、5 を出力します。

入力例 2

ABCDEFG

出力例 2

すべての長さ 1 の連続する部分文字列は回文です。

入力例 3

AAAAAAAAAA

出力例 3

Score : 200 points

Problem Statement

You are given a string S. Find the maximum length of a contiguous substring of S that is a palindrome.
Note that there is always a contiguous substring of S that is a palindrome.

Constraints

S is a string of length between 2 and 100, inclusive, consisting of uppercase English letters.

Input

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

Output

Print the answer.

Sample Input 1

TOYOTA

Sample Output 1

TOYOT, a contiguous substring of TOYOTA, is a palindrome of length 5.
TOYOTA, the only length-6 contiguous substring of TOYOTA, is not a palindrome, so print 5.

Sample Input 2

ABCDEFG

Sample Output 2

Every contiguous substring of length 1 is a palindrome.

Sample Input 3

AAAAAAAAAA

Sample Output 3

E - Tile Distance 2

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 350 点

問題文

座標平面上に 2\times1 の大きさのタイルが敷き詰められています。タイルは、次の規則に従って敷き詰められています。

整数の組 (i,j) に対し、正方形 A _ {i,j}=\lbrace(x,y)\mid i\leq x\leq i+1\wedge j\leq y\leq j+1\rbrace は 1 つのタイルに含まれる。
i+j が偶数のとき、A _ {i,j} と A _ {i + 1,j} は同じタイルに含まれる。

ただし、タイルは境界を含むものとし、共通部分が正の面積をもつような 2 つの異なるタイルは存在しないとします。

原点の近くでは、タイルは以下のように敷き詰められています。

高橋君は、はじめ座標平面上の点 (S _ x+0.5,S _ y+0.5) にいます。

高橋君は、次の移動を好きなだけ繰り返します。

上下左右の方向と正の整数 n を選ぶ。その方向に n だけ進む。

高橋君が異なるタイルを通るたび、高橋君は通行料を 1 だけ支払います。

高橋君が点 (T _ x+0.5,T _ y+0.5) にたどり着くために支払わなければならない通行料の最小値を求めてください。

制約

0\leq S _ x\leq2\times10 ^ {16}
0\leq S _ y\leq2\times10 ^ {16}
0\leq T _ x\leq2\times10 ^ {16}
0\leq T _ y\leq2\times10 ^ {16}
入力はすべて整数

入力

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

S _ x S _ y
T _ x T _ y

出力

高橋君が支払わなければならない通行料の最小値を出力せよ。

入力例 1

5 0
2 5

出力例 1

例えば、以下のように移動することで支払う通行料を 5 にすることができます。

左に 1 進む。通行料を 0 支払う。
上に 1 進む。通行料を 1 支払う。
左に 1 進む。通行料を 0 支払う。
上に 3 進む。通行料を 3 支払う。
左に 1 進む。通行料を 0 支払う。
上に 1 進む。通行料を 1 支払う。

支払う通行料を 4 以下にすることはできないので、5 を出力してください。

入力例 2

3 1
4 1

出力例 2

通行料を支払わなくてよい場合もあります。

入力例 3

2552608206527595 5411232866732612
771856005518028 7206210729152763

出力例 3

1794977862420151

出力すべき値が 32\operatorname{bit} 整数の範囲に収まらない場合があることに注意してください。

Score : 350 points

Problem Statement

The coordinate plane is covered with 2\times1 tiles. The tiles are laid out according to the following rules:

For an integer pair (i,j), the square A _ {i,j}=\lbrace(x,y)\mid i\leq x\leq i+1\wedge j\leq y\leq j+1\rbrace is contained in one tile.
When i+j is even, A _ {i,j} and A _ {i + 1,j} are contained in the same tile.

Tiles include their boundaries, and no two different tiles share a positive area.

Near the origin, the tiles are laid out as follows:

Takahashi starts at the point (S _ x+0.5,S _ y+0.5) on the coordinate plane.

He can repeat the following move as many times as he likes:

Choose a direction (up, down, left, or right) and a positive integer n. Move n units in that direction.

Each time he enters a tile, he pays a toll of 1.

Find the minimum toll he must pay to reach the point (T _ x+0.5,T _ y+0.5).

Constraints

0\leq S _ x\leq2\times10 ^ {16}
0\leq S _ y\leq2\times10 ^ {16}
0\leq T _ x\leq2\times10 ^ {16}
0\leq T _ y\leq2\times10 ^ {16}
All input values are integers.

Input

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

S _ x S _ y
T _ x T _ y

Output

Print the minimum toll Takahashi must pay.

Sample Input 1

5 0
2 5

Sample Output 1

For example, Takahashi can pay a toll of 5 by moving as follows:

Move left by 1. Pay a toll of 0.
Move up by 1. Pay a toll of 1.
Move left by 1. Pay a toll of 0.
Move up by 3. Pay a toll of 3.
Move left by 1. Pay a toll of 0.
Move up by 1. Pay a toll of 1.

It is impossible to reduce the toll to 4 or less, so print 5.

Sample Input 2

3 1
4 1

Sample Output 2

There are cases where no toll needs to be paid.

Sample Input 3

2552608206527595 5411232866732612
771856005518028 7206210729152763

Sample Output 3

1794977862420151

Note that the value to be output may exceed the range of a 32-bit integer.