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

A - Feet

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

配点 : 100 点

問題文

1 フィートは 12 インチです。

A フィート B インチは、インチ換算で何インチですか？

制約

1 \leq A \leq 8
0 \leq B \leq 11
入力される値はすべて整数

入力

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

A B

出力

答えを 1 行に出力せよ。単位 (インチ) は省いて出力すること。

入力例 1

6 7

出力例 1

6 フィート 7 インチは、インチ換算で 6 \times 12 + 7 = 79 インチです。

入力例 2

4 11

出力例 2

4 フィート 11 インチは、インチ換算で 4 \times 12 + 11 = 59 インチです。

入力例 3

8 0

出力例 3

8 フィート 0 インチは、インチ換算で 8 \times 12 + 0 = 96 インチです。

Score : 100 points

Problem Statement

1 foot is 12 inches.

How many inches is A feet B inches?

Constraints

1 \leq A \leq 8
0 \leq B \leq 11
All input values are integers.

Input

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

A B

Output

Output the answer in one line. Omit the unit (inches).

Sample Input 1

6 7

Sample Output 1

6 feet 7 inches is 6 \times 12 + 7 = 79 inches.

Sample Input 2

4 11

Sample Output 2

4 feet 11 inches is 4 \times 12 + 11 = 59 inches.

Sample Input 3

8 0

Sample Output 3

8 feet 0 inches is 8 \times 12 + 0 = 96 inches.

B - Exponential or Quadratic

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

配点 : 100 点

問題文

2^n \gt n^2 ですか？

制約

n は 1 以上 10^9 以下の整数

入力

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

出力

2^n \gt n^2 なら Yes を、そうでないなら No を出力せよ。

入力例 1

出力例 1

Yes

2^5=32,\ 5^2=25 より 2^n \gt n^2 であるため、Yes を出力します。

入力例 2

出力例 2

No

n=2 の場合 2^n=n^2=2^2 となり、故に 2^n \gt n^2 ではありません。よって No を出力します。

入力例 3

623947744

出力例 3

Yes

Score : 100 points

Problem Statement

Does 2^n \gt n^2 hold?

Constraints

n is an integer between 1 and 10^9 (inclusive).

Input

Input is given from Standard Input in the following format:

Output

If 2^n \gt n^2, print Yes; otherwise, print No.

Sample Input 1

Sample Output 1

Yes

Since 2^5=32,\ 5^2=25, we have 2^n \gt n^2, so Yes should be printed.

Sample Input 2

Sample Output 2

No

For n=2, we have 2^n=n^2=2^2, so 2^n \gt n^2 does not hold. Thus, No should be printed.

Sample Input 3

623947744

Sample Output 3

Yes

C - Qual B

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

配点 : 200 点

問題文

あるプログラミングコンテストの予選に N 人が参加し、参加者全員が異なる順位を得ました。
長さ N の文字列 S が与えられ、この文字列は決勝への参加希望の有無を表現します。具体的には下記の通りです。

S の i 文字目が o なら、予選 i 位の参加者が決勝への参加を希望した。
S の i 文字目が x なら、予選 i 位の参加者が決勝への参加を希望しなかった。

決勝への参加を希望した参加者のうち順位の小さい方から K 人が予選を通過します。

以下の条件を満たす長さ N の文字列 T を出力してください。

予選 i 位の参加者が予選を通過する場合、 T の i 文字目は o
予選 i 位の参加者が予選を通過しない場合、 T の i 文字目は x

制約

N,K は整数
1 \le K \le N \le 100
S は o と x からなる長さ N の文字列
S には少なくとも K 個の o が含まれる

入力

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

N K
S

出力

答えを出力せよ。

入力例 1

10 3
oxxoxooxox

出力例 1

oxxoxoxxxx

この入力の場合、予選の参加者は N=10 人であり、予選を通過する人数は K=3 人です。

予選 1 位の参加者は決勝への参加を希望しているため、予選を通過します。この時点で、通過者は 1 人です。
予選 2,3 位の参加者は決勝への参加を希望していないため、予選を通過しません。
予選 4 位の参加者は決勝への参加を希望しているため、予選を通過します。この時点で、通過者は 2 人です。
予選 5 位の参加者は決勝への参加を希望していないため、予選を通過しません。
予選 6 位の参加者は決勝への参加を希望しているため、予選を通過します。この時点で、通過者は 3 人です。
ここで、予選を通過した人数が 3 人となりました。なので、予選 7 位以下の参加者は予選を通過しません。

