AtCoder Daily Training EASY 2026/07/14 18:00start

A - Double Click

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

配点 : 100 点

問題文

高橋君は、時刻 0 にパソコンの電源をつけ、それからマウスを N 回クリックしました。i(1 \le i \le N) 回目のクリックは時刻 T_i に行われました。

高橋君が時刻 x_1 と時刻 x_2 (ただし x_1 < x_2)にマウスを連続してクリックしたとき、x_2 - x_1 \le D であれば時刻 x_2 にダブルクリックが成立したと言います。

高橋君が最初にダブルクリックを成立させた時刻を求めてください。ただし、高橋君が 1 回もダブルクリックを成立させていないならば -1 を出力してください。

制約

1 \le N \le 100
1 \le D \le 10^9
1 \le T_i \le 10^9(1 \le i \le N)
T_i < T_{i+1}(1 \le i \le N-1)
入力はすべて整数

入力

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

N D
T_1 T_2 \dots T_N

出力

高橋君が 1 回でもダブルクリックを成立させたならば最初にダブルクリックが成立した時刻を、そうでないならば -1 を出力せよ。

入力例 1

4 500
300 900 1300 1700

出力例 1

高橋君は時刻 900,1300 にマウスをクリックしていて、1300 - 900 \le 500 であるため時刻 1300 にダブルクリックが成立しています。

時刻 1300 より前にダブルクリックは成立していないため、1300 を出力してください。

入力例 2

5 99
100 200 300 400 500

出力例 2

-1

高橋君は 1 回もダブルクリックを成立させていません。よって、-1 を出力してください。

入力例 3

4 500
100 600 1100 1600

出力例 3

高橋君が複数回ダブルクリックを成立させていても、そのうち最初の時刻のみを出力することに注意してください。

Score : 100 points

Problem Statement

Takahashi turned on a computer at time 0 and clicked the mouse N times. The i-th (1 \le i \le N) click was at time T_i.

If he consecutively clicked the mouse at time x_1 and time x_2 (where x_1 < x_2), a double click is said to be fired at time x_2 if and only if x_2 - x_1 \le D.

What time was a double click fired for the first time? If no double click was fired, print -1 instead.

Constraints

1 \le N \le 100
1 \le D \le 10^9
1 \le T_i \le 10^9(1 \le i \le N)
T_i < T_{i+1}(1 \le i \le N-1)
All values in the input are integers.

Input

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

N D
T_1 T_2 \dots T_N

Output

If at least one double click was fired, print the time of the first such event; otherwise, print -1.

Sample Input 1

4 500
300 900 1300 1700

Sample Output 1

Takahashi clicked the mouse at time 900 and 1300. Since 1300 - 900 \le 500, a double click was fired at time 1300.

A double click had not been fired before time 1300, so 1300 should be printed.

Sample Input 2

5 99
100 200 300 400 500

Sample Output 2

-1

No double click was fired, so print -1.

Sample Input 3

4 500
100 600 1100 1600

Sample Output 3

If multiple double clicks were fired, be sure to print only the first such event.

B - Jogging

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

配点 : 100 点

問題文

高橋君と青木君はジョギングをすることにしました。
高橋君は「A 秒間秒速 B メートルで歩き、C 秒間休む」ことを繰り返します。
青木君は「D 秒間秒速 E メートルで歩き、F 秒間休む」ことを繰り返します。
二人が同時にジョギングを始めてから X 秒後、高橋君と青木君のうちどちらが長い距離を進んでいますか？

制約

1 \leq A, B, C, D, E, F, X \leq 100
入力は全て整数

入力

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

A B C D E F X

出力

二人が同時にジョギングを始めてから X 秒後時点で、高橋君の方が青木君よりも長い距離を進んでいるならば Takahashi、青木君の方が高橋君よりも長い距離を進んでいるならば Aoki、二人が同じ距離を進んでいるならば Draw と出力せよ。

入力例 1

4 3 3 6 2 5 10

出力例 1

Takahashi

二人はジョギングを始めてから 10 秒間の間、以下のように行動します。

高橋君は 4 秒間歩き、3 秒間休んだ後、再び 3 秒間歩く。合計 (4 + 3) \times 3 = 21 メートル歩く。
青木君は 6 秒間歩き、4 秒間休む。合計 6 \times 2 = 12 メートル歩く。

高橋君の方が長い距離を進んでいるので、Takahashi と出力します。

入力例 2

3 1 4 1 5 9 2

出力例 2

Aoki

入力例 3

1 1 1 1 1 1 1

