Problem Statement

You are given N strings.

The i-th string S_i (1 \leq i \leq N) is either Takahashi or Aoki.

How many i are there such that S_i is equal to Takahashi?

Constraints

• 1 \leq N \leq 100
• N is an integer.
• Each S_i is Takahashi or Aoki. (1 \leq i \leq N)

Sample Input 1

3
Aoki
Takahashi
Takahashi

Sample Output 1

2

S_2 and S_3 are equal to Takahashi, while S_1 is not.

Therefore, print 2.

Sample Input 2

2
Aoki
Aoki

Sample Output 2

0

It is possible that no S_i is equal to Takahashi.

Sample Input 3

20
Aoki
Takahashi
Takahashi
Aoki
Aoki
Aoki
Aoki
Takahashi
Aoki
Aoki
Aoki
Takahashi
Takahashi
Aoki
Takahashi
Aoki
Aoki
Aoki
Aoki
Takahashi

Sample Output 3

7

Problem Statement

There are four cards with integers A,B,C,D written on them.
Determine whether a Full House can be formed by adding one card.

A set of five cards is called a Full House if and only if the following condition is satisfied:

• For two distinct integers x and y, there are three cards with x written on them and two cards with y written on them.

Constraints

• All input values are integers.
• 1 \le A,B,C,D \le 13

Sample Input 1

7 7 7 1

Sample Output 1

Yes

Adding 1 to 7,7,7,1 forms a Full House.

Sample Input 2

13 12 11 10

Sample Output 2

No

Adding anything to 13,12,11,10 does not form a Full House.

Sample Input 3

3 3 5 5

Sample Output 3

Yes

Adding 3,3,5,5 to 3 forms a Full House.
Also, adding 5 forms a Full House.

Sample Input 4

8 8 8 8

Sample Output 4

No

Adding anything to 8,8,8,8 does not form a Full House.
Note that five identical cards do not form a Full House.

Sample Input 5

1 3 4 1

Sample Output 5

No

Problem Statement

You are given a string S consisting of lowercase English letters. How many different non-empty substrings does S have?

A substring is a contiguous subsequence. For example, xxx is a substring of yxxxy but not of xxyxx.

Constraints

• S is a string of length between 1 and 100, inclusive, consisting of lowercase English letters.

Sample Input 1

yay

Sample Output 1

5

S has the following five different non-empty substrings:

• a
• y
• ay
• ya
• yay

Sample Input 2

aababc

Sample Output 2

17

Sample Input 3

abracadabra

Sample Output 3

54

Problem Statement

Given a non-negative integer X, perform the following operation for i=1,2,\dots,K in this order and find the resulting X.

• Round X off to the nearest 10^i.
  • Formally, replace X with Y that is "the largest multiple of 10^i that minimizes |Y-X|."
  • Here are some examples:
    • Rounding 273 off to the nearest 10^2 yields 300.
    • Rounding 999 off to the nearest 10^3 yields 1000.
    • Rounding 100 off to the nearest 10^{10} yields 0.
    • Rounding 1015 off to the nearest 10^1 yields 1020.

Constraints

• X and K are integers.
• 0 \le X < 10^{15}
• 1 \le K \le 15

Sample Input 1

2048 2

Sample Output 1

2100

X changes as 2048 \rightarrow 2050 \rightarrow 2100 by the operations.

Sample Input 2

1 15

Sample Output 2

0

Sample Input 3

999 3

Sample Output 3

1000

Sample Input 4

314159265358979 12

Sample Output 4

314000000000000

X may not fit into a 32-bit integer type.

Problem Statement

N people numbered 1 through N tossed a coin several times. We know that person i's tosses resulted in A_i heads and B_i tails.

Person i's success rate of the tosses is defined by \displaystyle\frac{A_i}{A_i+B_i}. Sort people 1,\ldots,N in descending order of their success rates, with ties broken in ascending order of their assigned numbers.

Constraints

• 2\leq N \leq 2\times 10^5
• 0\leq A_i, B_i\leq 10^9
• A_i+B_i \geq 1
• All input values are integers.

