Problem Statement

Takahashi wants to send a letter to Santa Claus. He has an envelope with an X-yen (Japanese currency) stamp stuck on it.
To be delivered to Santa Claus, the envelope must have stamps in a total value of at least Y yen.
Takahashi will put some more 10-yen stamps so that the envelope will have stamps worth at least Y yen in total.
At least how many more 10-yen stamps does Takahashi need to put on the envelope?

Constraints

• X and Y are integers.
• 1 \le X,Y \le 1000

Sample Input 1

80 94

Sample Output 1

2

• After adding zero 10-yen stamps to the 80-yen stamp, the total is 80 yen, which is less than the required amount of 94 yen.
• After adding one 10-yen stamp to the 80-yen stamp, the total is 90 yen, which is less than the required amount of 94 yen.
• After adding two 10-yen stamps to the 80-yen stamp, the total is 100 yen, which is not less than the required amount of 94 yen.

Sample Input 2

1000 63

Sample Output 2

0

The envelope may already have a stamp with enough value.

Sample Input 3

270 750

Sample Output 3

48

Problem Statement

You are given a string S consisting of lowercase English letters.
Remove all occurrences of a, e, i, o, u from S and print the resulting string.
S contains at least one character other than a, e, i, o, u.

Constraints

• S is a string of length between 1 and 100, inclusive, consisting of lowercase English letters.
• S contains at least one character other than a, e, i, o, u.

Sample Input 1

atcoder

Sample Output 1

tcdr

For S = atcoder, remove the 1-st, 4-th, and 6-th characters to get tcdr.

Sample Input 2

xyz

Sample Output 2

xyz

Sample Input 3

aaaabbbbcccc

Sample Output 3

bbbbcccc

Problem Statement

There is a grid of 64 squares with 8 rows and 8 columns. Let (i,j) denote the square at the i-th row from the top (1\leq i\leq8) and j-th column from the left (1\leq j\leq8).

Each square is either empty or has a piece placed on it. The state of the squares is represented by a sequence (S_1,S_2,S_3,\ldots,S_8) of 8 strings of length 8. Square (i,j) (1\leq i\leq8,1\leq j\leq8) is empty if the j-th character of S_i is ., and has a piece if it is #.

You want to place your piece on an empty square in such a way that it cannot be captured by any of the existing pieces.

A piece placed on square (i,j) can capture pieces that satisfy either of the following conditions:

• Placed on a square in row i
• Placed on a square in column j

For example, a piece placed on square (4,4) can capture pieces placed on the squares shown in blue in the following figure:

How many squares can you place your piece on?

Constraints

• Each S_i is a string of length 8 consisting of . and # (1\leq i\leq 8).

Sample Input 1

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

Sample Output 1

4

The existing pieces can capture pieces placed on the squares shown in blue in the following figure:

Therefore, you can place your piece without it being captured on 4 squares: square (6,6), square (6,7), square (7,6), and square (7,7).

Sample Input 2

........
........
........
........
........
........
........
........

Sample Output 2

64

There may be no pieces on the grid.

Sample Input 3

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

Sample Output 3

4

Problem Statement

You have an empty sequence A. There are Q queries given, and you need to process them in the order they are given.
The queries are of the following two types:

• 1 x: Append x to the end of A.
• 2 k: Find the k-th value from the end of A. It is guaranteed that the length of A is at least k when this query is given.

Constraints

• 1 \leq Q \leq 100
• In the first type of query, x is an integer satisfying 1 \leq x \leq 10^9.
• In the second type of query, k is a positive integer not greater than the current length of sequence A.

Sample Input 1

5
1 20
1 30
2 1
1 40
2 3

Sample Output 1

30
20

• Initially, A is empty.
• The first query appends 20 to the end of A, making A=(20).
• The second query appends 30 to the end of A, making A=(20,30).
• The answer to the third query is 30, which is the 1-st value from the end of A=(20,30).
• The fourth query appends 40 to the end of A, making A=(20,30,40).
• The answer to the fifth query is 20, which is the 3-rd value from the end of A=(20,30,40).

Problem Statement

As KEYENCE headquarters have more and more workers, they decided to divide the departments in the headquarters into two groups and stagger their lunch breaks.

KEYENCE headquarters have N departments, and the number of people in the i-th department (1\leq i\leq N) is K_i.

When assigning each department to Group A or Group B, having each group take lunch breaks at the same time, and ensuring that the lunch break times of Group A and Group B do not overlap, find the minimum possible value of the maximum number of people taking a lunch break at the same time.
In other words, find the minimum possible value of the larger of the following: the total number of people in departments assigned to Group A, and the total number of people in departments assigned to Group B.

Constraints

• 2 \leq N \leq 20
• 1 \leq K_i \leq 10^8
• All input values are integers.

Sample Input 1

5
2 3 5 10 12

Sample Output 1

17

When assigning departments 1, 2, and 5 to Group A, and departments 3 and 4 to Group B, Group A has a total of 2+3+12=17 people, and Group B has a total of 5+10=15 people. Thus, the maximum number of people taking a lunch break at the same time is 17.

It is impossible to assign the departments so that both groups have 16 or fewer people, so print 17.

Sample Input 2

2
1 1

Sample Output 2

1

Multiple departments may have the same number of people.

Sample Input 3

6
22 25 26 45 22 31

Sample Output 3

89

For example, when assigning departments 1, 4, and 5 to Group A, and departments 2, 3, and 6 to Group B, the maximum number of people taking a lunch break at the same time is 89.

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 0 and 1.
• The sum of |S| = 2^N-1 in each input does not exceed 5 \times 10^5.

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.

