AtCoder Daily Training HARD 2024/05/28 15:30start

E - Jumping Takahashi

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

高橋君は数直線上の座標 0 の位置にいます。

これから高橋君は N 回のジャンプを行います。i \, (1 \leq i \leq N) 回目のジャンプでは、正の方向に a_i または b_i 移動します。

N 回のジャンプの後に座標 X の位置にいるようにすることはできますか？

制約

1 \leq N \leq 100
1 \leq a_i \lt b_i \leq 100 \, (1 \leq i \leq N)
1 \leq X \leq 10000
入力は全て整数

入力

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

N X
a_1 b_1
\vdots
a_N b_N

出力

N 回のジャンプの後に座標 X の位置にいるようにすることができるならば Yes と、そうでないなら No と出力せよ。

入力例 1

2 10
3 6
4 5

出力例 1

Yes

1 回目のジャンプでは b_1 (= 6) 移動し、2 回目のジャンプでは a_2 (= 4) 移動することで、座標 X (= 10) の位置にいるようにすることができます。

入力例 2

2 10
10 100
10 100

出力例 2

No

1 回目のジャンプの後に座標 X (= 10) の位置にいるようにすることはできますが、全てのジャンプの後に座標 X (= 10) の位置にいるようにすることはできません。

入力例 3

出力例 3

Yes

Score : 300 points

Problem Statement

Takahashi is standing at the coordinate 0 on a number line.

He will now perform N jumps. In the i-th jump (1 \leq i \leq N), he moves a_i or b_i in the positive direction.

Is it possible for him to be at the coordinate X after N jumps?

Constraints

1 \leq N \leq 100
1 \leq a_i \lt b_i \leq 100 \, (1 \leq i \leq N)
1 \leq X \leq 10000
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N X
a_1 b_1
\vdots
a_N b_N

Output

If it is possible for Takahashi to be at the coordinate X after N jumps, print Yes; otherwise, print No.

Sample Input 1

2 10
3 6
4 5

Sample Output 1

Yes

By moving b_1 (= 6) in the first jump and a_2 (= 4) in the second jump, he can be at the coordinate X (= 10).

Sample Input 2

2 10
10 100
10 100

Sample Output 2

No

He can be at the coordinate X (= 10) after the first jump, but not after all jumps.

Sample Input 3

Sample Output 3

Yes

F - One More aab aba baa

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

文字列 S の各文字を並べ替えて作ることが可能な文字列を辞書順にすべて列挙したとき、前から K 番目にくる文字列を求めてください。

「各文字を並べ替えて作ることが可能な文字列」とは？

「文字列 A が文字列 B の各文字を並べ替えて作ることが可能な文字列である」とは、任意の文字が文字列 A と文字列 B に同数含まれるということを指します。

制約

1 \le |S| \le 8
S は英小文字のみからなる
S の各文字を並べ替えてできる文字列は K 種類以上存在する

入力

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

S K

出力

答えを出力せよ。

入力例 1

aab 2

出力例 1

aba

文字列 aab の各文字を並べ替えて作ることが可能な文字列は \{ aab, aba, baa \} の 3 つですが、このうち辞書順で前から 2 番目にくるものは aba です。

入力例 2

baba 4

出力例 2

baab

入力例 3

ydxwacbz 40320

出力例 3

zyxwdcba

Score : 300 points

Problem Statement

Find the K-th lexicographically smallest string among the strings that are permutations of a string S.

What is a permutation of a string?

A string A is said to be a permutation of a string B when any character occurs the same number of times in A and B.

Constraints

1 \le |S| \le 8
S consists of lowercase English letters.
There are at least K distinct strings that are permutations of S.

Input

Input is given from Standard Input in the following format:

S K

Output

Print the answer.

Sample Input 1

aab 2

Sample Output 1

aba

There are three permutations of a string aab: \{ aab, aba, baa \}. The 2-nd lexicographically smallest of them is aba.

