AtCoder Daily Training EASY 2024/12/24 17:30start

A - Shout Everyday

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

配点 : 150 点

問題文

AtCoder 王国の住民は A 時になるとたこ焼きへの愛を叫ぶことになっています。

AtCoder 王国に住む高橋君は毎日 B 時に就寝し C 時に起床します。高橋君は、起きているときはたこ焼きへの愛を叫ぶことができ、寝ているときは叫ぶことができません。高橋君が毎日たこ焼きへの愛を叫ぶことができているか判定してください。ただし、一日は 24 時間であり、高橋君が寝ている時間は 24 時間未満であるとします。

制約

0\leq A,B,C\lt 24
A,B,C は相異なる
入力は全て整数

入力

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

A B C

出力

高橋君が毎日たこ焼きへの愛を叫ぶことができているならば Yes を、そうでないならば No を出力せよ。

入力例 1

21 8 14

出力例 1

Yes

高橋君は毎日 8 時に就寝し 14 時に起床します。21 時には起きているため、高橋君は毎日たこ焼きへの愛を叫ぶことができます。よって Yes を出力します。

入力例 2

0 21 7

出力例 2

No

高橋君は毎日 21 時に就寝し 7 時に起床します。0 時には起きていないため、高橋君は毎日たこ焼きへの愛を叫ぶことができません。よって No を出力します。

入力例 3

10 7 17

出力例 3

No

Score : 150 points

Problem Statement

In the Kingdom of AtCoder, residents are required to shout their love for takoyaki at A o'clock every day.

Takahashi, who lives in the Kingdom of AtCoder, goes to bed at B o'clock and wakes up at C o'clock every day (in the 24-hour clock). He can shout his love for takoyaki when he is awake, but cannot when he is asleep. Determine whether he can shout his love for takoyaki every day. Here, a day has 24 hours, and his sleeping time is less than 24 hours.

Constraints

0\leq A,B,C\lt 24
A, B, and C are pairwise different.
All input values are integers.

Input

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

A B C

Output

Print Yes if Takahashi can shout his love for takoyaki every day, and No otherwise.

Sample Input 1

21 8 14

Sample Output 1

Yes

Takahashi goes to bed at 8 o'clock and wakes up at 14 o'clock every day. He is awake at 21 o'clock, so he can shout his love for takoyaki every day. Therefore, print Yes.

Sample Input 2

0 21 7

Sample Output 2

No

Takahashi goes to bed at 21 o'clock and wakes up at 7 o'clock every day. He is not awake at 0 o'clock, so he cannot shout his love for takoyaki every day. Therefore, print No.

Sample Input 3

10 7 17

Sample Output 3

No

B - Intersection

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

配点 : 100 点

問題文

数直線があり、高橋君はこれを赤色と青色で次のように塗りました。

X=L_1 から X=R_1 までをすべて赤色で塗る。
X=L_2 から X=R_2 までをすべて青色で塗る。

数直線のうち、赤色と青色の両方で塗られている部分の長さを求めてください。

制約

0\leq L_1<R_1\leq 100
0\leq L_2<R_2\leq 100
入力はすべて整数

入力

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

L_1 R_1 L_2 R_2

出力

両方の色で塗られている部分の長さを整数で出力せよ。

入力例 1

0 3 1 5

出力例 1

X=0 から X=3 までが赤く、 X=1 から X=5 までが青く塗られています。

よって、両方の色で塗られている部分は X=1 から X=3 までであり、その長さは 2 となります。

入力例 2

0 1 4 5

出力例 2

両方の色で塗られている部分はありません。

入力例 3

0 3 3 7

出力例 3

赤色と青色で塗られている部分が接している場合でも、両方の色で塗られている部分の長さは 0 となります。

Score : 100 points

Problem Statement

We have a number line. Takahashi painted some parts of this line, as follows:

First, he painted the part from X=L_1 to X=R_1 red.
Next, he painted the part from X=L_2 to X=R_2 blue.

Find the length of the part of the line painted both red and blue.

Constraints

0\leq L_1<R_1\leq 100
0\leq L_2<R_2\leq 100
All values in input are integers.

Input

Input is given from Standard Input in the following format:

L_1 R_1 L_2 R_2

Output

Print the length of the part of the line painted both red and blue, as an integer.

Sample Input 1

0 3 1 5

Sample Output 1

The part from X=0 to X=3 is painted red, and the part from X=1 to X=5 is painted blue.

Thus, the part from X=1 to X=3 is painted both red and blue, and its length is 2.

Sample Input 2

0 1 4 5

Sample Output 2

No part is painted both red and blue.

Sample Input 3

