Problem Statement

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.

Determine how many of the N boxes will be empty after D days have passed. (It can be proved that this value does not depend on which cookies Takahashi chooses each day.)

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

4

For example, Takahashi might act as follows:

• Day 1: There are cookies in the 2nd, 3rd, and 5th boxes from the left. He chooses the cookie in the 2nd box to eat.
• Day 2: There are cookies in the 3rd and 5th boxes. He chooses the cookie in the 5th box to eat.
• After two days have passed, only the 3rd box from the left contains a cookie. Therefore, four out of the five boxes are empty.

Even though Takahashi might choose differently on each day than in this example, there will still be four empty boxes after two days. Therefore, the answer is 4.

Sample Input 2

3 3
@@@

Sample Output 2

3

Sample Input 3

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

Sample Output 3

7

Problem Statement

In a certain programming contest, T-shirts are awarded to participants according to the following rules.

• All participants who ranked A-th or higher get a T-shirt.
• Additionally, from the participants who ranked between (A+1)-th and B-th (inclusive), C participants chosen uniformly at random get a T-shirt.

There were 1000 participants in this contest, and all of them got different ranks.
Iroha-chan, who participated in this contest, ranked X-th.
Find the probability that she gets a T-shirt.

Constraints

• All values in input are integers.
• 1 \le A < B \le 1000
• 1 \le C \le B-A
• 1 \le X \le 1000

Sample Input 1

30 500 20 103

Sample Output 1

0.042553191489

Iroha-chan ranked 103-rd.
She will get a T-shirt if she is among the 20 participants chosen uniformly at random from the 470 participants who ranked between 31-st and 500-th, which happens with probability \frac{20}{470}=0.04255319\dots.

Sample Input 2

50 500 100 1

Sample Output 2

1.000000000000

Iroha-chan ranked 1-st. This time, she is guaranteed to get a T-shirt.

Sample Input 3

1 2 1 1000

Sample Output 3

0.000000000000

Iroha-chan ranked 1000-th. This time, she will never get a T-shirt.

Problem Statement

Takahashi bought a table clock.
The clock shows the time as shown in Figure 1 at \mathrm{AB}:\mathrm{CD} in the 24-hour system.
For example, the clock in Figure 2 shows 7:58.

The format of the time is formally described as follows.
Suppose that the current time is m minutes past h in the 24-hour system. Here, the 24-hour system represents the hour by an integer between 0 and 23 (inclusive), and the minute by an integer between 0 and 59 (inclusive).
Let A be the tens digit of h, B be the ones digit of h, C be the tens digit of m, and D be the ones digit of m. (Here, if h has only one digit, we consider that it has a leading zero; the same applies to m.)
Then, the clock shows A in its top-left, B in its bottom-left, C in its top-right, and D in its bottom-right.

Takahashi has decided to call a time a confusing time if it satisfies the following condition:

• after swapping the top-right and bottom-left digits on the clock, it still reads a valid time in the 24-hour system.

For example, the clock in Figure 3 shows 20:13. After swapping its top-right and bottom-left digits, it reads 21:03. Thus, 20:13 is a confusing time.

The clock now shows H:M.
Find the next confusing time (including now) in the 24-hour system.

Constraints

• 0 \leq H \leq 23
• 0 \leq M \leq 59
• H and M are integers.

Sample Input 1

1 23

Sample Output 1

1 23

1:23 is a confusing time because, after swapping its top-right and bottom-left digits on the clock, it reads 2:13.
Thus, the answer is 1:23.
Your answer is considered correct even if you print 01 23 with a leading zero.

Sample Input 2

19 57

Sample Output 2

20 0

The next confusing time after 19:57 is 20:00.

Sample Input 3

20 40

Sample Output 3

21 0

Note that 24:00 is an invalid notation in the 24-hour system.

Problem Statement

You are given N sequences numbered 1 to N.
Sequence i has a length of L_i and its j-th element (1 \leq j \leq L_i) is a_{i,j}.

Sequence i and Sequence j are considered the same when L_i = L_j and a_{i,k} = a_{j,k} for every k (1 \leq k \leq L_i).
How many different sequences are there among Sequence 1 through Sequence N?

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq L_i \leq 2 \times 10^5 (1 \leq i \leq N)
• 0 \leq a_{i,j} \leq 10^{9} (1 \leq i \leq N, 1 \leq j \leq L_i)
• The total number of elements in the sequences, \sum_{i=1}^N L_i, does not exceed 2 \times 10^5.
• All values in input are integers.

