Problem Statement

In an electric circuit, when two resistors R_1 and R_2 are connected in parallel, the equivalent resistance R_3 can be derived from the following formula:

• \frac{1}{R_1} + \frac{1}{R_2} = \frac{1}{R_3}

Given R_1 and R_2, find R_3.

Constraints

• 1 \leq R_1, R_2 \leq 100
• R_1 and R_2 are integers.

Sample Input 1

2 3

Sample Output 1

1.2000000000

Sample Input 2

100 99

Sample Output 2

49.7487437186

Problem Statement

You are given a string S consisting of letters b, d, p and q. Determine whether S is a mirror string.

Here, a mirror string is a string S such that the following sequence of operations on S results in the same string S:

1. Reverse the order of the characters in S.

2. Replace each occurrence of b by d, d by b, p by q, and q by p, simultaneously.

Constraints

• 1 \leq |S| \leq 10^5
• S consists of letters b, d, p, and q.

Sample Input 1

pdbq

Sample Output 1

Yes

Sample Input 2

ppqb

Sample Output 2

No

Problem Statement

Kode Festival is an anual contest where the hardest stone in the world is determined. (Kode is a Japanese word for "hardness".)

This year, 2^N stones participated. The hardness of the i-th stone is A_i.

In the contest, stones are thrown at each other in a knockout tournament.

When two stones with hardness X and Y are thrown at each other, the following will happen:

• When X > Y: The stone with hardness Y will be destroyed and eliminated. The hardness of the stone with hardness X will become X-Y.

• When X = Y: One of the stones will be destroyed and eliminated. The hardness of the other stone will remain the same.

• When X < Y: The stone with hardness X will be destroyed and eliminated. The hardness of the stone with hardness Y will become Y-X.

The 2^N stones will fight in a knockout tournament as follows:

1. The following pairs will fight: (the 1-st stone versus the 2-nd stone), (the 3-rd stone versus the 4-th stone), ...

2. The following pairs will fight: (the winner of (1-st versus 2-nd) versus the winner of (3-rd versus 4-th)), (the winner of (5-th versus 6-th) versus the winner of (7-th versus 8-th)), ...

3. And so forth, until there is only one stone remaining.

Determine the eventual hardness of the last stone remaining.

Constraints

• 1 \leq N \leq 18
• 1 \leq A_i \leq 10^9
• A_i is an integer.

Sample Input 1

2
1
3
10
19

Sample Output 1

7

Sample Input 2

3
1
3
2
4
6
8
100
104

Sample Output 2

2

Problem Statement

A 3×3 grid with a integer written in each square, is called a magic square if and only if the integers in each row, the integers in each column, and the integers in each diagonal (from the top left corner to the bottom right corner, and from the top right corner to the bottom left corner), all add up to the same sum.

You are given the integers written in the following three squares in a magic square:

• The integer A at the upper row and left column
• The integer B at the upper row and middle column
• The integer C at the middle row and middle column

Determine the integers written in the remaining squares in the magic square.

It can be shown that there exists a unique magic square consistent with the given information.

Constraints

• 0 \leq A, B, C \leq 100

Sample Input 1

8
3
5

Sample Output 1

8 3 4
1 5 9
6 7 2

Sample Input 2

1
1
1

Sample Output 2

1 1 1
1 1 1
1 1 1

Problem Statement

Takahashi is drawing a segment on grid paper.

From a certain square, a square that is x squares to the right and y squares above, is denoted as square (x, y).

When Takahashi draws a segment connecting the lower left corner of square (A, B) and the lower left corner of square (C, D), find the number of the squares crossed by the segment.

Here, the segment is said to cross a square if the segment has non-empty intersection with the region within the square, excluding the boundary.

Constraints

• 1 \leq A, B, C, D \leq 10^9
• At least one of A \neq C and B \neq D holds.

Sample Input 1

1 1 3 4

Sample Output 1

4

Sample Input 2

2 3 10 7

Sample Output 2

8

Problem Statement

We have a cord whose length is a positive integer. We will perform the following condition until the length of the cord becomes at most 2:

• Operation: Cut the rope at two positions to obtain three cords, each with a length of a positive integer. Among these, discard one with the longest length and one with the shortest length, and keep the remaining one.

Let f(N) be the maximum possible number of times to perform this operation, starting with a cord with the length N.

You are given a positive integer X. Find the maximum integer N such that f(N)=X.

Constraints