出力例 3

Draw

Score : 100 points

Problem Statement

Takahashi and Aoki decided to jog.
Takahashi repeats the following: "walk at B meters a second for A seconds and take a rest for C seconds."
Aoki repeats the following: "walk at E meters a second for D seconds and take a rest for F seconds."
When X seconds have passed since they simultaneously started to jog, which of Takahashi and Aoki goes ahead?

Constraints

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

Input

Input is given from Standard Input in the following format:

A B C D E F X

Output

When X seconds have passed since they simultaneously started to jog, if Takahashi goes ahead of Aoki, print Takahashi; if Aoki goes ahead of Takahashi, print Aoki; if they have advanced the same distance, print Draw.

Sample Input 1

4 3 3 6 2 5 10

Sample Output 1

Takahashi

During the first 10 seconds after they started to jog, they move as follows.

Takahashi walks for 4 seconds, takes a rest for 3 seconds, and walks again for 3 seconds. As a result, he advances a total of (4 + 3) \times 3 = 21 meters.
Aoki walks for 6 seconds and takes a rest for 4 seconds. As a result, he advances a total of 6 \times 2 = 12 meters.

Since Takahashi goes ahead, Takahashi should be printed.

Sample Input 2

3 1 4 1 5 9 2

Sample Output 2

Aoki

Sample Input 3

1 1 1 1 1 1 1

Sample Output 3

Draw

C - Make Target

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

配点 : 200 点

問題文

概要：以下のような N\times N の模様を作成してください。
###########
#.........#
#.#######.#
#.#.....#.#
#.#.###.#.#
#.#.#.#.#.#
#.#.###.#.#
#.#.....#.#
#.#######.#
#.........#
###########

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

N\times N のグリッドがあります。このグリッドの上から i 行目、左から j 列目のマスをマス (i,j) と表します。はじめ、どのマスにも色は塗られていません。

これから、i=1,2,\dots,N の順に、以下の操作を行います。

j=N+1-i とする。
i\leq j であるならば、i が奇数ならば黒、偶数ならば白で、マス (i,i) を左上、マス (j,j) を右下とする矩形領域に含まれるマスを塗りつぶす。このとき、既に色が塗られているマスについては色を上書きする。
i\gt j であるならば、何もしない。

すべての操作を行った後、色が塗られていないマスが存在しないことが証明できます。最終的に各マスがどの色で塗られているかを求めてください。

制約

1\leq N\leq 50
入力はすべて整数

入力

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

出力

N 行出力せよ。i 行目には、最終的にグリッドの i 行目に塗られている色を以下のような長さ N の文字列 S_i として出力せよ。入出力例も参考にすること。

マス (i,j) が最終的に黒で塗られているならば、S_i の j 文字目は # である。
マス (i,j) が最終的に白で塗られているならば、S_i の j 文字目は . である。

入力例 1

出力例 1

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

概要で示した模様と同じです。

入力例 2

出力例 2

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

以下のように色が塗られます。ここで、まだ色が塗られていないマスを ? と表します。

         i=1      i=2      i=3      i=4      i=5
?????    #####    #####    #####    #####    #####
?????    #####    #...#    #...#    #...#    #...#
????? -> ##### -> #...# -> #.#.# -> #.#.# -> #.#.#
?????    #####    #...#    #...#    #...#    #...#
?????    #####    #####    #####    #####    #####

入力例 3

出力例 3

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

入力例 4

出力例 4

##
##

Score : 200 points

Problem Statement

Overview: Create an N \times N pattern as follows.

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

You are given a positive integer N.

Consider an N \times N grid. Let (i,j) denote the cell at the i-th row from the top and the j-th column from the left. Initially, no cell is colored.

Then, for i = 1,2,\dots,N in order, perform the following operation:

Let j = N + 1 - i.
If i \leq j, fill the rectangular region whose top-left cell is (i,i) and bottom-right cell is (j,j) with black if i is odd, or white if i is even. If some cells are already colored, overwrite their colors.
If i > j, do nothing.

After all these operations, it can be proved that there are no uncolored cells. Determine the final color of each cell.

Constraints

1 \leq N \leq 50
All input values are integers.

Input

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

Output

Print N lines. The i-th line should contain a length-N string S_i representing the colors of the i-th row of the grid after all operations, as follows:

If cell (i,j) is finally colored black, the j-th character of S_i should be #.
If cell (i,j) is finally colored white, the j-th character of S_i should be ..

Sample Input 1

Sample Output 1

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

This matches the pattern shown in the Overview.

