AtCoder Daily Training EASY 2025/11/04 17:30start

A - Sigma Cubes

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

配点 : 100 点

問題文

正整数 N が与えられます。

i=1,2,\ldots,N について (-1)^i \times i^3 を計算したときの、それら N 個の値の総和を求めてください。

すなわち、 \displaystyle \sum_{i=1}^N (-1)^i \times i^3 を求めてください。

制約

N は 1 以上 10 以下の整数

入力

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

出力

\displaystyle \sum_{i=1}^N (-1)^i \times i^3 の値を出力せよ。

入力例 1

出力例 1

-20

i=1 のとき： (-1)^i\times i^3=-1 です。
i=2 のとき： (-1)^i\times i^3=8 です。
i=3 のとき： (-1)^i\times i^3=-27 です。

したがって、 -1 + 8 - 27 = -20 を出力してください。

入力例 2

出力例 2

-425

入力例 3

出力例 3

Score : 100 points

Problem Statement

You are given a positive integer N.

For i=1,2,\ldots,N, calculate (-1)^i \times i^3, and find the sum of these N values.

That is, find \displaystyle \sum_{i=1}^N (-1)^i \times i^3.

Constraints

N is an integer between 1 and 10, inclusive.

Input

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

Output

Output the value of \displaystyle \sum_{i=1}^N (-1)^i \times i^3.

Sample Input 1

Sample Output 1

-20

When i=1: (-1)^i\times i^3=-1.
When i=2: (-1)^i\times i^3=8.
When i=3: (-1)^i\times i^3=-27.

Therefore, output -1 + 8 - 27 = -20.

Sample Input 2

Sample Output 2

-425

Sample Input 3

Sample Output 3

B - Misdelivery

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

配点 : 100 点

問題文

AtCoder マンションには 1 号室から N 号室までの N 個の部屋があります。
各 i 号室には S_i さんが 1 人で住んでいます。

あなたは X 号室の Y さん宛に荷物を届けようとしています。宛先が正しいかどうかを判定してください。

制約

1 \leq N \leq 100
1 \leq X \leq N
N,X は整数
S_i および Y は英小文字のみからなる長さ 1 以上 10 以下の文字列

入力

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

N
S_1
S_2
\vdots
S_N
X Y

出力

X 号室に住んでいる人の名前が Y であるとき Yes、そうでないとき No と出力せよ。

入力例 1

3
sato
suzuki
takahashi
3 takahashi

出力例 1

Yes

3 号室に住んでいるのは takahashi さんであり、荷物の宛名と一致しています。

入力例 2

3
sato
suzuki
takahashi
1 aoki

出力例 2

No

1 号室に住んでいるのは sato さんであり、荷物の宛名である aoki と一致しません。

入力例 3

2
smith
smith
1 smith

出力例 3

Yes

AtCoder マンションには異なる部屋に同じ名前の人が住んでいることがあります。

入力例 4

2
wang
li
2 wang

出力例 4

No

Score : 100 points

Problem Statement

Mansion AtCoder has N rooms numbered from room 1 to room N.
Each room i is inhabited by one person named S_i.

You are to deliver a package addressed to Mr./Ms. Y in room X. Determine whether the destination is correct.

Constraints

1 \leq N \leq 100
1 \leq X \leq N
N and X are integers.
S_i and Y are strings consisting of lowercase English letters with length between 1 and 10, inclusive.

Input

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

N
S_1
S_2
\vdots
S_N
X Y

Output

Print Yes if the name of the person living in room X is Y, and No otherwise.

Sample Input 1

3
sato
suzuki
takahashi
3 takahashi

Sample Output 1

Yes

The person living in room 3 is takahashi, which matches the name on the package.

Sample Input 2

3
sato
suzuki
takahashi
1 aoki

Sample Output 2

No

The person living in room 1 is sato, which does not match the name on the package, aoki.

Sample Input 3

2
smith
smith
1 smith

Sample Output 3

Yes

Mansion AtCoder may have people with the same name living in different rooms.

Sample Input 4

2
wang
li
2 wang

Sample Output 4

No

C - Maintain Multiple Sequences

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

配点 : 200 点

問題文

整数からなる数列が N 個あります。
i \, (1 \leq i \leq N) 番目の数列は L_i 項からなり、i 番目の数列の第 j \, (1 \leq j \leq L_i) 項は a_{i, j} です。