Sample Input 2

baba 4

Sample Output 2

baab

Sample Input 3

ydxwacbz 40320

Sample Output 3

zyxwdcba

G - Tiling

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 450 点

問題文

一辺の長さが 1 のマスからなる H 行 W 列のマス目と、N 枚のタイルがあります。
i (1\leq i\leq N) 枚目のタイルは A_i\times B_i の長方形です。
以下の条件をすべてみたすようにタイルをマス目に置くことができるか判定してください。

全てのマスがちょうど 1 枚のタイルで覆われている。
使用されないタイルがあっても良い。
使用するタイルは 回転したり裏返したりして置かれていても良い。ただし、各タイルはマスの線に合わせてマス目からはみ出ることがないように置かれていなければならない。

制約

1\leq N\leq 7
1 \leq H,W \leq 10
1\leq A_i,B_i\leq 10
入力はすべて整数

入力

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

N H W
A_1 B_1
A_2 B_2
\vdots
A_N B_N

出力

問題文中の条件をみたすようにタイルをマス目に置くことができるならば Yes を、そうでないならば No を出力せよ。

入力例 1

出力例 1

Yes

2,4,5 枚目のタイルを使用して次のように置くと、マス目の各マスをちょうど 1 枚のタイルで覆うことができます。

よって、Yes を出力します。

入力例 2

1 1 2
2 3

出力例 2

No

マス目からはみ出さないようにタイルを置くことはできません。
よって、No を出力します。

入力例 3

1 2 2
1 1

出力例 3

No

全てのマスを覆うようにタイルを置くことができません。
よって、No を出力します。

入力例 4

出力例 4

No

全てのマスはちょうど 1 枚のタイルで覆われている必要があることに注意してください。

Score: 450 points

Problem Statement

There is a grid of H rows and W columns, each cell having a side length of 1, and we have N tiles.
The i-th tile (1\leq i\leq N) is a rectangle of size A_i\times B_i.
Determine whether it is possible to place the tiles on the grid so that all of the following conditions are satisfied:

Every cell is covered by exactly one tile.
It is fine to have unused tiles.
The tiles may be rotated or flipped when placed. However, each tile must be aligned with the edges of the cells without extending outside the grid.

Constraints

1\leq N\leq 7
1 \leq H,W \leq 10
1\leq A_i,B_i\leq 10
All input values are integers.

Input

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

N H W
A_1 B_1
A_2 B_2
\ldots
A_N B_N

Output

If it is possible to place the tiles on the grid so that all of the conditions in the problem statement are satisfied, print Yes; otherwise, print No.

Sample Input 1

Sample Output 1

Yes

Placing the 2-nd, 4-th, and 5-th tiles as shown below covers every cell of the grid by exactly one tile.

Hence, print Yes.

Sample Input 2

1 1 2
2 3

Sample Output 2

No

It is impossible to place the tile without letting it extend outside the grid.
Hence, print No.

Sample Input 3

1 2 2
1 1

Sample Output 3

No

It is impossible to cover all cells with the tile.
Hence, print No.

Sample Input 4

Sample Output 4

No

Note that each cell must be covered by exactly one tile.

H - Σ[k=0..10^100]floor(X／10^k)

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 500 点

問題文

\displaystyle \sum_{k=0}^{10^{100}} \left \lfloor \frac{X}{10^k} \right \rfloor を求めてください。

注釈

\lfloor A \rfloor は、 A の小数点以下を切り捨てた値を指します。

制約

X は整数
1 \le X < 10^{500000}

入力

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

出力

答えを整数として出力せよ。
但し、たとえ答えが大きな整数であっても、求める答えを正確に整数として出力する必要がある。たとえば、 2.33e+21 のような指数表記や、 0523 のような先頭に不要な 0 を付けたような表記は許されない。

入力例 1

出力例 1

