AtCoder Daily Training EASY 2026/10/21 18:00start

A - Edge Checker 2

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

下の画像で示す図において、a 番の点と b 番の点が線で直接結ばれているかを答えてください。

制約

1 \leq a \lt b \leq 15
a,b は整数

入力

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

a b

出力

a 番の点と b 番の点が線で直接結ばれているなら Yes、結ばれていないなら No を出力せよ。

入力例 1

1 2

出力例 1

Yes

問題文で示した図において、1 番の点と 2 番の点は線で直接結ばれています。よって、Yes を出力します。

入力例 2

2 8

出力例 2

No

問題文で示した図において、2 番の点と 8 番の点は線で直接結ばれていません。よって、No を出力します。

入力例 3

14 15

出力例 3

No

Score : 100 points

Problem Statement

Determine if there is a segment that directly connects the points numbered a and b in the figure below.

Constraints

1 \leq a \lt b \leq 15
a and b are integers.

Input

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

a b

Output

Print Yes if there is a segment that directly connects the points numbered a and b; print No otherwise.

Sample Input 1

1 2

Sample Output 1

Yes

In the figure in the Problem Statement, there is a segment that directly connects the points numbered 1 and 2, so Yes should be printed.

Sample Input 2

2 8

Sample Output 2

No

In the figure in the Problem Statement, there is no segment that directly connects the points numbered 2 and 8, so No should be printed.

Sample Input 3

14 15

Sample Output 3

No

B - A Unique Letter

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

長さ 3 の文字列 S が与えられます。
S に 1 度だけ含まれる文字を 1 つ出力してください。
但し、そのような文字が存在しない場合は代わりに -1 と出力してください。

制約

S は英小文字のみからなる 3 文字の文字列

入力

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

出力

答えを出力せよ。正解が複数ある場合、どれを出力してもよい。

入力例 1

pop

出力例 1

pop に o は 1 度だけ含まれます。

入力例 2

abc

出力例 2

abc に a, b, c はどれも 1 度だけ含まれるので、どれを出力しても構いません。

入力例 3

xxx

出力例 3

-1

xxx に 1 度だけ含まれる文字はありません。

Score : 100 points

Problem Statement

You are given a string S of length 3.
Print a character that occurs only once in S.
If there is no such character, print -1 instead.

Constraints

S is a string of length 3 consisting of lowercase English letters.

Input

Input is given from Standard Input in the following format:

Output

Print the answer. If multiple solutions exist, you may print any of them.

Sample Input 1

pop

Sample Output 1

o occurs only once in pop.

Sample Input 2

abc

Sample Output 2

a, b, and c occur once each in abc, so you may print any of them.

Sample Input 3

xxx

Sample Output 3

-1

No character occurs only once in xxx.

C - Distance Table

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

N 個の駅、駅 1, 駅 2, \ldots, 駅 N が直線上にこの順に並んでいます。
ここで、1\leq i\leq N-1 について、駅 i と駅 (i+1) の間の距離は D_i です。

1\leq i<j\leq N をみたす整数の組 (i,j) それぞれについて、駅 i と駅 j の間の距離を求めてください。
なお、出力形式については出力の欄を参照してください。

制約

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

入力

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

N
D_1 D_2 \ldots D_{N-1}

出力

N-1 行出力せよ。
i 行目 (1\leq i\leq N-1) には、(N-i) 個の整数を空白区切りで出力せよ。
i 行目の j 番目 (1\leq j\leq N-i) には、駅 i と駅 (i+j) の間の距離を出力せよ。

入力例 1

5
5 10 2 3

出力例 1

各駅の間の距離は次のようになります。

駅 1 と駅 2 の間の距離は 5 です。
駅 1 と駅 3 の間の距離は 5+10=15 です。
駅 1 と駅 4 の間の距離は 5+10+2=17 です。
駅 1 と駅 5 の間の距離は 5+10+2+3=20 です。
駅 2 と駅 3 の間の距離は 10 です。
駅 2 と駅 4 の間の距離は 10+2=12 です。
駅 2 と駅 5 の間の距離は 10+2+3=15 です。
駅 3 と駅 4 の間の距離は 2 です。
駅 3 と駅 5 の間の距離は 2+3=5 です。
駅 4 と駅 5 の間の距離は 3 です。

よって、上記のように出力します。

入力例 2

2
100

出力例 2

Score : 200 points

Problem Statement