Score : 200 points

Problem Statement

There were N contestants in the qualification round of a programming contest. All contestants got distinct ranks.
You are given a length-N string S, which represents whether the contestants want to participate in the final round or not. Specifically,

if the i-th character of S is o, the contestant ranked i-th in the qualification wants to participate in the final;
if the i-th character of S is x, the contestant ranked i-th in the qualification does not want to participate in the final.

Among those who want to participate in the final, K contestants with the smallest ranks advance to the final.

Print a string T of length N that satisfies the following conditions:

if the contestant ranked i-th in the qualification advances to the final, the i-th character of T is o;
if the contestant ranked i-th in the qualification does not advance to the final, the i-th character of T is x.

Constraints

N and K are integers.
1 \le K \le N \le 100
S is a string of length N consisting of o and x.
S has at least K o's.

Input

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

N K
S

Output

Print the answer.

Sample Input 1

10 3
oxxoxooxox

Sample Output 1

oxxoxoxxxx

In this input, N=10 people took part in the qualification round, and K=3 of them advance to the final.

The participant who ranked 1-st in the qualification wants to participate in the final, so the participant advances to the final. 1 participant has advanced so far.
The participants who ranked 2-nd and 3-rd in the qualification do not want to participate in the final, so the participants do not advance to the final.
The participant who ranked 4-th in the qualification wants to participate in the final, so the participant advances to the final. 2 participants have advanced so far.
The participants who ranked 5-th in the qualification does not want to participate in the final, so the participant does not advance to the final.
The participant who ranked 6-th in the qualification wants to participate in the final, so the participant advances to the final. 3 participants have advanced so far.
Now that 3 people have advanced to the final, no participants ranked 7-th or lower advance to the final.

D - Rectangle Detection

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

配点 : 200 点

問題文

高橋くんは、以下の方法で 10 個の文字列 S_1,S_2,\dots,S_{10} を生成しました。

まず、 S_i (1 \le i \le 10)= .......... ( . が 10 個並んだ文字列) とする。
次に、以下の条件を全て満たす 4 つの整数 A,B,C,D を選ぶ。
- 1 \le A \le B \le 10
- 1 \le C \le D \le 10
その後、以下の条件を全て満たす全ての整数組 (i,j) について、 S_i の j 文字目を # に書き換える。
- A \le i \le B
- C \le j \le D

以上の方法で生成された S_1,S_2,\dots,S_{10} が与えられるので、高橋くんが選んだ整数 A,B,C,D を求めてください。
なお、制約より A,B,C,D は一意に定まる (答えはただひとつ存在する) ことが証明できます。

制約

S_1,S_2,\dots,S_{10} は問題文中の方法で生成されうるそれぞれ長さ 10 の文字列

入力

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

S_1
S_2
\vdots
S_{10}

出力

答えを以下の形式で出力せよ。

A B
C D

入力例 1

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

出力例 1

5 8
4 9

高橋くんが選んだ整数は A=5,B=8,C=4,D=9 です。
このように選ぶことにより、 S_5,S_6,S_7,S_8 の 4 文字目から 9 文字目が # であり他の文字が . である 10 個の長さ 10 の文字列 S_1,S_2,\dots,S_{10} が生成されます。
これは入力で与えられた 10 個の文字列と一致します。

入力例 2

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

出力例 2

2 2
3 3

入力例 3

##########
##########
##########
##########
##########
##########
##########
##########
##########
##########

出力例 3

1 10
1 10

Score : 200 points

Problem Statement

Takahashi generated 10 strings S_1,S_2,\dots,S_{10} as follows.

First, let S_i (1 \le i \le 10)= .......... (10 .s in a row).
Next, choose four integers A, B, C, and D satisfying all of the following.
- 1 \le A \le B \le 10.
- 1 \le C \le D \le 10.
Then, for every pair of integers (i,j) satisfying all of the following, replace the j-th character of S_i with #.
- A \le i \le B.
- C \le j \le D.