求める値は、 1225+122+12+1+0+0+\dots+0=1360 となります。

入力例 2

出力例 2

繰り上がりに注意してください。

入力例 3

314159265358979323846264338327950288419716939937510

出力例 3

349065850398865915384738153697722542688574377708317

入力される値も出力すべき値も非常に大きくなる場合があります。

Score : 500 points

Problem Statement

Find \displaystyle \sum_{k=0}^{10^{100}} \left \lfloor \frac{X}{10^k} \right \rfloor.

Notes

\lfloor A \rfloor denotes the value of A truncated to an integer.

Constraints

X is an integer.
1 \le X < 10^{500000}

Input

Input is given from Standard Input in the following format:

Output

Print the answer as an integer.
Here, the answer must be precisely printed as an integer, even if it is large. It is not allowed to use exponential notation, such as 2.33e+21, or print unnecessary leading zeros, as in 0523.

Sample Input 1

Sample Output 1

The value we seek is 1225+122+12+1+0+0+\dots+0=1360.

Sample Input 2

Sample Output 2

Beware of carries.

Sample Input 3

314159265358979323846264338327950288419716939937510

Sample Output 3

349065850398865915384738153697722542688574377708317

The values in input and output can both be enormous.

I - Usual Color Ball Problems

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 550 点

問題文

正整数 N, M, K と、長さ N の正整数列 (C_1, C_2, \ldots, C_N) が与えられるので、 r = 0, 1, 2, \ldots, N-1 の場合それぞれについて、下記の問題の答えを出力してください。

色がついた N 個のボールからなる列があり、i = 1, 2, \ldots, N について、列の先頭から i 番目にあるボールの色は C_i です。また、1 から M の番号がつけられた M 個の空の箱があります。

下記の手順を行った後に箱に入っているボールの総数を求めてください。

まず、下記の操作を r 回行う。

列の先頭のボール 1 個を列の最後尾に移動する。

その後、列にボールが 1 個以上残っている限り、下記の操作を繰り返す。

列の先頭のボールと同じ色のボールが既に 1 個以上 K 個未満入っている箱が存在する場合、その箱に列の先頭のボールを入れる。

そのような箱が存在しない場合、

空の箱が存在するなら、そのうち番号が最小のものに、列の先頭のボールを入れる。

空の箱が存在しない場合、列の先頭のボールをどの箱にも入れず、食べる。

制約

入力される値はすべて整数
1 \leq N \leq 2 \times 10^5
1 \leq M, K \leq N
1 \leq C_i \leq N

入力

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

N M K
C_1 C_2 \ldots C_N

出力

r = 0, 1, 2, \ldots, N-1 のそれぞれの場合の問題の答え X_r を下記の通りに N 行にわたって出力せよ。

X_0
X_1
\vdots
X_{N-1}

入力例 1

7 2 2
1 2 3 5 2 5 4

出力例 1

例として、r = 1 の場合の手順を説明します。まず「列の先頭のボール 1 個を列の最後尾に移動する」ことを 1 回行い、ボールの色の列は (2, 3, 5, 2, 5, 4, 1) となります。その後、ボールを箱に入れていく操作を下記の通りに行います。

1 回目の操作：先頭のボールの色は 2 です。色 2 のボールが 1 個以上 2 個未満入った箱は存在しないため、先頭のボールを空の箱のうち番号が最小の箱 1 に入れます。
2 回目の操作：先頭のボールの色は 3 です。色 3 のボールが 1 個以上 2 個未満入った箱は存在しないため、先頭のボールを空の箱のうち番号が最小の箱 2 に入れます。
3 回目の操作：先頭のボールの色は 5 です。色 5 のボールが 1 個以上 2 個未満入った箱も空の箱も存在しないため、先頭のボールを食べます。
4 回目の操作：先頭のボールの色は 2 です。色 2 のボールが 1 個以上 2 個未満入った箱として箱 1 が存在するため、先頭のボールを箱 1 に入れます。
5 回目の操作：先頭のボールの色は 5 です。色 5 のボールが 1 個以上 2 個未満入った箱も空の箱も存在しないため、先頭のボールを食べます。
6 回目の操作：先頭のボールの色は 4 です。色 4 のボールが 1 個以上 2 個未満入った箱も空の箱も存在しないため、先頭のボールを食べます。
7 回目の操作：先頭のボールの色は 1 です。色 1 のボールが 1 個以上 2 個未満入った箱も空の箱も存在しないため、先頭のボールを食べます。

