Problem Statement

A fruit store sells apples.
You may perform the following operations as many times as you want in any order:

• Buy one apple for X yen (the currency in Japan).
• Buy three apples for Y yen.

How much yen do you need to pay to obtain exactly N apples?

Constraints

• 1 \leq X \leq Y \leq 100
• 1 \leq N \leq 100
• All values in input are integers.

Sample Input 1

10 25 10

Sample Output 1

85

Buy three apples for 25 yen three times and one apple for 10 yen, and you will obtain exactly 10 apples for a total of 85 yen.
You cannot obtain exactly 10 apples for a lower cost, so the answer is 85 yen.

Sample Input 2

10 40 10

Sample Output 2

100

It is optimal to buy an apple for 10 yen 10 times.

Sample Input 3

100 100 2

Sample Output 3

200

The only way to obtain exactly 2 apples is to buy an apple for 100 yen twice.

Sample Input 4

100 100 100

Sample Output 4

3400

Problem Statement

We will hand out a total of K cards to N people numbered 1, 2, \ldots, N.

Beginning with Person A, we will give the cards one by one to the people in this order: A, A+1, A+2, \ldots, N, 1, 2, \ldots. Who will get the last card?

Formally, after Person x(1 \leq x < N) gets a card, Person x+1 will get a card. After Person N gets a card, Person 1 gets a card.

Constraints

• 1 \leq N,K \leq 1000
• 1 \leq A \leq N
• All values in input are integers.

Sample Input 1

3 3 2

Sample Output 1

1

The cards are given to Person 2, 3, 1 in this order.

Sample Input 2

1 100 1

Sample Output 2

1

Sample Input 3

3 14 2

Sample Output 3

3

Problem Statement

Naohiro had N+1 consecutive integers, one of each, but he lost one of them.

The remaining N integers are given in arbitrary order as A_1,\ldots,A_N. Find the lost integer.

The given input guarantees that the lost integer is uniquely determined.

Constraints

• 2 \leq N \leq 100
• 1 \leq A_i \leq 1000
• All input values are integers.
• The lost integer is uniquely determined.

Sample Input 1

3
2 3 5

Sample Output 1

4

Naohiro originally had four integers, 2,3,4,5, then lost 4, and now has 2,3,5.

Print the lost integer, 4.

Sample Input 2

8
3 1 4 5 9 2 6 8

Sample Output 2

7

Sample Input 3

16
152 153 154 147 148 149 158 159 160 155 156 157 144 145 146 150

Sample Output 3

151

Problem Statement

You are given a string S. Find the maximum length of a contiguous substring of S that is a palindrome.
Note that there is always a contiguous substring of S that is a palindrome.

Constraints

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

Sample Input 1

TOYOTA

Sample Output 1

5

TOYOT, a contiguous substring of TOYOTA, is a palindrome of length 5.
TOYOTA, the only length-6 contiguous substring of TOYOTA, is not a palindrome, so print 5.

Sample Input 2

ABCDEFG

Sample Output 2

1

Every contiguous substring of length 1 is a palindrome.

Sample Input 3

AAAAAAAAAA

Sample Output 3

10

Problem Statement

On an xy-coordinate plane, is there a lattice point whose distances from two lattice points (x_1, y_1) and (x_2, y_2) are both \sqrt{5}?

Notes

A point on an xy-coordinate plane whose x and y coordinates are both integers is called a lattice point.
The distance between two points (a, b) and (c, d) is defined to be the Euclidean distance between them, \sqrt{(a - c)^2 + (b-d)^2}.

The following figure illustrates an xy-plane with a black circle at (0, 0) and white circles at the lattice points whose distances from (0, 0) are \sqrt{5}. (The grid shows where either x or y is an integer.)

Constraints

• -10^9 \leq x_1 \leq 10^9
• -10^9 \leq y_1 \leq 10^9
• -10^9 \leq x_2 \leq 10^9
• -10^9 \leq y_2 \leq 10^9
• (x_1, y_1) \neq (x_2, y_2)
• All values in input are integers.

Sample Input 1

0 0 3 3

Sample Output 1

Yes

• The distance between points (2,1) and (x_1, y_1) is \sqrt{(0-2)^2 + (0-1)^2} = \sqrt{5};
• the distance between points (2,1) and (x_2, y_2) is \sqrt{(3-2)^2 + (3-1)^2} = \sqrt{5};
• point (2, 1) is a lattice point,

so point (2, 1) satisfies the condition. Thus, Yes should be printed.
One can also assert in the same way that (1, 2) also satisfies the condition.

Sample Input 2

0 1 2 3

Sample Output 2

No

No lattice point satisfies the condition, so No should be printed.

Sample Input 3

1000000000 1000000000 999999999 999999999

Sample Output 3

Yes

Point (10^9 + 1, 10^9 - 2) and point (10^9 - 2, 10^9 + 1) satisfy the condition.

Problem Statement

This problem is an easier version of Problem G.

There is a slot machine with three reels.
The arrangement of symbols on the i-th reel is represented by the string S_i. Here, S_i is a string of length M consisting of digits.

Each reel has a corresponding button. For each non-negative integer t, Takahashi can either choose and press one button or do nothing exactly t seconds after the reels start spinning.
If he presses the button corresponding to the i-th reel exactly t seconds after the reels start spinning, the i-th reel will stop and display the ((t \bmod M)+1)-th character of S_i.
Here, t \bmod M denotes the remainder when t is divided by M.

Takahashi wants to stop all the reels so that all the displayed characters are the same.
Find the minimum possible number of seconds from the start of the spin until all the reels are stopped so that his goal is achieved.
If this is impossible, report that fact.