Sample Input 1

4
2 1 2
2 1 1
2 2 1
2 1 2

Sample Output 1

3

Sample Input 1 contains four sequences:

• Sequence 1 : (1, 2)
• Sequence 2 : (1, 1)
• Sequence 3 : (2, 1)
• Sequence 4 : (1, 2)

Except that Sequence 1 and Sequence 4 are the same, these sequences are pairwise different, so we have three different sequences.

Sample Input 2

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

Sample Output 2

4

Sample Input 2 contains five sequences:

• Sequence 1 : (1)
• Sequence 2 : (1)
• Sequence 3 : (2)
• Sequence 4 : (1, 1)
• Sequence 5 : (1, 1, 1)

Sample Input 3

1
1 1

Sample Output 3

1

Problem Statement

In the Kingdom of AtCoder, a week consists of A+B days, with the first through A-th days being holidays and the (A+1)-th through (A+B)-th being weekdays.

Takahashi has N plans, and the i-th plan is scheduled D_i days later.

He has forgotten what day of the week it is today. Determine if it is possible for all of his N plans to be scheduled on holidays.

Constraints

• 1\leq N\leq 2\times 10^5
• 1\leq A,B\leq 10^9
• 1\leq D_1<D_2<\ldots<D_N\leq 10^9

Sample Input 1

3 2 5
1 2 9

Sample Output 1

Yes

In this input, a week consists of seven days, with the first through second days being holidays and the third through seventh days being weekdays.

Let us assume today is the seventh day of the week. In this case, one day later would be the first day of the week, two days later would be the second day of the week, and nine days later would also be the second day of the week, making all plans scheduled on holidays. Therefore, it is possible for all of Takahashi's N plans to be scheduled on holidays.

Sample Input 2

2 5 10
10 15

Sample Output 2

No

Sample Input 3

4 347 347
347 700 705 710

Sample Output 3

Yes

Problem Statement

A positive integer x is called a 321-like Number when it satisfies the following condition. This definition is the same as the one in Problem A.

• The digits of x are strictly decreasing from top to bottom.
• In other words, if x has d digits, it satisfies the following for every integer i such that 1 \le i < d:
  • (the i-th digit from the top of x) > (the (i+1)-th digit from the top of x).

Note that all one-digit positive integers are 321-like Numbers.

For example, 321, 96410, and 1 are 321-like Numbers, but 123, 2109, and 86411 are not.

Find the K-th smallest 321-like Number.

Constraints

• All input values are integers.
• 1 \le K
• At least K 321-like Numbers exist.

Sample Input 1

15

Sample Output 1

32

The 321-like Numbers are (1,2,3,4,5,6,7,8,9,10,20,21,30,31,32,40,\dots) from smallest to largest.
The 15-th smallest of them is 32.

Sample Input 2

321

Sample Output 2

9610

Sample Input 3

777

Sample Output 3

983210

Problem Statement

There are N rest areas around a lake.
The rest areas are numbered 1, 2, ..., N in clockwise order.
It takes A_i steps to walk clockwise from rest area i to rest area i+1 (where rest area N+1 refers to rest area 1).
The minimum number of steps required to walk clockwise from rest area s to rest area t (s \neq t) is a multiple of M.
Find the number of possible pairs (s,t).

Constraints

• All input values are integers
• 2 \le N \le 2 \times 10^5
• 1 \le A_i \le 10^9
• 1 \le M \le 10^6

Sample Input 1

4 3
2 1 4 3

Sample Output 1

4

