AtCoder Daily Training EASY 2025/07/23 16:00start

A - Saturday

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

配点 : 100 点

問題文

ある日、学校へ行くのに疲れてしまった高橋くんは、土曜日まであと何日あるかを知りたくなりました。
その日は平日で、曜日を英語で表すと S だったことが分かっています。その日より後の直近の土曜日は何日後かを求めてください。

なお、月曜日、火曜日、水曜日、木曜日、金曜日はそれぞれ英語で Monday, Tuesday, Wednesday, Thursday, Friday です。

制約

S は Monday, Tuesday, Wednesday, Thursday, Friday のいずれかである

入力

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

出力

答えを整数として出力せよ。

入力例 1

Wednesday

出力例 1

この日は水曜日なので、3 日後に土曜日になります。

入力例 2

Monday

出力例 2

Score : 100 points

Problem Statement

One day, tired from going to school, Takahashi wanted to know how many days there were until Saturday.
We know that the day was a weekday, and the name of the day of the week was S in English.
How many days were there until the first Saturday after that day (including Saturday but not the starting day)?

Constraints

S is Monday, Tuesday, Wednesday, Thursday, or Friday.

Input

Input is given from Standard Input in the following format:

Output

Print the answer as an integer.

Sample Input 1

Wednesday

Sample Output 1

It was Wednesday, so there were 3 days until the first Saturday after that day.

Sample Input 2

Monday

Sample Output 2

B - Five Integers

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

配点 : 100 点

問題文

与えられる 5 つの整数 A, B, C, D, E の中に何種類の整数があるかを出力してください。

制約

0 \leq A, B, C, D, E \leq 100
入力はすべて整数

入力

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

A B C D E

出力

答えを出力せよ。

入力例 1

31 9 24 31 24

出力例 1

与えられる 5 つの整数 31, 9, 24, 31, 24 の中には、9, 24, 31 という 3 種類の整数があります。よって、3 を出力します。

入力例 2

0 0 0 0 0

出力例 2

Score : 100 points

Problem Statement

Print how many distinct integers there are in given five integers A, B, C, D, and E.

Constraints

0 \leq A, B, C, D, E \leq 100
All values in input are integers.

Input

Input is given from Standard Input in the following format:

A B C D E

Output

Print the answer.

Sample Input 1

31 9 24 31 24

Sample Output 1

In the given five integers 31, 9, 24, 31, and 24, there are three distinct integers 9, 24, and 31. Thus, 3 should be printed.

Sample Input 2

0 0 0 0 0

Sample Output 2

C - Grid Rotation

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

配点 : 250 点

問題文

縦 N 行横 N 列からなる 2 つのグリッド S,T があります。グリッドの上から i 行目、左から j 列目のマスをマス (i,j) と表します。

グリッド S,T の各マスは白または黒のいずれかに塗られています。S_{i,j} が . のとき S のマス (i,j) は白く、S_{i,j} が # のとき S のマス (i,j) は黒く塗られています。T についても同様です。

次の 2 種類の操作を好きな順序で好きな回数行うとき、グリッド S をグリッド T と一致させるために必要な操作回数の最小値を求めてください。

グリッド S のマスを 1 つ選び、色を変更する
グリッド S 全体を 90 度右に回転する

制約

1\leq N \leq 100
N は整数
S_{i,j},T_{i,j} は . または #

入力

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

N
S_{1,1}S_{1,2}\dots S_{1,N}
\vdots
S_{N,1}S_{N,2}\dots S_{N,N}
T_{1,1}T_{1,2}\dots T_{1,N}
\vdots
T_{N,1}T_{N,2}\dots T_{N,N}

出力

答えを出力せよ。

入力例 1

4
###.
..#.
..#.
..#.
...#
...#
###.
....

出力例 1

下図のようにして 2 回の操作で S を T と一致させることができます。

入力例 2

13
.#..###..##..
#.#.#..#.#.#.
#.#.###..#...
###.#..#.#.#.
#.#.###..##..
.............
..#...#....#.
.##..#.#..##.
#.#..#.#.#.#.
####.#.#.####
..#..#.#...#.
..#...#....#.
.............
.............
.#....#...#..
.#...#.#..#..
####.#.#.####
.#.#.###..#.#
.##....#..##.
.#....#...#..
.............
..##..###.#.#
.#.#.#..#.###
.#.#..###.#.#
.#.#.#..#.#.#
..##..###..#.