Sample Input 2

Sample Output 2

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

Colors are applied as follows, where ? denotes a cell not yet colored:

         i=1      i=2      i=3      i=4      i=5
?????    #####    #####    #####    #####    #####
?????    #####    #...#    #...#    #...#    #...#
????? -> ##### -> #...# -> #.#.# -> #.#.# -> #.#.#
?????    #####    #...#    #...#    #...#    #...#
?????    #####    #####    #####    #####    #####

Sample Input 3

Sample Output 3

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

Sample Input 4

Sample Output 4

##
##

D - Number Box

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

配点 : 200 点

問題文

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

N 行 N 列のマス目があり、上から i 行目、左から j 列目のマスには数字 A_{i,j} が書かれています。

このマス目は上下および左右がつながっているものとします。つまり以下が全て成り立ちます。

(1,i) の上のマスは (N,i) であり、(N,i) の下のマスは (1,i) である。(1\le i\le N)
(i,1) の左のマスは (i,N) であり、(i,N) の右のマスは (i,1) である。(1\le i\le N)

高橋君は、上下左右および斜めの 8 方向のうちいずれかを初めに選びます。そして、好きなマスから決めた方向に 1 マス移動することを N-1 回繰り返します。

高橋君は N 個のマス上を移動することになりますが、高橋君が通ったマスに書かれている数字を左から通った順番に並べた整数としてあり得る最大のものを求めてください。

制約

1 \le N \le 10
1 \le A_{i,j} \le 9
入力はすべて整数。

入力

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

N
A_{1,1}A_{1,2}\dots A_{1,N}
A_{2,1}A_{2,2}\dots A_{2,N}
\vdots
A_{N,1}A_{N,2}\dots A_{N,N}

出力

答えを出力せよ。

入力例 1

出力例 1

高橋君が上から 2 行目、左から 4 列目のマスから出発し、右下に進むことで、通ったマスに書かれた数字を並べ 9786 を作ることができます。 9786 より大きい値を作ることはできないため、9786 が解です。

入力例 2

出力例 2

1111111111

32bit整数型に答えが収まるとは限らないことに注意してください。

Score : 200 points

Problem Statement

You are given a positive integer N.

We have a grid with N rows and N columns, where the square at the i-th row from the top and j-th column from the left has a digit A_{i,j} written on it.

Assume that the upper and lower edges of this grid are connected, as well as the left and right edges. In other words, all of the following holds.

(N,i) is just above (1,i), and (1,i) is just below (N,i). (1\le i\le N).
(i,N) is just to the left of (i,1), and (i,1) is just to the right of (i,N). (1\le i\le N).

Takahashi will first choose one of the following eight directions: up, down, left, right, and the four diagonal directions. Then, he will start on a square of his choice and repeat moving one square in the chosen direction N-1 times.

In this process, Takahashi visits N squares. Find the greatest possible value of the integer that is obtained by arranging the digits written on the squares visited by Takahashi from left to right in the order visited by him.

Constraints

1 \le N \le 10
1 \le A_{i,j} \le 9
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_{1,1}A_{1,2}\dots A_{1,N}
A_{2,1}A_{2,2}\dots A_{2,N}
\vdots
A_{N,1}A_{N,2}\dots A_{N,N}

Output

Print the answer.

Sample Input 1

Sample Output 1

If Takahashi starts on the square at the 2-nd row from the top and 4-th column from the left and goes down and to the right, the integer obtained by arranging the digits written on the visited squares will be 9786. It is impossible to make a value greater than 9786, so the answer is 9786.

Sample Input 2

Sample Output 2

1111111111

Note that the answer may not fit into a 32-bit integer.

E - Keys

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

配点 : 300 点

問題文

あなたは N 本の鍵 1,2,\dots,N を持っています。
このうち何本かの鍵は正しい鍵で、それ以外はダミーの鍵です。

また、鍵を何本でも挿し込めるドアX があり、このドアX は正しい鍵を K 本以上挿し込んだ時、またその時に限って開きます。

あなたはこれらの鍵に対して M 回のテストを行いました。このうち i 回目のテストの内容は次の通りです。

C_i 本の鍵 A_{i,1},A_{i,2},\dots,A_{i,C_i} をドアX に挿し込む。
テスト結果はひとつの英文字 R_i で表現される。
- R_i = o のとき i 回目のテストでドアが開いたことを表す。
- R_i = x のとき i 回目のテストでドアが開かなかったことを表す。

