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

A - Streamer Takahashi

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

配点 : 100 点

問題文

配信者の高橋君は L 時から R 時に配信をすることにしました。

高橋君には N 人のリスナーがおり、i 人目のリスナーは X_i 時から Y_i 時まで配信を見ることができます。

高橋君の配信を最初から最後まで見ることができるリスナーは何人いますか？

制約

1\leq N\leq 100
0\leq L\lt R\leq 23
0\leq X_i\lt Y_i\leq 23
入力は全て整数

入力

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

N L R
X_1 Y_1
X_2 Y_2
\vdots
X_N Y_N

出力

高橋君の配信を最初から最後まで見ることができるリスナーの数を出力せよ。

入力例 1

出力例 1

高橋君の配信を最初から最後まで見ることができるのは 1,3,4 人目のリスナーです。

入力例 2

出力例 2

高橋君の配信を最初から最後まで見ることができるリスナーはいません。

入力例 3

出力例 3

Score : 100 points

Problem Statement

Streamer Takahashi has decided to stream from L o'clock to R o'clock (using the 24-hour clock).

He has N listeners, and the i-th listener can watch the stream from X_i o'clock to Y_i o'clock.

How many listeners can watch Takahashi's stream from beginning to end?

Constraints

1\leq N\leq 100
0\leq L\lt R\leq 23
0\leq X_i\lt Y_i\leq 23
All input values are integers.

Input

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

N L R
X_1 Y_1
X_2 Y_2
\vdots
X_N Y_N

Output

Output the number of listeners who can watch Takahashi's stream from beginning to end.

Sample Input 1

Sample Output 1

The listeners who can watch Takahashi's stream from beginning to end are the 1st, 3rd, and 4th listeners.

Sample Input 2

Sample Output 2

No listeners can watch Takahashi's stream from beginning to end.

Sample Input 3

Sample Output 3

B - Subsegment Reverse

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

配点 : 100 点

問題文

正整数 N,L,R が与えられます。
長さ N の数列 A=(1,2,\dots,N) に対し、 L 項目から R 項目までを逆順に並べ替えるという操作を一度行いました。
操作後の数列を出力してください。

制約

入力は全て整数
1 \le L \le R \le N \le 100

入力

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

N L R

出力

操作後の数列を A'=(A'_1,A'_2,\dots,A'_N) として、以下の形式で出力せよ。

A'_1 A'_2 \dots A'_N

入力例 1

5 2 3

出力例 1

1 3 2 4 5

最初、 A=(1,2,3,4,5) です。
2 項目から 3 項目までを逆順に並べ替えた後の数列は (1,3,2,4,5) なので、これを出力してください。

入力例 2

7 1 1

出力例 2

1 2 3 4 5 6 7

L=R である場合もあります。

入力例 3

10 1 10

出力例 3

10 9 8 7 6 5 4 3 2 1

L=1 や R=N である場合もあります。

Score : 100 points

Problem Statement

You are given positive integers N, L, and R.
For a sequence A = (1, 2, \dots, N) of length N, an operation of reversing the L-th through R-th elements was performed once.
Print the sequence after this operation.

Constraints

All input values are integers.
1 \leq L \leq R \leq N \leq 100

Input

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

N L R

Output

Let A' = (A'_1, A'_2, \dots, A'_N) be the sequence after the operation. Print it in the following format:

A'_1 A'_2 \dots A'_N

Sample Input 1

5 2 3

Sample Output 1

1 3 2 4 5

Initially, A = (1, 2, 3, 4, 5).
After reversing the second through third elements, the sequence becomes (1, 3, 2, 4, 5), which should be printed.

Sample Input 2

7 1 1

Sample Output 2

1 2 3 4 5 6 7

It is possible that L = R.

Sample Input 3

10 1 10

Sample Output 3

10 9 8 7 6 5 4 3 2 1

It is possible that L = 1 or R = N.