You are given S_1,S_2,\dots,S_{10} generated as above. Find the integers A, B, C, and D Takahashi chose.
It can be proved that such integers A, B, C, and D uniquely exist (there is just one answer) under the Constraints.

Constraints

S_1,S_2,\dots,S_{10} are strings, each of length 10, that can be generated according to the Problem Statement.

Input

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

S_1
S_2
\vdots
S_{10}

Output

Print the answer in the following format:

A B
C D

Sample Input 1

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

Sample Output 1

5 8
4 9

Here, Takahashi chose A=5, B=8, C=4, D=9.
This choice generates 10 strings S_1,S_2,\dots,S_{10}, each of length 10, where the 4-th through 9-th characters of S_5,S_6,S_7,S_8 are #, and the other characters are ..
These are equal to the strings given in the input.

Sample Input 2

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

Sample Output 2

2 2
3 3

Sample Input 3

##########
##########
##########
##########
##########
##########
##########
##########
##########
##########

Sample Output 3

1 10
1 10

E - Simple path

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

配点 : 300 点

問題文

N 頂点の木 T があり、 i (1\leq i\leq N-1) 番目の辺は頂点 U_i と頂点 V_i を結んでいます。

T 上の相異なる 2 頂点 X,Y が与えられるので、頂点 X から頂点 Y への単純パス上の頂点（端点含む）を順に列挙してください。

ただし、木上の任意の相異なる 2 頂点 a,b について、a から b への単純パスがただ一つ存在することが証明できます。

単純パスとは？

グラフ G 上の頂点 X,Y に対して、頂点列 v_1,v_2, \ldots, v_k であって、 v_1=X, v_k=Y かつ、1\leq i\leq k-1 に対して v_i と v_{i+1} が辺で結ばれているようなものを頂点 X から頂点 Y へのパスと呼びます。さらに、v_1,v_2, \ldots, v_k がすべて異なるようなものを頂点 X から頂点 Y への 単純パス と呼びます。

制約

1\leq N\leq 2\times 10^5
1\leq X,Y\leq N
X\neq Y
1\leq U_i,V_i\leq N
入力はすべて整数
与えられるグラフは木

入力

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

N X Y
U_1 V_1
U_2 V_2
\vdots
U_{N-1} V_{N-1}

出力

頂点 X から頂点 Y への単純パス上の頂点番号を順に空白区切りで出力せよ。

入力例 1

出力例 1

2 1 3 5

木 T は以下のような形であり、頂点 2 から頂点 5への単純パスは頂点 2 \to 頂点 1 \to 頂点 3 \to 頂点 5 となります。
よって、2,1,3,5 をこの順に空白区切りで出力します。

入力例 2

出力例 2

1 2

木 T は以下のような形です。

Score : 300 points

Problem Statement

There is a tree T with N vertices. The i-th edge (1\leq i\leq N-1) connects vertex U_i and vertex V_i.

You are given two different vertices X and Y in T. List all vertices along the simple path from vertex X to vertex Y in order, including endpoints.

It can be proved that, for any two different vertices a and b in a tree, there is a unique simple path from a to b.

What is a simple path?

For vertices X and Y in a graph G, a path from vertex X to vertex Y is a sequence of vertices v_1,v_2, \ldots, v_k such that v_1=X, v_k=Y, and v_i and v_{i+1} are connected by an edge for each 1\leq i\leq k-1. Additionally, if all of v_1,v_2, \ldots, v_k are distinct, the path is said to be a simple path from vertex X to vertex Y.

Constraints

1\leq N\leq 2\times 10^5
1\leq X,Y\leq N
X\neq Y
1\leq U_i,V_i\leq N
All values in the input are integers.
The given graph is a tree.

Input

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

N X Y
U_1 V_1
U_2 V_2
\vdots
U_{N-1} V_{N-1}

Output

Print the indices of all vertices along the simple path from vertex X to vertex Y in order, with spaces in between.

Sample Input 1

Sample Output 1

2 1 3 5

The tree T is shown below. The simple path from vertex 2 to vertex 5 is 2 \to 1 \to 3 \to 5.
Thus, 2,1,3,5 should be printed in this order, with spaces in between.

Sample Input 2

Sample Output 2

1 2

The tree T is shown below.