Sample Input 1

3
1 3
3 1
2 2

Sample Output 1

2 3 1

Person 1's success rate is 0.25, person 2's is 0.75, and person 3's is 0.5.

Sort them in descending order of their success rates to obtain the order in Sample Output.

Sample Input 2

2
1 3
2 6

Sample Output 2

1 2

Note that person 1 and 2 should be printed in ascending order of their numbers, as they have the same success rates.

Sample Input 3

4
999999999 1000000000
333333333 999999999
1000000000 999999997
999999998 1000000000

Sample Output 3

3 1 4 2

Problem Statement

You are given a permutation A=(A_1,\ldots,A_N) of (1,2,\ldots,N).
Transform A into (1,2,\ldots,N) by performing the following operation between 0 and N-1 times, inclusive:

• Operation: Choose any pair of integers (i,j) such that 1\leq i < j \leq N. Swap the elements at the i-th and j-th positions of A.

It can be proved that under the given constraints, it is always possible to transform A into (1,2,\ldots,N).

Constraints

• 2 \leq N \leq 2\times 10^5
• (A_1,\ldots,A_N) is a permutation of (1,2,\ldots,N).
• All input values are integers.

Sample Input 1

5
3 4 1 2 5

Sample Output 1

2
1 3
2 4

The operations change the sequence as follows:

• Initially, A=(3,4,1,2,5).
• The first operation swaps the first and third elements, making A=(1,4,3,2,5).
• The second operation swaps the second and fourth elements, making A=(1,2,3,4,5).

Other outputs such as the following are also considered correct:

4
2 3
3 4
1 2
2 3

Sample Input 2

4
1 2 3 4

Sample Output 2

0

Sample Input 3

3
3 1 2

Sample Output 3

2
1 2
2 3

Problem Statement

There are N houses at points (X_1,Y_1),\ldots,(X_N,Y_N) on a two-dimensional plane.

Initially, Santa Claus is at point (S_x,S_y). He will act according to the sequence (D_1,C_1),\ldots,(D_M,C_M) as follows:

• For i=1,2,\ldots,M in order, he moves as follows:
  • Let (x,y) be the point where he currently is.
    • If D_i is U, move in a straight line from (x,y) to (x,y+C_i).
    • If D_i is D, move in a straight line from (x,y) to (x,y-C_i).
    • If D_i is L, move in a straight line from (x,y) to (x-C_i,y).
    • If D_i is R, move in a straight line from (x,y) to (x+C_i,y).

Find the point where he is after completing all actions, and the number of distinct houses he passed through or arrived at during his actions. If the same house is passed multiple times, it is only counted once.

Constraints

• 1 \leq N \leq 2\times 10^5
• 1 \leq M \leq 2\times 10^5
• -10^9 \leq X_i,Y_i \leq 10^9
• The pairs (X_i,Y_i) are distinct.
• -10^9 \leq S_x,S_y \leq 10^9
• There is no house at (S_x,S_y).
• Each D_i is one of U, D, L, R.
• 1 \leq C_i \leq 10^9
• All input numbers are integers.

Sample Input 1

3 4 3 2
2 2
3 3
2 1
L 2
D 1
R 1
U 2

Sample Output 1

2 3 2

Santa Claus behaves as follows:

• D_1= L, so he moves from (3,2) to (3-2,2) in a straight line. During this, he passes through the house at (2,2).
• D_2= D, so he moves from (1,2) to (1,2-1) in a straight line.
• D_3= R, so he moves from (1,1) to (1+1,1) in a straight line. During this, he passes through the house at (2,1).
• D_4= U, so he moves from (2,1) to (2,1+2) in a straight line. During this, he passes through the house at (2,2), but it has already been passed.

The number of houses he passed or arrived during his actions is 2.

Sample Input 2

1 3 0 0
1 1
R 1000000000
R 1000000000
R 1000000000

Sample Output 2

3000000000 0 0

Be careful with overflow.

Problem Statement

In a two-dimensional plane, there are N towns and M chests. Town i is at the coordinates (X_i,Y_i), and chest i is at the coordinates (P_i,Q_i).

