Problem Statement

Let us define a function f as f(x) = x^2 + 2x + 3.
Given an integer t, find f(f(f(t)+t)+f(f(t))).
Here, it is guaranteed that the answer is an integer not greater than 2 \times 10^9.

Constraints

• t is an integer between 0 and 10 (inclusive).

Sample Input 1

0

Sample Output 1

1371

The answer is computed as follows.

• f(t) = t^2 + 2t + 3 = 0 \times 0 + 2 \times 0 + 3 = 3
• f(t)+t = 3 + 0 = 3
• f(f(t)+t) = f(3) = 3 \times 3 + 2 \times 3 + 3 = 18
• f(f(t)) = f(3) = 18
• f(f(f(t)+t)+f(f(t))) = f(18+18) = f(36) = 36 \times 36 + 2 \times 36 + 3 = 1371

Sample Input 2

3

Sample Output 2

722502

Sample Input 3

10

Sample Output 3

1111355571

Problem Statement

You are given positive integers N and K, and a sequence of length N, A=(A_1,A_2,\ldots,A_N).

Extract all elements of A that are multiples of K, divide them by K, and print the quotients.

Constraints

• 1\leq N,K\leq 100
• 1\leq A_1 < A_2 < \ldots < A_N \leq 100
• A has at least one multiple of K.
• All given numbers are integers.

Sample Input 1

5 2
2 5 6 7 10

Sample Output 1

1 3 5

The multiples of 2 among the elements in A are 2, 6, and 10. Divide them by 2 to get 1, 3, and 5, and print them in ascending order with spaces in between.

Sample Input 2

3 1
3 4 7

Sample Output 2

3 4 7

Sample Input 3

5 10
50 51 54 60 65

Sample Output 3

5 6

Problem Statement

You are given an integer N and a sequence S=(S_1,\ldots,S_N) of length N.

Find a sequence A=(A_1,\ldots,A_N) of length N that satisfies the following condition for all k=1,\ldots,N:

• A_1+A_2+\ldots+A_k = S_k.

Such a sequence A always exists and is unique.

Constraints

• 1 \leq N \leq 10
• -10^9\leq S_i \leq 10^9
• All values in the input are integers.

Sample Input 1

3
3 4 8

Sample Output 1

3 1 4

The sequence in the output actually satisfies all the conditions:

• A_1=3=S_1;
• A_1+A_2=3+1=4=S_2;
• A_1+A_2+A_3=3+1+4=8=S_3.

Sample Input 2

10
314159265 358979323 846264338 -327950288 419716939 -937510582 97494459 230781640 628620899 -862803482

Sample Output 2

314159265 44820058 487285015 -1174214626 747667227 -1357227521 1035005041 133287181 397839259 -1491424381

Problem Statement

There are N people. The family name and given name of the i-th person (1 \leq i \leq N) are S_i and T_i, respectively.

Determine whether there is a pair of people with the same family and given names. In other words, determine whether there is a pair of integers (i,j) such that 1 \leq i \lt j \leq N, S_i=S_j, and T_i=T_j.

Constraints

• 2 \leq N \leq 1000
• N is an integer.
• Each of S_i and T_i is a string of length between 1 and 10 (inclusive) consisting of English lowercase letters.

Sample Input 1

3
tanaka taro
sato hanako
tanaka taro

Sample Output 1

Yes

The first and third persons have the same family and given names.

Sample Input 2

3
saito ichiro
saito jiro
saito saburo

Sample Output 2

No

No two persons have the same family and given names.

Sample Input 3

4
sypdgidop bkseq
bajsqz hh
ozjekw mcybmtt
qfeysvw dbo

Sample Output 3

No

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

Person 0, Person 1, \ldots, and Person (N-1) are sitting around a turntable in their counterclockwise order, evenly spaced. Dish p_i is in front of Person i on the table.
You may perform the following operation 0 or more times:

• Rotate the turntable by one N-th of a counterclockwise turn. As a result, the dish that was in front of Person i right before the rotation is now in front of Person (i+1) \bmod N.

When you are finished, Person i is happy if Dish i is in front of Person (i-1) \bmod N, Person i, or Person (i+1) \bmod N.
Find the maximum possible number of happy people.

Constraints

• 3 \leq N \leq 2 \times 10^5
• 0 \leq p_i \leq N-1
• p_i \neq p_j if i \neq j.
• All values in input are integers.

Sample Input 1

4
1 2 0 3

Sample Output 1

4

The figure below shows the table after one operation.