C - Seek Grid

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

配点 : 200 点

問題文

N \times N のグリッド S と M\times M のグリッド T が与えられます。上から i 行目、左から j 列目のマス目をマス (i,j) と表します。

S,T の各マスの色はそれぞれ N^2個の文字 S_{i,j} \; (1\leq i,j\leq N) および M^2 個の文字 T_{i,j} \; (1\leq i,j\leq M) によって表されます。 S_{i,j} が . のとき S のマス (i,j) は白色、S_{i,j} が # のとき S のマス (i,j) は黒色で塗られています。T についても同様です。

S の中から T を探してください。具体的には、以下の条件を満たす a,b \; (1 \leq a,b \leq N-M+1) を出力してください。

すべての i,j \; (1\leq i,j \leq M) について、S_{a+i-1,b+j-1} = T_{i,j}

制約

1 \leq M \leq N \leq 50
N,M は整数
S_{i,j},T_{i,j} は . または #
条件を満たす a,b はちょうど 1 組存在する。

入力

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

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

出力

a,b をこの順に空白区切りで 1 行に出力せよ。

入力例 1

3 2
#.#
..#
##.
.#
#.

出力例 1

2 2

S の 2 行目から 3 行目、2 列目から 3 列目の 2 \times 2 マスが T と一致します。

入力例 2

2 1
#.
##
.

出力例 2

1 2

Score : 200 points

Problem Statement

You are given an N \times N grid S and an M \times M grid T. The cell at the i-th row from the top and the j-th column from the left is denoted by (i,j).

The colors of the cells in S and T are represented by N^2 characters S_{i,j} (1\leq i,j\leq N) and M^2 characters T_{i,j} (1\leq i,j\leq M), respectively. In grid S, cell (i,j) is white if S_{i,j} is ., and black if S_{i,j} is #. The same applies for grid T.

Find T within S. More precisely, output integers a and b (1 \leq a,b \leq N-M+1) that satisfy the following condition:

S_{a+i-1,b+j-1} = T_{i,j} for every i,j (1\leq i,j \leq M).

Constraints

1 \leq M \leq N \leq 50
N and M are integers.
Each of S_{i,j} and T_{i,j} is . or #.
There is exactly one pair (a,b) satisfying the condition.

Input

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

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

Output

Print a and b in this order, separated by a space on one line.

Sample Input 1

3 2
#.#
..#
##.
.#
#.

Sample Output 1

2 2

The 2 \times 2 subgrid of S from the 2nd to the 3rd row and from the 2nd to the 3rd column matches T.

Sample Input 2

2 1
#.
##
.

Sample Output 2

1 2

D - The Middle Day

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

配点 : 200 点

問題文

AtCoder 国の暦では、一年は 1,2,\dots,M 番目の月の M か月からなり、そのうち i 番目の月は 1,2,\dots,D_i 番目の日の D_i 日からなります。
さらに、 AtCoder 国の一年の日数は奇数、即ち D_1+D_2+\dots+D_M は奇数です。
一年の真ん中の日は何番目の月の何番目の日か求めてください。
言い換えると、 1 番目の月の 1 番目の日を 1 日目としたときの (D_1+D_2+\dots+D_M+1)/2 日目が何番目の月の何番目の日かを求めてください。

制約

入力は全て整数
1 \le M \le 100
1 \le D_i \le 100
D_1 + D_2 + \dots + D_M は奇数

入力

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

M
D_1 D_2 \dots D_M

出力

答えが a 番目の月の b 番目の日であるとき、以下の形式で出力せよ。

a b

入力例 1

12
31 28 31 30 31 30 31 31 30 31 30 31

出力例 1

7 2

この入力では、 1 年は 31+28+31+30+31+30+31+31+30+31+30+31=365 日からなります。
真ん中の日は (365+1)/2 = 183 日目であり、これを求めることを考えます。

