Problem Statement

There are four types of oysters, labeled 1, 2, 3, and 4. Exactly one of these types causes stomach trouble if eaten. The other types do not cause stomach trouble when eaten.

Takahashi ate oysters 1 and 2, and Aoki ate oysters 1 and 3. The information on whether each person got sick is given as two strings S_1 and S_2. Specifically, S_1 = sick means Takahashi got sick, and S_1 = fine means Takahashi did not get sick. Likewise, S_2 = sick means Aoki got sick, and S_2 = fine means Aoki did not get sick.

Based on the given information, find which type of oyster causes stomach trouble.

Constraints

• Each of S_1 and S_2 is sick or fine.

Sample Input 1

sick fine

Sample Output 1

2

Takahashi (who ate oysters 1 and 2) got sick, and Aoki (who ate oysters 1 and 3) did not get sick, so it can be concluded that oyster 2 causes stomach trouble.

Sample Input 2

fine fine

Sample Output 2

4

Neither Takahashi (who ate oysters 1 and 2) nor Aoki (who ate oysters 1 and 3) got sick, so it can be concluded that oyster 4 causes stomach trouble.

Problem Statement

You are given a string S of length N consisting of A, B, and C.
Find the position where ABC first appears as a (contiguous) substring in S. In other words, find the smallest integer n that satisfies all of the following conditions.

• 1 \leq n \leq N - 2.
• The string obtained by extracting the n-th through (n+2)-th characters of S is ABC.

If ABC does not appear in S, print -1.

Constraints

• 3 \leq N \leq 100
• S is a string of length N consisting of A, B, and C.

Sample Input 1

8
ABABCABC

Sample Output 1

3

ABC first appears in S at the 3-rd through 5-th characters of S. Therefore, the answer is 3.

Sample Input 2

3
ACB

Sample Output 2

-1

If ABC does not appear in S, print -1.

Sample Input 3

20
BBAAABBACAACABCBABAB

Sample Output 3

13

Problem Statement

The AtCoder amusement park has an attraction that can accommodate K people. Now, there are N groups lined up in the queue for this attraction.

The i-th group from the front (1\leq i\leq N) consists of A_i people. For all i (1\leq i\leq N), it holds that A_i \leq K.

Takahashi, as a staff member of this attraction, will guide the groups in the queue according to the following procedure.

Initially, no one has been guided to the attraction, and there are K empty seats.

1. If there are no groups in the queue, start the attraction and end the guidance.
2. Compare the number of empty seats in the attraction with the number of people in the group at the front of the queue, and do one of the following:
   • If the number of empty seats is less than the number of people in the group at the front, start the attraction. Then, the number of empty seats becomes K again.
   • Otherwise, guide the entire group at the front of the queue to the attraction. The front group is removed from the queue, and the number of empty seats decreases by the number of people in the group.
3. Go back to step 1.

Here, no additional groups will line up after the guidance has started. Under these conditions, it can be shown that this procedure will end in a finite number of steps.

Determine how many times the attraction will be started throughout the guidance.

Constraints

• 1\leq N\leq 100
• 1\leq K\leq 100
• 1\leq A_i\leq K\ (1\leq i\leq N)
• All input values are integers.

Sample Input 1

7 6
2 5 1 4 1 2 3

Sample Output 1

4

Initially, the seven groups are lined up as follows:

Part of Takahashi's guidance is shown in the following figure:

• Initially, the group at the front has 2 people, and there are 6 empty seats. Thus, he guides the front group to the attraction, leaving 4 empty seats.
• Next, the group at the front has 5 people, which is more than the 4 empty seats, so the attraction is started.
• After the attraction is started, there are 6 empty seats again, so the front group is guided to the attraction, leaving 1 empty seat.
• Next, the group at the front has 1 person, so they are guided to the attraction, leaving 0 empty seats.

In total, he starts the attraction four times before the guidance is completed. Therefore, print 4.

Sample Input 2

7 10
1 10 1 10 1 10 1

Sample Output 2

7

Sample Input 3

15 100
73 8 55 26 97 48 37 47 35 55 5 17 62 2 60

Sample Output 3

8

Problem Statement

This problem shares a similar setting with Problem A. The way Takahashi chooses cookies and what you are required to find are different from Problem A.

There are N boxes arranged in a row, and some of these boxes contain cookies.

The state of these boxes is represented by a string S of length N. Specifically, the i-th box (1\leq i \leq N) from the left contains one cookie if the i-th character of S is @, and is empty if it is ..

Over the next D days, Takahashi will choose and eat one cookie per day from among the cookies in these boxes. On each day, he chooses the cookie in the rightmost box that contains a cookie at that point.

Determine, for each of the N boxes, whether it will contain a cookie after D days have passed.

It is guaranteed that S contains at least D occurrences of @.

Constraints

• 1 \leq D \leq N \leq 100
• N and D are integers.
• S is a string of length N consisting of @ and ..
• S contains at least D occurrences of @.

Sample Input 1

5 2
.@@.@

Sample Output 1

.@...

Takahashi acts as follows:

• Day 1: There are cookies in the 2nd, 3rd, and 5th boxes from the left. Among these, the rightmost is the 5th box. He eats the cookie in this box.
• Day 2: There are cookies in the 2nd and 3rd boxes. Among these, the rightmost is the 3rd box. He eats the cookie in this box.
• After two days have passed, only the 2nd box from the left contains a cookie.

Therefore, the correct output is .@....

Sample Input 2

3 3
@@@

Sample Output 2

...

Sample Input 3

10 4
@@@.@@.@@.

Sample Output 3

@@@.......

Problem Statement

You are given a positive integer D.

Find the minimum value of |x^2+y^2-D| for non-negative integers x and y.

Constraints

• 1\leq D \leq 2\times 10^{12}
• All input values are integers.

Sample Input 1

21

Sample Output 1

1

For x=4 and y=2, we have |x^2+y^2-D| = |16+4-21|=1.

There are no non-negative integers x and y such that |x^2+y^2-D|=0, so the answer is 1.

Sample Input 2

998244353

Sample Output 2

0

Sample Input 3

264428617

Sample Output 3

32

Problem Statement

Takahashi has a red jewel of level N. (He has no other jewels.)
Takahashi can do the following operations any number of times.

• Convert a red jewel of level n (n is at least 2) into "a red jewel of level (n-1) and X blue jewels of level n".
• Convert a blue jewel of level n (n is at least 2) into "a red jewel of level (n-1) and Y blue jewels of level (n-1)".

Takahashi wants as many blue jewels of level 1 as possible. At most, how many blue jewels of level 1 can he obtain by the operations?

Constraints

• 1 \leq N \leq 10
• 1 \leq X \leq 5
• 1 \leq Y \leq 5
• All values in input are integers.

Sample Input 1

2 3 4

Sample Output 1

12

Takahashi can obtain 12 blue jewels of level 1 by the following conversions.

• First, he converts a red jewel of level 2 into a red jewel of level 1 and 3 blue jewels of level 2.
  • After this operation, Takahashi has 1 red jewel of level 1 and 3 blue jewels of level 2.
• Next, he repeats the following conversion 3 times: converting a blue jewel of level 2 into a red jewel of level 1 and 4 blue jewels of level 1.
  • After these operations, Takahashi has 4 red jewels of level 1 and 12 blue jewels of level 1.
• He cannot perform a conversion anymore.

He cannot obtain more than 12 blue jewels of level 1, so the answer is 12.

Sample Input 2

1 5 5

Sample Output 2

0

Takahashi may not be able to obtain a blue jewel of level 1.

Sample Input 3

10 5 5

Sample Output 3

3942349900

Note that the answer may not fit into a 32-bit integer type.

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.

Sample Input 1

5 5 5
1 1
3 3
4 4
2 3
2 5

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

5 3 3
1 1
2 2
2 2
2 2
2 2

Sample Output 4

No

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

Problem Statement

Let us play a game using a die. The game consists of at most N turns, each of which goes as follows.

• Throw a 6-sided die that shows 1,\ldots,6 with equal probability, and let X be the number shown (each throw is independent of the others).
• If it is the N-th turn now, your score is X, and the game ends.
• Otherwise, choose whether to continue or end the game.
  • If you end the game, your score is X, and there is no more turn.

Find the expected value of your score when you play the game to maximize this expected value.

Constraints

• 1 \leq N \leq 100

Sample Input 1

1

Sample Output 1

3.5000000000

Sample Input 2

2

Sample Output 2

4.2500000000

Sample Input 3

10

Sample Output 3

5.6502176688

Problem Statement

You are given two trees: tree 1 with N_1 vertices numbered 1 to N_1, and tree 2 with N_2 vertices numbered 1 to N_2. The i-th edge of tree 1 connects vertices u_{1,i} and v_{1,i} bidirectionally, and the i-th edge of tree 2 connects vertices u_{2,i} and v_{2,i} bidirectionally.

One can add a bidirectional edge between vertex i of tree 1 and vertex j of tree 2 to obtain a single tree. Let f(i,j) be the diameter of this tree.

Find \displaystyle \sum_{i=1}^{N_1}\sum_{j=1}^{N_2} f(i,j).

Here, the distance between two vertices of a tree is the minimum number of edges that must be used to move between them, and the diameter of a tree is the maximum distance between two vertices.

Constraints

• 1 \le N_1, N_2 \le 2 \times 10^{5}
• 1 \le u_{1,i}, v_{1,i} \le N_1
• 1 \le u_{2,i}, v_{2,i} \le N_2
• Both given graphs are trees.
• All input values are integers.

Sample Input 1

3
1 3
1 2
3
1 2
3 1

Sample Output 1

39

For example, one can connect vertex 2 of tree 1 and vertex 3 of tree 2 to obtain a tree of diameter 5. Thus, f(2,3) is 5.

The sum of f(i,j) is 39.

Sample Input 2

7
5 6
1 3
5 7
4 5
1 6
1 2
5
5 3
2 4
2 3
5 1

Sample Output 2

267