0 3 3 7

Sample Output 3

If the part painted red and the part painted blue are adjacent to each other, the length of the part painted both red and blue is 0.

C - Delimiter

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

配点 : 150 点

問題文

N 個の整数 A_1,A_2,\dots,A_N が、 1 行に 1 つずつ、 N 行にわたって与えられます。但し、 N は入力では与えられません。
さらに、以下が保証されます。

A_i \neq 0 ( 1 \le i \le N-1 )
A_N = 0

A_N, A_{N-1},\dots,A_1 をこの順に出力してください。

制約

入力は全て整数
1 \le N \le 100
1 \le A_i \le 10^9 ( 1 \le i \le N-1 )
A_N = 0

入力

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

A_1
A_2
\vdots
A_N

出力

A_N, A_{N-1},\dots,A_1 をこの順に、改行区切りで整数として出力せよ。

入力例 1

出力例 1

繰り返しになりますが、 N は入力では与えられないことに注意してください。
この入力においては N=4 で、 A=(3,2,1,0) です。

入力例 2

出力例 2

A=(0) です。

入力例 3

出力例 3

Score: 150 points

Problem Statement

You are given N integers A_1,A_2,\dots,A_N, one per line, over N lines. However, N is not given in the input.
Furthermore, the following is guaranteed:

A_i \neq 0 ( 1 \le i \le N-1 )
A_N = 0

Print A_N, A_{N-1},\dots,A_1 in this order.

Constraints

All input values are integers.
1 \le N \le 100
1 \le A_i \le 10^9 ( 1 \le i \le N-1 )
A_N = 0

Input

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

A_1
A_2
\vdots
A_N

Output

Print A_N, A_{N-1}, \dots, A_1 in this order, as integers, separated by newlines.

Sample Input 1

Sample Output 1

Note again that N is not given in the input. Here, N=4 and A=(3,2,1,0).

Sample Input 2

Sample Output 2

A=(0).

Sample Input 3

Sample Output 3

D - Enlarged Checker Board

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

配点 : 200 点

問題文

縦 A 行、横 B 列のマスからなるタイルを縦 N 行、横 N 列に並べてできた、縦 (A\times N) 行、横 (B\times N) 列のマス目 X があります。
1\leq i,j \leq N について、上から i 行目、左から j 列目のタイルをタイル (i,j) とします。

X の各マスは以下のように塗られています。

各タイルは白いタイルまたは黒いタイルである。
白いタイルのすべてのマスは白で塗られ、黒いタイルのすべてのマスは黒で塗られている。
タイル (1,1) は白いタイルである。
辺で隣接する 2 つのタイルは異なる色のタイルである。ただし、タイル (a,b) とタイル (c,d) が辺で隣接するとは、|a-c|+|b-d|=1 ( |x| を x の絶対値とする)であることを言う。

マス目 X を出力の形式に従って出力してください。

制約

1 \leq N,A,B \leq 10
入力は全て整数

入力

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

N A B

出力

次の条件をみたす (A\times N) 個の文字列 S_1,\ldots,S_{A\times N} を改行区切りで出力せよ。

S_1,\ldots,S_{A\times N} はそれぞれ長さ (B\times N) の . または # からなる文字列である。
各 i,j (1 \leq i \leq A\times N,1 \leq j \leq B\times N) に対し、マス目 X の上から i 行目かつ左から j 列目のマスが白で塗られているならば S_i の j 文字目は .であり、黒く塗られているならば # である。

入力例 1

4 3 2

出力例 1

..##..##
..##..##
..##..##
##..##..
##..##..
##..##..
..##..##
..##..##
..##..##
##..##..
##..##..
##..##..

入力例 2

5 1 5

出力例 2

.....#####.....#####.....
#####.....#####.....#####
.....#####.....#####.....
#####.....#####.....#####
.....#####.....#####.....

入力例 3

4 4 1

出力例 3

.#.#
.#.#
.#.#
.#.#
#.#.
#.#.
#.#.
#.#.
.#.#
.#.#
.#.#
.#.#
#.#.
#.#.
#.#.
#.#.

入力例 4

1 4 4

出力例 4

....
....
....
....

Score : 200 points

Problem Statement

Tiles are aligned in N horizontal rows and N vertical columns. Each tile has a grid with A horizontal rows and B vertical columns. On the whole, the tiles form a grid X with (A\times N) horizontal rows and (B\times N) vertical columns.
For 1\leq i,j \leq N, Tile (i,j) denotes the tile at the i-th row from the top and the j-th column from the left.

Each square of X is painted as follows.