1,2,3,4,5,6 番目の月に含まれる日数の合計は 181 日です。
7 番目の月の 1 番目の日は 182 日目です。
7 番目の月の 2 番目の日は 183 日目です。

以上から、答えが 7 番目の月の 2 番目の日であることが分かります。

入力例 2

1
1

出力例 2

1 1

入力例 3

6
3 1 4 1 5 9

出力例 3

5 3

Score : 200 points

Problem Statement

In the calendar of AtCoderLand, a year consists of M months: month 1, month 2, \dots, month M. The i-th month consists of D_i days: day 1, day 2, \dots, day D_i.
Furthermore, the number of days in a year is odd, that is, D_1+D_2+\dots+D_M is odd.
Find what day of what month is the middle day of the year.
In other words, let day 1 of month 1 be the first day, and find a and b such that the ((D_1+D_2+\dots+D_M+1)/2)-th day is day b of month a.

Constraints

All input values are integers.
1 \le M \le 100
1 \le D_i \le 100
D_1 + D_2 + \dots + D_M is odd.

Input

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

M
D_1 D_2 \dots D_M

Output

Let the answer be day b of month a, and print it in the following format:

a b

Sample Input 1

12
31 28 31 30 31 30 31 31 30 31 30 31

Sample Output 1

7 2

In this input, a year consists of 31+28+31+30+31+30+31+31+30+31+30+31=365 days.
Let us find the middle day, which is the ((365+1)/2 = 183)-th day.

Months 1,2,3,4,5,6 contain a total of 181 days.
Day 1 of month 7 is the 182-th day.
Day 2 of month 7 is the 183-th day.

Thus, the answer is day 2 of month 7.

Sample Input 2

1
1

Sample Output 2

1 1

Sample Input 3

6
3 1 4 1 5 9

Sample Output 3

5 3

E - Mixture

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

配点 : 350 点

問題文

N 種類の薬品 1,2,\dots,N があります。あなたの目標はこれらが全て混ざった状態にすることです。
0, 1 からなる長さ 2^N-1 の文字列 S が与えられます。この文字列は次の情報を表します。

まず、 1 種類以上の薬品が混ざった状態 i ( 1 \le i \le 2^N-1 ) を次のように定義する。
- i を 2 進法で表記した際に下から k ( 1 \le k \le N ) 桁目が 1 である、またその時に限り、薬品 k が含まれている。
- 例えば、 13 を 2 進法で表記すると 1101_{(2)} となるため、状態 13 は薬品 1,3,4 が混ざった状態を表現します。
S の i 文字目が 0 であるとき、状態 i は安全である。
S の i 文字目が 1 であるとき、状態 i は危険である。

あなたは次の操作を使って薬品を混ぜ合わせます。

まず、空の瓶を用意する。
次に、以下を繰り返す。
- まだ瓶に注いでいない薬品を 1 種類選択し、瓶に注ぐ。
- この時、瓶の中で混ざった薬品が危険な状態であってはならない。

この操作によって全ての薬品が混ざった状態を作れるか判定してください。

T 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

T は 1 以上 40000 以下の整数
N は 1 以上 18 以下の整数
S は 0, 1 からなる長さ 2^N-1 の文字列
ひとつの入力に含まれる |S| = 2^N-1 の総和は 5 \times 10^5 を超えない

入力

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

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

\mathrm{case}_i は i 番目のテストケースを表す。各テストケースは以下の形式で与えられる。

N
S

出力

T 行出力せよ。i 行目には i 番目のテストケースに対する答えを出力せよ。
各テストケースについて、全ての薬品が混ざった状態を作れるなら Yes 、作れないなら No と出力せよ。

入力例 1

5
3
0010000
3
0010110
1
1
2
100
4
001110010101110

出力例 1

Yes
No
No
Yes
Yes

この入力には 5 個のテストケースが含まれます。

1 番目のケースは次の通りです。