各鍵が正しいかダミーかの組み合わせは 2^N 通り考えられますが、このうちどのテスト結果にも矛盾しない組み合わせの個数を求めてください。
ただし、与えられるテスト結果が誤っており上記の条件を満たす組み合わせが存在しない場合もあります。その場合は 0 通りと解答してください。

制約

N,M,K,C_i,A_{i,j} は整数
1 \le K \le N \le 15
1 \le M \le 100
1 \le C_i \le N
1 \le A_{i,j} \le N
j \neq k ならば A_{i,j} \neq A_{i,k}
R_i は o または x

入力

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

N M K
C_1 A_{1,1} A_{1,2} \dots A_{1,C_1} R_1
C_2 A_{2,1} A_{2,2} \dots A_{2,C_2} R_2
\vdots
C_M A_{M,1} A_{M,2} \dots A_{M,C_M} R_M

出力

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

入力例 1

3 2 2
3 1 2 3 o
2 2 3 x

出力例 1

この入力では鍵が 3 本あり、テストは 2 回行われました。
また、ドアX を開くのに必要な正しい鍵の本数は 2 本です。

1 回目のテストでは鍵 1,2,3 を使い、その結果ドアX は開きました。
2 回目のテストでは鍵 2,3 を使い、その結果ドアX は開きませんした。

各鍵が正しいかダミーかの組み合わせであって、どのテスト結果にも矛盾しないものは以下の 2 通りです。

鍵 1 は本物、鍵 2 はダミー、鍵 3 は本物である。
鍵 1 は本物、鍵 2 は本物、鍵 3 はダミーである。

入力例 2

4 5 3
3 1 2 3 o
3 2 3 4 o
3 3 4 1 o
3 4 1 2 o
4 1 2 3 4 x

出力例 2

問題文中でも述べた通り、答えが 0 通りである場合もあります。

入力例 3

11 4 9
10 1 2 3 4 5 6 7 8 9 10 o
11 1 2 3 4 5 6 7 8 9 10 11 o
10 11 10 9 8 7 6 5 4 3 2 x
10 11 9 1 4 3 7 5 6 2 10 x

出力例 3

Score : 300 points

Problem Statement

You have N keys numbered 1, 2, \dots, N.
Some of these are real keys, while the others are dummies.

There is a door, Door X, into which you can insert any number of keys. Door X will open if and only if at least K real keys are inserted.

You have conducted M tests on these keys. The i-th test went as follows:

You inserted C_i keys A_{i,1}, A_{i,2}, \dots, A_{i,C_i} into Door X.
The test result is represented by a single English letter R_i.
- R_i = o means that Door X opened in the i-th test.
- R_i = x means that Door X did not open in the i-th test.

There are 2^N possible combinations of which keys are real and which are dummies. Among these, find the number of combinations that do not contradict any of the test results.
It is possible that the given test results are incorrect and no combination satisfies the conditions. In such a case, report 0.

Constraints

N, M, K, C_i, and A_{i,j} are integers.
1 \le K \le N \le 15
1 \le M \le 100
1 \le C_i \le N
1 \le A_{i,j} \le N
A_{i,j} \neq A_{i,k} if j \neq k.
R_i is o or x.

Input

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

N M K
C_1 A_{1,1} A_{1,2} \dots A_{1,C_1} R_1
C_2 A_{2,1} A_{2,2} \dots A_{2,C_2} R_2
\vdots
C_M A_{M,1} A_{M,2} \dots A_{M,C_M} R_M

Output

Print the answer as an integer.

Sample Input 1

3 2 2
3 1 2 3 o
2 2 3 x

Sample Output 1

In this input, there are three keys and two tests were conducted.
Two correct keys are required to open Door X.

In the first test, keys 1, 2, 3 were used, and Door X opened.
In the second test, keys 2, 3 were used, and Door X did not open.

There are two combinations of which keys are real and which are dummies that do not contradict any of the test results:

Key 1 is real, key 2 is a dummy, and key 3 is real.
Key 1 is real, key 2 is real, and key 3 is a dummy.

Sample Input 2

4 5 3
3 1 2 3 o
3 2 3 4 o
3 3 4 1 o
3 4 1 2 o
4 1 2 3 4 x

Sample Output 2

As mentioned in the problem statement, the answer may be 0.

Sample Input 3

11 4 9
10 1 2 3 4 5 6 7 8 9 10 o
11 1 2 3 4 5 6 7 8 9 10 11 o
10 11 10 9 8 7 6 5 4 3 2 x
10 11 9 1 4 3 7 5 6 2 10 x