Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 100 点
問題文
1 以上 9 以下の整数 N が入力として与えられます。
数字 N を N 個繋げて得られる文字列を出力してください。
制約
- N は 1 以上 9 以下の整数
入力
入力は以下の形式で標準入力から与えられる。
N
出力
答えを出力せよ。
入力例 1
3
出力例 1
333
3 を 3 個繋げて得られる文字列は 333 です。
入力例 2
9
出力例 2
999999999
Score : 100 points
Problem Statement
You are given an integer N between 1 and 9, inclusive, as input.
Concatenate N copies of the digit N and print the resulting string.
Constraints
- N is an integer between 1 and 9, inclusive.
Input
The input is given from Standard Input in the following format:
N
Output
Print the answer.
Sample Input 1
3
Sample Output 1
333
Concatenate three copies of the digit 3 to yield the string 333.
Sample Input 2
9
Sample Output 2
999999999
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 100 点
問題文
正の整数 X について、レベル X の 龍文字列 とは、1 個の L, X 個の o, 1 個の n, 1 個の g をこの順に並べた長さ (X+3) の文字列です。
正の整数 N が与えられるので、レベル N の龍文字列を出力してください。
大文字と小文字は区別されることに注意してください。
制約
- 1\leq N\leq 2024
- N は整数
入力
入力は以下の形式で標準入力から与えられる。
N
出力
レベル N の龍文字列を出力せよ。
入力例 1
3
出力例 1
Looong
1 個の L, 3 個の o, 1 個の n, 1 個の g をこの順に並べた文字列は Looong です。
入力例 2
1
出力例 2
Long
Score: 100 points
Problem Statement
For a positive integer X, the Dragon String of level X is a string of length (X+3) formed by one L, X occurrences of o, one n, and one g arranged in this order.
You are given a positive integer N. Print the Dragon String of level N.
Note that uppercase and lowercase letters are distinguished.
Constraints
- 1 \leq N \leq 2024
- N is an integer.
Input
The input is given from Standard Input in the following format:
N
Output
Print the Dragon String of level N.
Sample Input 1
3
Sample Output 1
Looong
Arranging one L, three os, one n, and one g in this order yields Looong.
Sample Input 2
1
Sample Output 2
Long
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
無限に長いピアノの鍵盤があります。 この鍵盤内の連続する区間であって、白鍵 W 個と黒鍵 B 個からなるものは存在しますか？
文字列 wbwbwwbwbwbw を無限に繰り返してできる文字列を S とおきます。
S の部分文字列であって、W 個の w と B 個の b からなるものは存在しますか？
S の部分文字列とは
S の部分文字列とは、ある 2 つの正整数 l,r\ (l\leq r) に対して、S の l 文字目、l+1 文字目、\dots、r 文字目をこの順に繋げてできる文字列のことをいいます。制約
- W,B は整数
- 0\leq W,B \leq 100
- W+B \geq 1
入力
入力は以下の形式で標準入力から与えられる。
W B
出力
S の部分文字列であって、W 個の w と B 個の b からなるものが存在するならば Yes を、存在しないならば No を出力せよ。
入力例 1
3 2
出力例 1
Yes
S の最初の 15 文字は wbwbwwbwbwbwwbw であり、S の 11 文字目から 15 文字目までを取り出してできる文字列 bwwbw は 3 個の w と 2 個の b からなる部分文字列の一例です。
入力例 2
3 0
出力例 2
No
3 個の w と 0 個の b からなる文字列は www のみですが、これは S の部分文字列ではありません。
入力例 3
92 66
出力例 3
Yes
Score: 200 points
Problem Statement
There is an infinitely long piano keyboard. Is there a continuous segment within this keyboard that consists of W white keys and B black keys?
Let S be the string formed by infinitely repeating the string wbwbwwbwbwbw.
Is there a substring of S that consists of W occurrences of w and B occurrences of b?
What is a substring of S?
A substring of S is a string that can be formed by concatenating the l-th, (l+1)-th, \dots, r-th characters of S in this order for some two positive integers l and r (l\leq r).Constraints
- W and B are integers.
- 0\leq W,B \leq 100
- W+B \geq 1
Input
The input is given from Standard Input in the following format:
W B
Output
If there is a substring of S that consists of W occurrences of w and B occurrences of b, print Yes; otherwise, print No.
Sample Input 1
3 2
Sample Output 1
Yes
The first 15 characters of S are wbwbwwbwbwbwwbw. You can take the 11-th through 15-th characters to form the string bwwbw, which is a substring consisting of three occurrences of w and two occurrences of b.
Sample Input 2
3 0
Sample Output 2
No
The only string consisting of three occurrences of w and zero occurrences of b is www, which is not a substring of S.
Sample Input 3
92 66
Sample Output 3
Yes
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
AtCoder Land では時報がモールス信号で行なわれます。高橋君はこのモールス信号を解読したいです。
N 個の文字列 S_1, S_2, \ldots, S_N が与えられます。S_i (1 \leq i \leq N) は . と - からなる文字列で、0 以上 9 以下のある数字に対応するモールス符号です。N 個の文字列を復号し、順に連結して 1 つの文字列として出力してください。
数字とモールス符号の対応は以下の通りです。
0 ----- 1 .---- 2 ..--- 3 ...-- 4 ....- 5 ..... 6 -.... 7 --... 8 ---.. 9 ----.
制約
- 1 \leq N \leq 100
- N は整数
- S_i (1 \leq i \leq N) は
.と-からなる文字列 - S_i (1 \leq i \leq N) は 0 以上 9 以下のある数字に対応するモールス符号
入力
入力は以下の形式で標準入力から与えられる。
N S_1 S_2 \vdots S_N
出力
N 個の文字列を復号し、順に連結して 1 つの文字列として出力してください。
入力例 1
3 ...-- ..... ---..
出力例 1
358
...-- は 3 と、..... は 5 と、---.. は 8 と復号されます。よって、358 を出力します。
入力例 2
10 ----- .---- ..--- ...-- ....- ..... -.... --... ---.. ----.
出力例 2
0123456789
Time Limit: 2 sec / Memory Limit: 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
0and1. - 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.