• 1 \leq X \leq 40

Sample Input 1

2

Sample Output 1

14

Problem Statement

You have N cups and 1 ball.

The cups are arranged in a row, from left to right.

You turned down all the cups, then inserted the ball into the leftmost cup.

Then, you will perform the following Q operations:

• The i-th operation: swap the positions of the A_i-th and B_i-th cups from the left. If one of these cups contains the ball, the ball will also move.

Since you are a magician, you can cast a magic described below:

• Magic: When the ball is contained in the i-th cup from the left, teleport the ball into the adjacent cup (that is, the (i-1)-th or (i+1)-th cup, if they exist).

The magic can be cast before the first operation, between two operations, or after the last operation, but you are allowed to cast it at most once during the whole process.

Find the number of cups with a possibility of containing the ball after all the operations and possibly casting the magic.

Constraints

• 2 \leq N \leq 10^5
• 1 \leq Q \leq 10^5
• 1 \leq A_i < B_i \leq N

Sample Input 1

10 3
1 3
2 4
4 5

Sample Output 1

4

Sample Input 2

20 3
1 7
8 20
1 19

Sample Output 2

5

Problem Statement

Takahashi recorded his daily life for the last few days as a integer sequence of length 2N, as follows:

• a_1, b_1, a_2, b_2, ... , a_N, b_N

This means that, starting from a certain time T, he was:

• sleeping for exactly a_1 seconds
• then awake for exactly b_1 seconds
• then sleeping for exactly a_2 seconds
• :
• then sleeping for exactly a_N seconds
• then awake for exactly b_N seconds

In this record, he waked up N times.

Takahashi is wondering how many times he waked up early during the recorded period.

Here, he is said to wake up early if he wakes up between 4:00 AM and 7:00 AM, inclusive.

If he wakes up more than once during this period, each of these awakenings is counted as waking up early.

Unfortunately, he forgot the time T.

Find the maximum possible number of times he waked up early during the recorded period.

For your information, a day consists of 86400 seconds, and the length of the period between 4:00 AM and 7:00 AM is 10800 seconds.

Constraints

• 1 \leq N \leq 10^5
• 1 \leq a_i, b_i \leq 10^5
• a_i and b_i are integers.

Sample Input 1

3
28800 57600
28800 57600
57600 28800

Sample Output 1

2

Sample Input 2

10
28800 57600
4800 9600
6000 1200
600 600
300 600
5400 600
6000 5760
6760 2880
6000 12000
9000 600

Sample Output 2

5

Problem Statement

There are N persons, conveniently numbered 1 through N. They will take 3y3s Challenge for N-1 seconds.

During the challenge, each person must look at each of the N-1 other persons for 1 seconds, in some order.

If any two persons look at each other during the challenge, the challenge ends in failure.

Find the order in which each person looks at each of the N-1 other persons, to be successful in the challenge.

Constraints

• 2 \leq N \leq 100

Sample Input 1

7

Sample Output 1

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

Sample Input 2

2

Sample Output 2

-1

Problem Statement

We have an N×N checkerboard.

From the square at the upper left corner, a square that is i squares to the right and j squares below is denoted as (i, j). Particularly, the square at the upper left corner is denoted as (0, 0).

Each square (i, j) such that i+j is even, is colored black, and the other squares are colored white.

We will satisfy the following condition by painting some of the white squares:

• Any black square can be reached from square (0, 0) by repeatedly moving to a black square that shares a side with the current square.

Achieve the objective by painting at most 170000 squares black.

Constraints

• 1 \leq N \leq 1,000

Sample Input 1

2

Sample Output 1

1
1 0

Sample Input 2

4

Sample Output 2

3
0 1
2 1
2 3

Problem Statement

There is a tree with N vertices, numbered 1 through N.

The i-th of the N-1 edges connects the vertices p_i and q_i.

Among the sequences of distinct vertices v_1, v_2, ..., v_M that satisfy the following condition, find the maximum value of M.

• For every 1 \leq i < M, the path connecting the vertices v_i and v_{i+1} do not contain any vertex in v, except for v_i and v_{i+1}.

Constraints

• 2 \leq N \leq 10^5
• 1 \leq p_i, q_i \leq N
• The given graph is a tree.

Sample Input 1

4
1 2
2 3
2 4

Sample Output 1

3

Sample Input 2

10
7 9
1 2
6 4
8 1
3 7
6 5
2 10
9 6
2 6

Sample Output 2

8