出力例 2

Score : 250 points

Problem Statement

There are two grids S and T, each with N rows and N columns. Let (i,j) denote the cell at the i-th row from the top and the j-th column from the left.

Each cell of grids S and T is colored either white or black. Cell (i,j) of S is white if S_{i,j} is ., and black if S_{i,j} is #. The same applies to T.

You may perform the following two types of operations any number of times in any order. Find the minimum number of operations required to make grid S identical to grid T.

Choose one cell of grid S and change its color.
Rotate the entire grid S 90 degrees clockwise.

Constraints

1 \le N \le 100
N is an integer.
Each of S_{i,j} and T_{i,j} is . or #.

Input

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

N
S_{1,1}S_{1,2}\dots S_{1,N}
\vdots
S_{N,1}S_{N,2}\dots S_{N,N}
T_{1,1}T_{1,2}\dots T_{1,N}
\vdots
T_{N,1}T_{N,2}\dots T_{N,N}

Output

Output the minimum number of operations required.

Sample Input 1

4
###.
..#.
..#.
..#.
...#
...#
###.
....

Sample Output 1

You can match S to T in two operations as shown below.

Sample Input 2

13
.#..###..##..
#.#.#..#.#.#.
#.#.###..#...
###.#..#.#.#.
#.#.###..##..
.............
..#...#....#.
.##..#.#..##.
#.#..#.#.#.#.
####.#.#.####
..#..#.#...#.
..#...#....#.
.............
.............
.#....#...#..
.#...#.#..#..
####.#.#.####
.#.#.###..#.#
.##....#..##.
.#....#...#..
.............
..##..###.#.#
.#.#.#..#.###
.#.#..###.#.#
.#.#.#..#.#.#
..##..###..#.

Sample Output 2

D - 3^A

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

配点 : 200 点

問題文

正整数 M が与えられます。以下の条件を全て満たす正整数 N と非負整数列 A=(A_1,A_2,\ldots,A_N) を一つ求めてください。

1\le N\le 20
0\le A_i\le 10 (1\le i\le N)
\displaystyle \sum_{i=1}^N 3^{A_i}=M

ただし、制約下では条件を満たす N と A の組が必ず存在することが証明できます。

制約

1\le M\le 10^5

入力

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

出力

以下の形式で条件を満たす N と A を出力せよ。

N
A_1 A_2 \ldots A_N

なお、条件を満たす N と A の組が複数存在する場合は、どれを出力しても正答となる。

入力例 1

出力例 1

2
1 1

N=2 、A=(1,1) とすると \displaystyle \sum_{i=1}^N 3^{A_i}=3+3=6 より全ての条件を満たします。

他に N=4 、 A=(0,0,1,0) なども条件を満たします。

入力例 2

出力例 2

4
2 0 2 4

入力例 3

出力例 3

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

1\le N\le 20 という制約に注意してください。

Score : 200 points

Problem Statement

You are given a positive integer M. Find a positive integer N and a sequence of non-negative integers A = (A_1, A_2, \ldots, A_N) that satisfy all of the following conditions:

1 \le N \le 20
0 \le A_i \le 10 (1 \le i \le N)
\displaystyle \sum_{i=1}^N 3^{A_i} = M

It can be proved that under the constraints, there always exists at least one such pair of N and A satisfying the conditions.

Constraints

1 \le M \le 10^5

Input

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

Output

Print N and A satisfying the conditions in the following format:

N
A_1 A_2 \ldots A_N

If there are multiple valid pairs of N and A, any of them is acceptable.

Sample Input 1

Sample Output 1

2
1 1

For example, with N=2 and A=(1,1), we have \displaystyle \sum_{i=1}^N 3^{A_i} = 3+3=6, satisfying all conditions.

Another example is N=4 and A=(0,0,1,0), which also satisfies the conditions.

Sample Input 2

Sample Output 2

4
2 0 2 4

Sample Input 3

Sample Output 3

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

Note the condition 1 \le N \le 20.

E - Tile Distance 2

実行時間制限: 2 sec / メモリ制限: 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.