Q 個のクエリが与えられます。k \, (1 \leq k \leq Q) 番目のクエリでは、整数 s_k, t_k が与えられるので、s_k 番目の数列の第 t_k 項を求めてください。

制約

1 \leq N, Q \leq 2 \times 10^5
L_i \geq 1 \, (1 \leq i \leq N)
\sum_{i=1}^N L_i \leq 2 \times 10^5
1 \leq a_{i, j} \leq 10^9 \, (1 \leq i \leq N, 1 \leq j \leq L_i)
1 \leq s_k \leq N, 1 \leq t_k \leq L_{s_k} \, (1 \leq k \leq Q)
入力は全て整数

入力

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

N Q
L_1 a_{1, 1} \ldots a_{1, L_1}
\vdots
L_N a_{N, 1} \ldots a_{N, L_N}
s_1 t_1
\vdots 
s_Q t_Q

出力

Q 行出力せよ。k \, (1 \leq k \leq Q) 行目には、k 番目のクエリに対する答えを出力せよ。

入力例 1

出力例 1

7
5

1 番目の数列は (1, 4, 7)、2 番目の数列は (5, 9) です。
それぞれのクエリに対する答えは次のようになります。

1 番目の数列の第 3 項は 7 です。
2 番目の数列の第 1 項は 5 です。

入力例 2

3 4
4 128 741 239 901
2 1 1
3 314 159 26535
1 1
2 2
3 3
1 4

出力例 2

Score : 200 points

Problem Statement

There are N sequences of integers.
The i-th (1 \leq i \leq N) sequence has L_i terms; the j-th (1 \leq j \leq L_i) term of the i-th sequence is a_{i, j}.

You are given Q queries. For the k-th (1 \leq k \leq Q) query, given integers s_k and t_k, find the t_k-th term of the s_k-th sequence.

Constraints

1 \leq N, Q \leq 2 \times 10^5
L_i \geq 1 \, (1 \leq i \leq N)
\sum_{i=1}^N L_i \leq 2 \times 10^5
1 \leq a_{i, j} \leq 10^9 \, (1 \leq i \leq N, 1 \leq j \leq L_i)
1 \leq s_k \leq N, 1 \leq t_k \leq L_{s_k} \, (1 \leq k \leq Q)
All values in the input are integers.

Input

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

N Q
L_1 a_{1, 1} \ldots a_{1, L_1}
\vdots
L_N a_{N, 1} \ldots a_{N, L_N}
s_1 t_1
\vdots 
s_Q t_Q

Output

Print Q lines. The k-th (1 \leq k \leq Q) line should contain the answer to the k-th query.

Sample Input 1

Sample Output 1

7
5

The 1-st sequence is (1, 4, 7) and the 2-nd is (5, 9).
The answer to each query is as follows:

The 3-rd term of the 1-st sequence is 7.
The 1-st term of the 2-nd sequence is 5.

Sample Input 2

3 4
4 128 741 239 901
2 1 1
3 314 159 26535
1 1
2 2
3 3
1 4

Sample Output 2

D - Intersection of Cuboids

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

配点 : 250 点

問題文

あなたは3Dゲームの当たり判定を実装しようとしています。

3 次元空間内の直方体であって、2 点 (a,b,c),(d,e,f) を結ぶ線分を対角線とし、全ての面が xy 平面、yz 平面、zx 平面のいずれかに平行なものを C(a,b,c,d,e,f) と表します。
（この定義により C(a,b,c,d,e,f) は一意に定まります）

2 つの直方体 C(a,b,c,d,e,f) と C(g,h,i,j,k,l) が与えられるので、これらの共通部分の体積が正かどうか判定してください。

制約

0 \leq a < d \leq 1000
0 \leq b < e \leq 1000
0 \leq c < f \leq 1000
0 \leq g < j \leq 1000
0 \leq h < k \leq 1000
0 \leq i < l \leq 1000
入力は全て整数

入力

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

a b c d e f
g h i j k l

出力

2 つの直方体の共通部分の体積が正なら Yes、そうでなければ No を出力せよ。

入力例 1

0 0 0 4 5 6
2 3 4 5 6 7

出力例 1

Yes

2 つの直方体の位置関係は下図のようになっており、共通部分の体積は 8 です。

入力例 2

0 0 0 2 2 2
0 0 2 2 2 4

出力例 2

No

2 つの直方体は面で接していますが、共通部分の体積は 0 です。

入力例 3

0 0 0 1000 1000 1000
10 10 10 100 100 100