• The minimum number of steps to walk clockwise from rest area 1 to rest area 2 is 2, which is not a multiple of 3.
• The minimum number of steps to walk clockwise from rest area 1 to rest area 3 is 3, which is a multiple of 3.
• The minimum number of steps to walk clockwise from rest area 1 to rest area 4 is 7, which is not a multiple of 3.
• The minimum number of steps to walk clockwise from rest area 2 to rest area 3 is 1, which is not a multiple of 3.
• The minimum number of steps to walk clockwise from rest area 2 to rest area 4 is 5, which is not a multiple of 3.
• The minimum number of steps to walk clockwise from rest area 2 to rest area 1 is 8, which is not a multiple of 3.
• The minimum number of steps to walk clockwise from rest area 3 to rest area 4 is 4, which is not a multiple of 3.
• The minimum number of steps to walk clockwise from rest area 3 to rest area 1 is 7, which is not a multiple of 3.
• The minimum number of steps to walk clockwise from rest area 3 to rest area 2 is 9, which is a multiple of 3.
• The minimum number of steps to walk clockwise from rest area 4 to rest area 1 is 3, which is a multiple of 3.
• The minimum number of steps to walk clockwise from rest area 4 to rest area 2 is 5, which is not a multiple of 3.
• The minimum number of steps to walk clockwise from rest area 4 to rest area 3 is 6, which is a multiple of 3.

Therefore, there are four possible pairs (s,t).

Sample Input 2

2 1000000
1 1

Sample Output 2

0

Sample Input 3

9 5
9 9 8 2 4 4 3 5 3

Sample Output 3

11

Problem Statement

In AtCoder Kingdom, N kinds of takoyakis (ball-shaped Japanese food) are sold. A takoyaki of the i-th kind is sold for A_i yen.

Takahashi will buy at least one takoyaki in total. He is allowed to buy multiple takoyakis of the same kind.

Find the K-th lowest price that Takahashi may pay. Here, if there are multiple sets of takoyakis that cost the same price, the price is counted only once.

Constraints

• 1 \le N \le 10
• 1 \le K \le 2 \times 10^5
• 1 \le A_i \le 10^9
• All values in the input are integers.

Sample Input 1

4 6
20 25 30 100

Sample Output 1

50

The four kinds of takoyakis sold in AtCoder Kingdom cost 20 yen, 25 yen, 30 yen, and 100 yen.

The six lowest prices that Takahashi may pay are 20 yen, 25 yen, 30 yen, 40 yen, 45 yen, and 50 yen. Thus, the answer is 50.

Note that at least one takoyaki must be bought.

Sample Input 2

2 10
2 1

Sample Output 2

10

Note that a price is not counted more than once even if there are multiple sets of takoyakis costing that price.

Sample Input 3

10 200000
955277671 764071525 871653439 819642859 703677532 515827892 127889502 881462887 330802980 503797872

Sample Output 3

5705443819

Problem Statement

KEYENCE is famous for quick delivery.

In this problem, the calendar proceeds as Day 1, Day 2, Day 3, \dots.

There are orders 1,2,\dots,N, and it is known that order i will be placed on Day T_i.
For these orders, shipping is carried out according to the following rules.

• At most K orders can be shipped together.
• Order i can only be shipped on Day T_i or later.
• Once a shipment is made, the next shipment cannot be made until X days later.
  • That is, if a shipment is made on Day a, the next shipment can be made on Day a+X.

For each day that passes from order placement to shipping, dissatisfaction accumulates by 1 per day.
That is, if order i is shipped on Day S_i, the dissatisfaction accumulated for that order is (S_i - T_i).

Find the minimum possible total dissatisfaction accumulated over all orders when you optimally schedule the shipping dates.

Constraints

• All input values are integers.
• 1 \le K \le N \le 100
• 1 \le X \le 10^9
• 1 \le T_1 \le T_2 \le \dots \le T_N \le 10^{12}

Sample Input 1

5 2 3
1 5 6 10 12

Sample Output 1

2

For example, by scheduling shipments as follows, we can achieve a total dissatisfaction of 2, which is the minimum possible.

• Ship order 1 on Day 1.
  • This results in dissatisfaction of (1-1) = 0, and the next shipment can be made on Day 4.
• Ship orders 2 and 3 on Day 6.
  • This results in dissatisfaction of (6-5) + (6-6) = 1, and the next shipment can be made on Day 9.
• Ship order 4 on Day 10.
  • This results in dissatisfaction of (10-10) = 0, and the next shipment can be made on Day 13.
• Ship order 5 on Day 13.
  • This results in dissatisfaction of (13-12) = 1, and the next shipment can be made on Day 16.

Sample Input 2

1 1 1000000000
1000000000000

Sample Output 2

0

Sample Input 3

15 4 5
1 3 3 6 6 6 10 10 10 10 15 15 15 15 15

Sample Output 3

35