Each tile is either a white tile or a black tile.
Every square in a white tile is painted white; every square in a black tile is painted black.
Tile (1,1) is a white tile.
Two tiles sharing a side have different colors. Here, Tile (a,b) and Tile (c,d) are said to be sharing a side if and only if |a-c|+|b-d|=1 (where |x| denotes the absolute value of x).

Print the grid X in the format specified in the Output section.

Constraints

1 \leq N,A,B \leq 10
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N A B

Output

Print (A\times N) strings S_1,\ldots,S_{A\times N} that satisfy the following condition, with newlines in between.

Each of S_1,\ldots,S_{A\times N} is a string of length (B\times N) consisting of . and #.
For each i and j (1 \leq i \leq A\times N,1 \leq j \leq B\times N), the j-th character of S_i is . if the square at the i-th row from the top and j-th column from the left in grid X is painted white; the character is # if the square is painted black.

Sample Input 1

4 3 2

Sample Output 1

..##..##
..##..##
..##..##
##..##..
##..##..
##..##..
..##..##
..##..##
..##..##
##..##..
##..##..
##..##..

Sample Input 2

5 1 5

Sample Output 2

.....#####.....#####.....
#####.....#####.....#####
.....#####.....#####.....
#####.....#####.....#####
.....#####.....#####.....

Sample Input 3

4 4 1

Sample Output 3

.#.#
.#.#
.#.#
.#.#
#.#.
#.#.
#.#.
#.#.
.#.#
.#.#
.#.#
.#.#
#.#.
#.#.
#.#.
#.#.

Sample Input 4

1 4 4

Sample Output 4

....
....
....
....

E - Count Arithmetic Subarrays

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

配点 : 300 点

問題文

長さ N の正整数列 A=(A_1,A_2,\dots,A_N) が与えられます。

1\leq l\leq r\leq N を満たす整数の組 (l,r) であって、数列 (A_l,A_{l+1},\dots,A_r) が等差数列であるようなものが何通りあるか求めてください。

なお、数列 (x_1,x_2,\dots,x_{|x|}) が等差数列であるとは、ある d が存在して x_{i+1}-x_i=d\ (1\leq i < |x|) であることをいいます。特に、長さ 1 の数列は常に等差数列です。

制約

1\leq N \leq 2\times 10^5
1\leq A_i \leq 10^9
入力は全て整数

入力

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

N
A_1 A_2 \dots A_N

出力

答えを出力せよ。

入力例 1

4
3 6 9 3

出力例 1

条件を満たす整数の組 (l,r) は (1,1),(2,2),(3,3),(4,4),(1,2),(2,3),(3,4),(1,3) の 8 通りです。

実際、(l,r)=(1,3) のとき (A_l,\dots,A_r)=(3,6,9) は等差数列なので条件を満たしますが、 (l,r)=(2,4) のとき (A_l,\dots,A_r)=(6,9,3) は等差数列ではないので条件を満たしません。

入力例 2

5
1 1 1 1 1

出力例 2

すべての整数の組 (l,r)\ (1\leq l\leq r\leq 5) が条件を満たします。

入力例 3

8
87 42 64 86 72 58 44 30

出力例 3

Score : 300 points

Problem Statement

You are given a sequence of N positive integers A=(A_1,A_2,\dots,A_N).

Find the number of pairs of integers (l,r) satisfying 1\leq l\leq r\leq N such that the subsequence (A_l,A_{l+1},\dots,A_r) forms an arithmetic progression.

A sequence (x_1,x_2,\dots,x_{|x|}) is an arithmetic progression if and only if there exists a d such that x_{i+1}-x_i=d\ (1\leq i < |x|). In particular, a sequence of length 1 is always an arithmetic progression.

Constraints

1\leq N \leq 2\times 10^5
1\leq A_i \leq 10^9
All input values are integers.

Input

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

N
A_1 A_2 \dots A_N

Output

Print the answer.

Sample Input 1

4
3 6 9 3

Sample Output 1

There are eight pairs of integers (l,r) satisfying the condition: (1,1),(2,2),(3,3),(4,4),(1,2),(2,3),(3,4),(1,3).

Indeed, when (l,r)=(1,3), (A_l,\dots,A_r)=(3,6,9) is an arithmetic progression, so it satisfies the condition. However, when (l,r)=(2,4), (A_l,\dots,A_r)=(6,9,3) is not an arithmetic progression, so it does not satisfy the condition.

Sample Input 2

5
1 1 1 1 1

Sample Output 2

All pairs of integers (l,r)\ (1\leq l\leq r\leq 5) satisfy the condition.

Sample Input 3

8
87 42 64 86 72 58 44 30