出力例 3

Yes

Score : 250 points

Problem Statement

You are trying to implement collision detection in a 3D game.

In a 3-dimensional space, let C(a,b,c,d,e,f) denote the cuboid with a diagonal connecting (a,b,c) and (d,e,f), and with all faces parallel to the xy-plane, yz-plane, or zx-plane.
(This definition uniquely determines C(a,b,c,d,e,f).)

Given two cuboids C(a,b,c,d,e,f) and C(g,h,i,j,k,l), determine whether their intersection has a positive volume.

Constraints

0 \leq a < d \leq 1000
0 \leq b < e \leq 1000
0 \leq c < f \leq 1000
0 \leq g < j \leq 1000
0 \leq h < k \leq 1000
0 \leq i < l \leq 1000
All input values are integers.

Input

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

a b c d e f
g h i j k l

Output

Print Yes if the intersection of the two cuboids has a positive volume, and No otherwise.

Sample Input 1

0 0 0 4 5 6
2 3 4 5 6 7

Sample Output 1

Yes

The positional relationship of the two cuboids is shown in the figure below, and their intersection has a volume of 8.

Sample Input 2

0 0 0 2 2 2
0 0 2 2 2 4

Sample Output 2

No

The two cuboids touch at a face, where the volume of the intersection is 0.

Sample Input 3

0 0 0 1000 1000 1000
10 10 10 100 100 100

Sample Output 3

Yes

E - Humidifier 3

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

配点 : 350 点

問題文

AtCoder社のオフィスは H 行 W 列のマス目で表されます。上から i 行目、左から j 列目のマスを (i, j) と表します。

各マスの状態は文字 S_{i,j} で表され、 S_{i,j} が # のときそのマスは壁、. のときそのマスは床、H のときそのマスは加湿器が置かれた床です。

あるマスは、ある加湿器から壁を通らず上下左右に D 回以下の移動で辿り着ける場合加湿されます。ここで、加湿器が置かれた床のマスは必ず加湿されていることに注意してください。

加湿されている床のマスの個数を求めてください。

制約

1 \leq H \leq 1000
1 \leq W \leq 1000
0 \leq D \leq H\times W
S_{i,j} は # または . または H である (1 \leq i \leq H, 1 \leq j \leq W)
入力される数値は全て整数

入力

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

H W D
S_{1,1}S_{1,2}\cdotsS_{1,W}
S_{2,1}S_{2,2}\cdotsS_{2,W}
\vdots
S_{H,1}S_{H,2}\cdotsS_{H,W}

出力

答えを出力せよ。

入力例 1

3 4 1
H...
#..H
.#.#

出力例 1

マス (1,1),(1,2),(1,4),(2,3),(2,4) の 5 つのマスが加湿されています。

入力例 2

5 6 2
##...H
H.....
..H.#.
.HH...
.###..

出力例 2

入力例 3

1 6 3
...#..

出力例 3

加湿されるマスが存在しない場合もあります。

Score : 350 points

Problem Statement

The AtCoder company office is represented as a grid of H rows and W columns. Let (i, j) denote the cell at the i-th row from the top and j-th column from the left.

The state of each cell is represented by a character S_{i,j}. If S_{i,j} is #, that cell has a wall; if S_{i,j} is ., that cell is a floor; if S_{i,j} is H, that cell has a humidifier placed on a floor cell.

A certain cell is considered humidified if it can be reached from at least one humidifier cell by at most D moves up, down, left, or right without passing through a wall. Note that any cell with a humidifier is always humidified.

Find the number of humidified floor cells.

Constraints

1 \leq H \leq 1000
1 \leq W \leq 1000
0 \leq D \leq H\times W
S_{i,j} is #, ., or H. (1 \leq i \leq H, 1 \leq j \leq W)
All input numbers are integers.

Input

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

H W D
S_{1,1}S_{1,2}\cdotsS_{1,W}
S_{2,1}S_{2,2}\cdotsS_{2,W}
\vdots
S_{H,1}S_{H,2}\cdotsS_{H,W}

Output

Print the answer.

Sample Input 1

3 4 1
H...
#..H
.#.#

Sample Output 1

Five cells (1,1), (1,2), (1,4), (2,3), (2,4) are humidified.

Sample Input 2

5 6 2
##...H
H.....
..H.#.
.HH...
.###..

Sample Output 2

Sample Input 3

1 6 3
...#..

Sample Output 3

It is possible that no cells are humidified.