最終的に箱に入っているボールの総数は 3 個であるので、r = 1 の問題の答えは 3 です。

入力例 2

20 5 4
20 2 20 2 7 3 11 20 3 8 7 9 1 11 8 20 2 18 11 18

出力例 2

Score: 550 points

Problem Statement

You are given positive integers N, M, K, and a sequence of positive integers of length N, (C_1, C_2, \ldots, C_N). For each r = 0, 1, 2, \ldots, N-1, print the answer to the following problem.

There is a sequence of N colored balls. For i = 1, 2, \ldots, N, the color of the i-th ball from the beginning of the sequence is C_i. Additionally, there are M empty boxes numbered 1 to M.

Determine the total number of balls in the boxes after performing the following steps.

First, perform the following operation r times.

Move the frontmost ball in the sequence to the end of the sequence.

Then, repeat the following operation as long as at least one ball remains in the sequence.

If there is a box that already contains at least one but fewer than K balls of the same color as the frontmost ball in the sequence, put the frontmost ball into that box.

If there is no such box,

If there is an empty box, put the frontmost ball into the one with the smallest box number.

If there are no empty boxes, eat the frontmost ball without putting it into any box.

Constraints

All input values are integers.
1 \leq N \leq 2 \times 10^5
1 \leq M, K \leq N
1 \leq C_i \leq N

Input

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

N M K
C_1 C_2 \ldots C_N

Output

Print the answer X_r to the problem for each r = 0, 1, 2, \ldots, N-1 over N lines as follows:

X_0
X_1
\vdots
X_{N-1}

Sample Input 1

7 2 2
1 2 3 5 2 5 4

Sample Output 1

For example, let us explain the procedure for r = 1. First, perform the operation "Move the frontmost ball in the sequence to the end of the sequence" once, and the sequence of ball colors becomes (2, 3, 5, 2, 5, 4, 1). Then, proceed with the operation of putting balls into boxes as follows:

First operation: The color of the frontmost ball is 2. There is no box with at least one but fewer than two balls of color 2, so put the frontmost ball into the empty box with the smallest box number, box 1.
Second operation: The color of the frontmost ball is 3. There is no box with at least one but fewer than two balls of color 3, so put the frontmost ball into the empty box with the smallest box number, box 2.
Third operation: The color of the frontmost ball is 5. There is no box with at least one but fewer than two balls of color 5 and no empty boxes, so eat the frontmost ball.
Fourth operation: The color of the frontmost ball is 2. There is a box, box 1, with at least one but fewer than two balls of color 2, so put the frontmost ball into box 1.
Fifth operation: The color of the frontmost ball is 5. There is no box with at least one but fewer than two balls of color 5 and no empty boxes, so eat the frontmost ball.
Sixth operation: The color of the frontmost ball is 4. There is no box with at least one but fewer than two balls of color 4 and no empty boxes, so eat the frontmost ball.
Seventh operation: The color of the frontmost ball is 1. There is no box with at least one but fewer than two balls of color 1 and no empty boxes, so eat the frontmost ball.

The final total number of balls in the boxes is 3, so the answer to the problem for r = 1 is 3.

Sample Input 2

20 5 4
20 2 20 2 7 3 11 20 3 8 7 9 1 11 8 20 2 18 11 18

Sample Output 2