Takahashi will go on a trip where he starts at the origin, visits all N towns, and then returns to the origin.
It is not mandatory to visit chests, but each chest contains an accelerator. Each time he picks up an accelerator, his moving speed gets multiplied by 2.

Takahashi's initial moving speed is 1. Find the shortest time needed to complete the trip.

Constraints

• 1 \leq N \leq 12
• 0 \leq M \leq 5
• -10^9 \leq X_i,Y_i,P_i,Q_i \leq 10^9
• (0,0), (X_i,Y_i), and (P_i,Q_i) are distinct.
• All values in the input are integers.

Sample Input 1

2 1
1 1
0 1
1 0

Sample Output 1

2.5000000000

Here is one optimal way to complete the trip.

• Go the distance 1 from the origin to chest 1 at a speed of 1, taking a time of 1.
• Go the distance 1 from chest 1 to town 1 at a speed of 2, taking a time of 0.5.
• Go the distance 1 from town 1 to town 2 at a speed of 2, taking a time of 0.5.
• Go the distance 1 from town 2 to the origin at a speed of 2, taking a time of 0.5.

Sample Input 2

2 1
1 1
0 1
100 0

Sample Output 2

3.4142135624

Here is one optimal way to complete the trip.

• Go the distance 1.41\ldots from the origin to town 1 at a speed of 1, taking a time of 1.41\ldots.
• Go the distance 1 from town 1 to town 2 at a speed of 1, taking a time of 1.
• Go the distance 1 from town 2 to the origin at a speed of 1, taking a time of 1.

Sample Input 3

1 2
4 4
1 0
0 1

Sample Output 3

4.3713203436

Here is one optimal way to complete the trip.

• Go the distance 1 from the origin to chest 1 at a speed of 1, taking a time of 1.
• Go the distance 1.41\ldots from chest 1 to chest 2 at a speed of 2, taking a time of 0.707\ldots.
• Go the distance 5 from chest 2 to town 1 at a speed of 4, taking a time of 1.25.
• Go the distance 5.65\ldots from town 1 to the origin at a speed of 4, taking a time of 1.41\ldots.

Problem Statement

There is a town represented as an xy-plane, where Santa lives, along with N children numbered 1 to N. Santa's house is at coordinates (S_X,S_Y), and the house of child i\ (1\leq i\leq N) is at (X_i,Y_i).

Santa wants to deliver one present to each of the N children in numerical order. To deliver a present to child i, Santa must visit the house of child i with at least one present in hand. However, Santa can only carry up to K presents at a time, and he must return to his own house to replenish presents (there are enough presents at Santa's house).

Find the minimum distance Santa must travel to leave his house, deliver presents to all N children, and return to his house.

Constraints

• 1\leq K\leq N \leq 2\times 10^5
• -10^9\leq S_X,S_Y,X_i,Y_i \leq 10^9
• (S_X,S_Y)\neq (X_i,Y_i)
• (X_i,Y_i)\neq (X_j,Y_j)\ (i\neq j)
• All input values are integers.

Sample Input 1

3 2
1 1
3 1
1 2
3 2

Sample Output 1

9.236067977499790

In the figure above, the red circle represents Santa's house, and the circles with numbers represent the houses of the children with those numbers.

Consider Santa acting as follows:

1. Leave his house with two presents.
2. Go to child 1's house and deliver a present.
3. Return to his house and replenish one present.
4. Go to child 2's house and deliver a present.
5. Go to child 3's house and deliver a present.
6. Return to his house.

In this case, Santa travels the distance of 2+2+1+2+\sqrt{5}=7+\sqrt{5}=9.236\dots, which is the minimum.

Sample Input 2

2 1
0 1
-1 1
1 1

Sample Output 2

4.000000000000000

Sample Input 3

8 3
735867677 193944314
586260100 -192321079
95834122 802780784
418379342 -790013317
-445130206 189801569
-354684803 -49687658
-204491568 -840249197
853829789 470958158
-751917965 762048217

Sample Output 3

11347715738.116592407226562