Here, there are four happy people:

• Person 0 is happy because Dish 0 is in front of Person 3\ (=(0-1) \bmod 4);
• Person 1 is happy because Dish 1 is in front of Person 1\ (=1);
• Person 2 is happy because Dish 2 is in front of Person 2\ (=2);
• Person 3 is happy because Dish 3 is in front of Person 0\ (=(3+1) \bmod 4).

There cannot be five or more happy people, so the answer is 4.

Sample Input 2

3
0 1 2

Sample Output 2

3

Sample Input 3

10
3 9 6 1 7 2 8 0 5 4

Sample Output 3

5

Problem Statement

A superman, Takahashi, is about to jump off the roof of a building to help a person in trouble on the ground. Takahashi's planet has a constant value g that represents the strength of gravity, and the time it takes for him to reach the ground after starting to fall is \frac{A}{\sqrt{g}}.

It is now time 0, and g = 1. Takahashi will perform the following operation as many times as he wants (possibly zero).

• Use a superpower to increase the value of g by 1. This takes a time of B.

Then, he will jump off the building. After starting to fall, he cannot change the value of g. Additionally, we only consider the time it takes to perform the operation and fall.

Find the earliest time Takahashi can reach the ground.

Constraints

• 1 \leq A \leq 10^{18}
• 1 \leq B \leq 10^{18}
• All values in the input are integers.

Sample Input 1

10 1

Sample Output 1

7.7735026919

• If he performs the operation zero times, he will reach the ground at time 1\times 0+\frac{10}{\sqrt{1}} = 10.
• If he performs the operation once, he will reach the ground at time 1\times 1+\frac{10}{\sqrt{2}} \fallingdotseq 8.07.
• If he performs the operation twice, he will reach the ground at time 1\times 2+\frac{10}{\sqrt{3}} \fallingdotseq 7.77.
• If he performs the operation three times, he will reach the ground at time 1\times 3+\frac{10}{\sqrt{4}} = 8.

Performing the operation four or more times will only delay the time to reach the ground. Therefore, it is optimal to perform the operation twice before jumping off, and the answer is 2+\frac{10}{\sqrt{3}}.

Sample Input 2

5 10

Sample Output 2

5.0000000000

It is optimal not to perform the operation at all.

Sample Input 3

1000000000000000000 100

Sample Output 3

8772053214538.5976562500

Problem Statement

We have a sequence of length N consisting of integers between 0 and M, inclusive: A=(A_1,A_2,\dots,A_N).

Snuke will perform the following operations 1 and 2 in order.

1. For each i such that A_i=0, independently choose a uniform random integer between 1 and M, inclusive, and replace A_i with that integer.
2. Sort A in ascending order.

Print the expected value of A_K after the two operations, modulo 998244353.

Constraints

• 1\leq K \leq N \leq 2000
• 1\leq M \leq 2000
• 0\leq A_i \leq M
• All values in the input are integers.

Sample Input 1

3 5 2
2 0 4

Sample Output 1

3

In the operation 1, Snuke will replace A_2 with an integer between 1 and 5. Let x be this integer.

• If x=1 or 2, we will have A_2=2 after the two operations.
• If x=3, we will have A_2=3 after the two operations.
• If x=4 or 5, we will have A_2=4 after the two operations.

Thus, the expected value of A_2 is \frac{2+2+3+4+4}{5}=3.

Sample Input 2

2 3 1
0 0

Sample Output 2

221832080

The expected value is \frac{14}{9}.

Sample Input 3

10 20 7
6 5 0 2 0 0 0 15 0 0

Sample Output 3

617586310

Problem Statement

You are given integers X and Y, which satisfy at least one of X \neq 0 and Y \neq 0.
Find a pair of integers (A, B) that satisfies all of the following conditions. If no such pair exists, report so.

• -10^{18} \leq A, B \leq 10^{18}
• The area of the triangle with vertices at points (0, 0), (X, Y), (A, B) on the xy-plane is 1.

Constraints

• -10^{17} \leq X, Y \leq 10^{17}
• (X, Y) \neq (0, 0)
• X and Y are integers.

Sample Input 1

3 5

Sample Output 1

1 1

The area of the triangle with vertices at points (0, 0), (3, 5), (1, 1) is 1. Thus, (A, B) = (1, 1) satisfies the conditions.

Sample Input 2

-2 0

Sample Output 2

0 1

Sample Input 3

8752654402832944 -6857065241301125

Sample Output 3

-1