Problem Statement

For a positive integer k, the Pyramid Sequence of size k is a sequence of length (2k-1) where the terms of the sequence have the values 1,2,\ldots,k-1,k,k-1,\ldots,2,1 in this order.

You are given a sequence A=(A_1,A_2,\ldots,A_N) of length N.
Find the maximum size of a Pyramid Sequence that can be obtained by repeatedly choosing and performing one of the following operations on A (possibly zero times).

• Choose one term of the sequence and decrease its value by 1.
• Remove the first or last term.

It can be proved that the constraints of the problem guarantee that at least one Pyramid Sequence can be obtained by repeating the operations.

Constraints

• 1\leq N\leq 2\times 10^5
• 1\leq A_i\leq 10^9
• All input values are integers.

Sample Input 1

5
2 2 3 1 1

Sample Output 1

2

Starting with A=(2,2,3,1,1), you can create a Pyramid Sequence of size 2 as follows:

• Choose the third term and decrease it by 1. The sequence becomes A=(2,2,2,1,1).
• Remove the first term. The sequence becomes A=(2,2,1,1).
• Remove the last term. The sequence becomes A=(2,2,1).
• Choose the first term and decrease it by 1. The sequence becomes A=(1,2,1).

(1,2,1) is a Pyramid Sequence of size 2.
On the other hand, there is no way to perform the operations to create a Pyramid Sequence of size 3 or larger, so you should print 2.

Sample Input 2

5
1 2 3 4 5

Sample Output 2

3

Sample Input 3

1
1000000000

Sample Output 3

1

Problem Statement

There are N+1 sequences A_0, A_1, \ldots, A_{N}. A_i is defined as follows:

• A_0 is an empty sequence.
• A_i\ (1\leq i\leq N) is a sequence obtained by appending an integer y_i to the end of the sequence A_{x_i}\ (0\leq x_i\lt i).

Find the permutation P=(P_1, P_2,\ldots,P_N) of (1,2,\ldots,N) that satisfies the following condition:

• For i = 1,2,\ldots,N-1, one of the following holds:
  • A_{P_i} is lexicographically smaller than A_{P_{i+1}}.
  • A_{P_i}= A_{P_{i+1}} and P_i\lt P_{i+1}

In other words, when A_1,A_2,\ldots,A_N are arranged in lexicographical order (when there are multiple equal sequences, arrange those with smaller indices first), P is the sequence of indices that appears in that arrangement.

Constraints

• 1\leq N\leq 3\times 10^5
• 0\leq x_i\lt i
• 1\leq y_i\leq 10^9
• All input values are integers.

Sample Input 1

4
0 2
0 1
2 2
0 1

Sample Output 1

2 4 3 1

A_1 = (2), A_2 = (1), A_3 = (1, 2), A_4 = (1), so P=(2,4,3,1).

Sample Input 2

5
0 1
0 1
0 1
0 1
0 1

Sample Output 2

1 2 3 4 5

A_1 = A_2 = A_3 = A_4 = A_5 = (1).

Sample Input 3

10
0 305186313
1 915059758
0 105282054
1 696409999
3 185928366
3 573289179
6 254538849
3 105282054
5 696409999
8 168629803

Sample Output 3

3 8 10 5 9 6 7 1 4 2

Problem Statement

There is a circular cake that has been cut into N equal slices by its radii.

Each piece is labeled with an integer from 1 to N in clockwise order, and for each integer i with 1 \leq i \leq N, the piece i is also referred to as piece N + i.

Initially, every piece’s color is color 0.

You can perform the following operation any number of times:

• Choose integers a, b, and c such that 1 \leq a, b, c \leq N. For each integer i with 0 \leq i < b, change the color of piece a + i to color c. The cost of this operation is b + X_c.

You want each piece i (for 1 \leq i \leq N) to have color C_i. Find the minimum total cost of operations needed to achieve this.

Constraints

• 1 \leq N \leq 400
• 1 \leq C_i \leq N
• 1 \leq X_i \leq 10^9
• All input values are integers.

Sample Input 1

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

Sample Output 1

20

Let A_i denote the color of piece i. Initially, (A_1, A_2, A_3, A_4, A_5, A_6) = (0, 0, 0, 0, 0, 0).

Performing an operation with (a, b, c) = (2, 1, 4) changes (A_1, A_2, A_3, A_4, A_5, A_6) to (0, 4, 0, 0, 0, 0).

Performing an operation with (a, b, c) = (3, 3, 2) changes (A_1, A_2, A_3, A_4, A_5, A_6) to (0, 4, 2, 2, 2, 0).

Performing an operation with (a, b, c) = (1, 1, 1) changes (A_1, A_2, A_3, A_4, A_5, A_6) to (1, 4, 2, 2, 2, 0).

Performing an operation with (a, b, c) = (4, 1, 1) changes (A_1, A_2, A_3, A_4, A_5, A_6) to (1, 4, 2, 1, 2, 0).

Performing an operation with (a, b, c) = (6, 1, 5) changes (A_1, A_2, A_3, A_4, A_5, A_6) to (1, 4, 2, 1, 2, 5).

In this case, the total cost is 5 + 5 + 2 + 2 + 6 = 20.

Sample Input 2

5
1 2 3 4 5
1000000000 1000000000 1000000000 1000000000 1000000000

Sample Output 2

5000000005

Sample Input 3

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

Sample Output 3

23