3 種類の薬品が存在する。
薬品 1,2 が混ざった状態 3 のみが危険で、他の状態は安全である。
例えば、以下の手順で全ての薬品が混ざった状態を作ることができます。
- はじめに、瓶に薬品 2 を注ぐ。瓶の中で薬品 2 のみが混ざっており、これは状態 2 なので安全である。
- 次に、瓶に薬品 3 を注ぐ。瓶の中で薬品 2,3 が混ざっており、これは状態 6 なので安全である。
- 最後に、瓶に薬品 1 を注ぐ。瓶の中で薬品 1,2,3 が混ざっており、これは状態 7 なので安全である。

2 番目のケースは次の通りです。

3 種類の薬品が存在する。
薬品 1,2 が混ざった状態 3 、薬品 1,3 が混ざった状態 5 、薬品 2,3 が混ざった状態 6 が危険で、他の状態は安全である。
このケースについて、全ての薬品が混ざった状態を作ることはできません。

3 番目のケースは次の通りです。

1 種類の薬品が存在する。
薬品 1 のみが混ざった状態 1 が危険であるため、全ての薬品が混ざった状態を作ることはできません。

Score : 350 points

Problem Statement

There are N types of chemicals 1,2,\dots,N. Your goal is to create a state where all of them are mixed.
You are given a string S of length 2^N-1 consisting of 0 and 1, which represents the following information:

First, define state i (1 \le i \le 2^N-1) where one or more types of chemicals are mixed as follows:
- When the k-th digit (1 \le k \le N) from the bottom in the binary representation of i is 1, and only then, chemical k is included.
- For example, 13 in binary is 1101_{(2)}, so state 13 represents a state where chemicals 1,3,4 are mixed.
When the i-th character of S is 0, state i is safe.
When the i-th character of S is 1, state i is dangerous.

You mix chemicals using the following operation:

First, prepare an empty bottle.
Next, repeat the following:
- Choose one type of chemical that has not yet been poured into the bottle and pour it into the bottle.
- At this time, the chemicals mixed in the bottle must not be in a dangerous state.

Determine whether this operation can create a state where all chemicals are mixed.

You are given T test cases; solve each of them.

Constraints

T is an integer between 1 and 40000, inclusive.
N is an integer between 1 and 18, inclusive.
S is a string of length 2^N-1 consisting of 0 and 1.
The sum of |S| = 2^N-1 in each input does not exceed 5 \times 10^5.

Input

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

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

\mathrm{case}_i represents the i-th test case. Each test case is given in the following format:

N
S

Output

Output T lines. The i-th line should contain the answer for the i-th test case.
For each test case, if it is possible to create a state where all chemicals are mixed, print Yes; otherwise, print No.

Sample Input 1

5
3
0010000
3
0010110
1
1
2
100
4
001110010101110

Sample Output 1

Yes
No
No
Yes
Yes

This input contains five test cases.

The 1st case is as follows:

There are three types of chemicals.
Only state 3 where chemicals 1,2 are mixed is dangerous, and the other states are safe.
For example, you can create a state where all chemicals are mixed with the following procedure:
- First, pour chemical 2 into the bottle. Only chemical 2 is mixed in the bottle, which is state 2, so it is safe.
- Next, pour chemical 3 into the bottle. Chemicals 2,3 are mixed in the bottle, which is state 6, so it is safe.
- Finally, pour chemical 1 into the bottle. Chemicals 1,2,3 are mixed in the bottle, which is state 7, so it is safe.

The 2nd case is as follows:

There are three types of chemicals.
State 3 where chemicals 1,2 are mixed, state 5 where chemicals 1,3 are mixed, and state 6 where chemicals 2,3 are mixed are dangerous, and the other states are safe.
For this case, it is impossible to create a state where all chemicals are mixed.

The 3rd case is as follows:

There is one type of chemical.
Since state 1 where only chemical 1 is mixed is dangerous, it is impossible to create a state where all chemicals are mixed.