Constraints

• 1 \leq M \leq 100
• M is an integer.
• S_i is a string of length M consisting of digits.

Sample Input 1

10
1937458062
8124690357
2385760149

Sample Output 1

6

Takahashi can stop each reel as follows so that 6 seconds after the reels start spinning, all the reels display 8.

• Press the button corresponding to the second reel 0 seconds after the reels start spinning. The second reel stops and displays 8, the ((0 \bmod 10)+1=1)-st character of S_2.
• Press the button corresponding to the third reel 2 seconds after the reels start spinning. The third reel stops and displays 8, the ((2 \bmod 10)+1=3)-rd character of S_3.
• Press the button corresponding to the first reel 6 seconds after the reels start spinning. The first reel stops and displays 8, the ((6 \bmod 10)+1=7)-th character of S_1.

There is no way to make the reels display the same character in 5 or fewer seconds, so print 6.

Sample Input 2

20
01234567890123456789
01234567890123456789
01234567890123456789

Sample Output 2

20

Note that he must stop all the reels and make them display the same character.

Sample Input 3

5
11111
22222
33333

Sample Output 3

-1

It is impossible to stop the reels so that all the displayed characters are the same.
In this case, print -1.

Problem Statement

You are given a sequence A = (A_1, A_2, \dots, A_N) of length N consisting of positive integers, and integers x and y.
Determine whether it is possible to place N+1 points p_1, p_2, \dots, p_N, p_{N+1} in the xy-coordinate plane to satisfy all of the following conditions. (It is allowed to place two or more points at the same coordinates.)

• p_1 = (0, 0).
• p_2 = (A_1, 0).
• p_{N+1} = (x, y).
• The distance between the points p_i and p_{i+1} is A_i. (1 \leq i \leq N)
• The segments p_i p_{i+1} and p_{i+1} p_{i+2} form a 90 degree angle. (1 \leq i \leq N - 1)

Constraints

• 2 \leq N \leq 10^3
• 1 \leq A_i \leq 10
• |x|, |y| \leq 10^4
• All values in the input are integers.

Sample Input 1

3 -1 1
2 1 3

Sample Output 1

Yes

The figure below shows a placement where p_1 = (0, 0), p_2 = (2, 0), p_3 = (2, 1), and p_4 = (-1, 1). All conditions in the Problem Statement are satisfied.

Sample Input 2

5 2 0
2 2 2 2 2

Sample Output 2

Yes

Letting p_1 = (0, 0), p_2 = (2, 0), p_3 = (2, 2), p_4 = (0, 2), p_5 = (0, 0), and p_6 = (2, 0) satisfies all the conditions. Note that multiple points may be placed at the same coordinates.

Sample Input 3

4 5 5
1 2 3 4

Sample Output 3

No

Sample Input 4

3 2 7
2 7 4

Sample Output 4

No

Sample Input 5

10 8 -7
6 10 4 1 5 9 8 6 5 1

Sample Output 5

Yes

Problem Statement

Find \displaystyle \sum_{k=0}^{10^{100}} \left \lfloor \frac{X}{10^k} \right \rfloor.

Notes

\lfloor A \rfloor denotes the value of A truncated to an integer.

Constraints

• X is an integer.
• 1 \le X < 10^{500000}

Sample Input 1

1225

Sample Output 1

1360

The value we seek is 1225+122+12+1+0+0+\dots+0=1360.

Sample Input 2

99999

Sample Output 2

111105

Beware of carries.

Sample Input 3

314159265358979323846264338327950288419716939937510

Sample Output 3

349065850398865915384738153697722542688574377708317

The values in input and output can both be enormous.

Problem Statement

There are N boxes numbered 1,2,\ldots,N, and 10^{100} balls numbered 1,2,\dots,10^{100}. Initially, box i contains just ball i.

Process a total of Q operations that will be performed.

There are three types of operations: 1, 2, and 3.

Type 1: Put all contents of box Y into box X. It is guaranteed that X \neq Y.

1 X Y

Type 2: Put ball k+1 into box X, where k is the current total number of balls contained in the boxes.

2 X

Type 3: Report the number of the box that contains ball X.

3 X

Constraints

• All values in the input are integers.
• 2 \le N \le 3 \times 10^5
• 1 \le Q \le 3 \times 10^5
• For each type-1 operation, 1 \le X,Y \le N and X \neq Y.
• For each type-2 operation, 1 \le X \le N.
• For each type-3 operation, ball X is contained in some box at that point.
• There is at least one type-3 operation.

Sample Input 1

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

Sample Output 1

5
4
3
1
3

This input contains ten operations.

• The first operation is of type 3. Ball 5 is in box 5.
• The second operation is of type 1. Put all contents of box 4 into box 1.
  • Box 1 now contains balls 1 and 4, and box 4 is now empty.
• The third operation is of type 2. Put ball 6 into box 1.
• The fourth operation is of type 2. Put ball 7 into box 4.
• The fifth operation is of type 3. Ball 7 is in box 4.
• The sixth operation is of type 1. Put all contents of box 1 into box 3.
  • Box 3 now contains balls 1, 3, 4, and 6, and box 1 is now empty.
• The seventh operation is of type 3. Ball 4 is in box 3.
• The eighth operation is of type 1. Put all contents of box 4 into box 1.
  • Box 1 now contains ball 7, and box 4 is now empty.
• The ninth operation is of type 3. Ball 7 is in box 1.
• The tenth operation is of type 3. Ball 6 is in box 3.