There are N stations, station 1, station 2, \ldots, station N, arranged in this order on a straight line.
Here, for 1\leq i\leq N-1, the distance between stations i and (i+1) is D_i.

For each pair of integers (i,j) satisfying 1\leq i<j\leq N, find the distance between stations i and j.
For the output format, refer to the Output section.

Constraints

2 \leq N \leq 50
1 \leq D_i \leq 100
All input values are integers.

Input

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

N
D_1 D_2 \ldots D_{N-1}

Output

Output N-1 lines.
On the i-th line (1\leq i\leq N-1), output (N-i) integers, separated by spaces.
The j-th integer on the i-th line (1\leq j\leq N-i) should be the distance between stations i and (i+j).

Sample Input 1

5
5 10 2 3

Sample Output 1

The distances between stations are as follows:

The distance between stations 1 and 2 is 5.
The distance between stations 1 and 3 is 5+10=15.
The distance between stations 1 and 4 is 5+10+2=17.
The distance between stations 1 and 5 is 5+10+2+3=20.
The distance between stations 2 and 3 is 10.
The distance between stations 2 and 4 is 10+2=12.
The distance between stations 2 and 5 is 10+2+3=15.
The distance between stations 3 and 4 is 2.
The distance between stations 3 and 5 is 2+3=5.
The distance between stations 4 and 5 is 3.

Thus, output as shown above.

Sample Input 2

2
100

Sample Output 2

D - Product Calculator

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

高橋君は電卓を持っています。電卓には最初 1 が表示されています。
高橋君は電卓に対して N 回操作を行います。
i 回目 (1\leq i\leq N) の操作では、その時点で画面に表示されている数に正の整数 A_i をかけます。
しかし、電卓には K 桁までしか表示できないため、計算結果が (K+1) 桁以上になる場合、代わりに 1 が画面に表示されます。そうでない場合は正しく計算結果が表示されます。

N 回の操作の後に電卓に表示されている数を求めてください。

制約

1 \leq N \leq 100
1 \leq K \leq 18
1 \leq A_i < 10^K
入力はすべて整数

入力

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

N K
A_1 A_2 \ldots A_N

出力

N 回の操作の後に電卓に表示されている数を出力せよ。

入力例 1

5 2
7 13 3 2 5

出力例 1

今回電卓は 2 桁まで表示することができ、最初 1 が表示されています。これに対して、次のように高橋君は操作を行います。

1 回目の操作で、7 をかけます。1\times 7=7 であり、電卓には 7 が表示されます。
2 回目の操作で、13 をかけます。7\times 13=91 であり、電卓には 91 が表示されます。
3 回目の操作で、3 をかけます。91\times 3=273 であり、3 桁になってしまうため、電卓には 1 が表示されます。
4 回目の操作で、2 をかけます。1\times 2=2 であり、電卓には 2 が表示されます。
5 回目の操作で、5 をかけます。2\times 5=10 であり、電卓には 10 が表示されます。

入力例 2

2 1
2 5

出力例 2

Score : 200 points

Problem Statement

Takahashi has a calculator that initially displays 1.
He will perform N operations on the calculator.
In the i-th operation (1 \leq i \leq N), he multiplies the currently displayed number by a positive integer A_i.
However, the calculator can display at most K digits. If the result of the multiplication has (K+1) or more digits, the display shows 1 instead; otherwise, the result is shown correctly.

Find the number showing on the calculator after the N operations.

Constraints

1 \leq N \leq 100
1 \leq K \leq 18
1 \leq A_i < 10^K
All input values are integers.

Input

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

N K
A_1 A_2 \ldots A_N

Output

Output the number shown on the calculator after the N operations.

Sample Input 1

5 2
7 13 3 2 5

Sample Output 1

This calculator can display at most two digits and initially shows 1. Takahashi operates as follows:

The 1st operation multiplies by 7. Since 1 \times 7 = 7, the calculator shows 7.
The 2nd operation multiplies by 13. Since 7 \times 13 = 91, the calculator shows 91.
The 3rd operation multiplies by 3. Since 91\times 3=273, which has three digits, the calculator shows 1.
The 4th operation multiplies by 2. Since 1\times 2=2, the calculator shows 2.
The 5th operation multiplies by 5. Since 2\times 5=10, the calculator shows 10.

Sample Input 2

2 1
2 5

Sample Output 2

E - Keys

Time Limit: 2 sec / Memory Limit: 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