Warning

Do not make any mention of this problem until December 29, 2019, 05:00 a.m. JST. In case of violation, compensation may be demanded.

After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

You were asked to write a program that receives a three-digit integer, multiplies it by 2, and prints the result.

It seems, however, that the string S given to the program may contain lowercase English letters. You decide to print an error message in such a case.

Write the following program: if S is a three-digit integer (possibly beginning with a 0), the program should multiply it by 2 and print the result; otherwise, the program should print error.

Constraints

• S is a string of length 3.
• Each character of S is a digit or a lowercase English letter.

Sample Input 1

678

Sample Output 1

1356

For an integer, multiply it by 2 and print the result.

Sample Input 2

abc

Sample Output 2

error

For a non-integer string, print error.

Sample Input 3

0x8

Sample Output 3

error

The input may be a combination of digits and English letters. Some languages can interpret these strings as integers, but print error in these cases, too.

Sample Input 4

012

Sample Output 4

24

Assume that S is written in decimal notation, even if S begins with a 0.

Warning

Do not make any mention of this problem until December 29, 2019, 05:00 a.m. JST. In case of violation, compensation may be demanded.

After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

Given is a series of sales of a certain product for N days, as an integer sequence A_1, A_2, \ldots, A_N. A_i (1 \leq i \leq N) represents the sale for the i-th day.

You decide to write a program that, for each day starting with the second day, prints how much the sales increased (or decreased) compared to the previous day.

More specifically, your program should print N-1 lines. The i-th line (1 \leq i \leq N-1) should contain the following:

• If A_{i+1} is equal to A_i: stay
• If A_{i+1} is less than A_i: down [amount], where [amount] is the integer value A_i - A_{i+1}
• If A_{i+1} is greater than A_i: up [amount], where [amount] is the integer value A_{i+1} - A_i

Write this program.

Constraints

• 2 \leq N \leq 100000
• 0 \leq A_i \leq 10^9
• All values in input are integers.

Sample Input 1

10
9
10
3
100
100
90
80
10
30
10

Sample Output 1

up 1
down 7
up 97
stay
down 10
down 10
down 70
up 20
down 20

Given is a series of sales for N = 10 days. Let us explain the first four lines in the output:

• Line 1: A_2 = 10 is greater than A_1 = 9 by 1, so print up 1.
• Line 2: A_3 = 3 is smaller than A_2 = 10 by 7, so print down 7.
• Line 3: A_4 = 100 is greater than A_3 = 3 by 97, so print up 97.
• Line 4: A_5 = 100 is equal to A_4 = 100, so print stay.

Warning

Do not make any mention of this problem until December 29, 2019, 05:00 a.m. JST. In case of violation, compensation may be demanded.

After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

Given are six distinct integers A, B, C, D, E, and F.

Write the program that finds out the third-largest number among them.

Constraints

• 1 \leq A, B, C, D, E, F \leq 100
• A, B, C, D, E, and F are all different.
• All values in input are integers.

Sample Input 1

4 18 25 20 9 13

Sample Output 1

18

The third-largest number is 18.

Sample Input 2

95 96 97 98 99 100

Sample Output 2

98

Sample Input 3

19 92 3 35 78 1

Sample Output 3

35

Warning

Do not make any mention of this problem until December 29, 2019, 05:00 a.m. JST. In case of violation, compensation may be demanded.

After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

We have an integer sequence of length N stored in our server. Until just a minute ago, this sequence contained one occurrence of each integer from 1 to N.

However, trouble has occurred, which may have replaced one element in the sequence with another integer between 1 and N (inclusive). It is also possible that there was no such overwrite.

Given is the integer sequence after the trouble, A_1, \ldots, A_N. Write a program that reads it and determines whether there was an overwrite. If there was an overwrite, the program should also report which integer was replaced with which integer.

Constraints

• 1 \leq N \leq 200000
• 1 \leq A_i \leq N
• The sequence A_1, \ldots, A_N is consistent with the situation described in Problem Statement.

Sample Input 1

6
1
5
6
3
2
6

Sample Output 1

6 4

The original sequence should have contained one occurrence of each integer from 1 to 6. However, the given sequence contains two occurrences of 6 and no occurrence of 4. Thus, we can see that 4 was replaced with 6.

Sample Input 2

7
5
4
3
2
7
6
1

Sample Output 2

Correct

The original sequence should have contained one occurrence of each integer from 1 to 7, and so does the given sequence. Thus, we can see that there was no overwrite.

Warning

Do not make any mention of this problem until December 29, 2019, 05:00 a.m. JST. In case of violation, compensation may be demanded.

After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

You run a social media site with N users. The users are called User 1, \ldots, N, and they can follow an unlimited number of other users. The list of users followed by a particular user is called follow-list of that user.

However, due to trouble, the follow-lists of all users have been lost. Fortunately, all operations ever performed on the site have been recorded in the log file. You are trying to restore the follow-lists of the users from this file.

The file consists of Q lines, and the i-th line contains a string S_i. The users can perform the three kinds of operations below, and S_i corresponds to the i-th operation performed on the whole site.

• Follow: User a follows User b (a \neq b). The log file records the line 1 a b.
• Follow-Back-All: User a follows all users who are following User a at that moment. The log file records the line 2 a.
• Follow-Follow: For every user x who are followed by User a at that time, User a performs the following: "follow all users (except User a itself) followed by User x." The log file records the line 3 a.

At the beginning of the site, no user was following anyone else. Also, if User a is already following User b and attempts to re-follow User b, nothing happens.

Restore the follow-lists of all users.

Constraints

• 2 \leq N \leq 100
• 0 \leq Q \leq 500
• S_i is a string in one of the following formats:
  • 1 a b (1 \leq a, b \leq N and a \neq b)
  • 2 a (1 \leq a \leq N)
  • 3 a (1 \leq a \leq N)

Sample Input 1

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

Sample Output 1

NYYNYY
NNYNNN
NNNYNN
NNNNNN
NNNNNY
YNNNYN

Six users, User 1, \ldots, 6, performed a total of seven operations, which resulted in the following log file:

• S_1: User 1 followed User 2.
• S_2: User 2 followed User 3.
• S_3: User 3 followed User 4.
• S_4: User 1 followed User 5.
• S_5: User 5 followed User 6.
• S_6: User 1 performed Follow-Follow. At the moment, User 1 was following two users, User 2 and 5. User 2 was following User 3, and User 5 was following User 6, so User 1 followed two users, User 3 and 6.
• S_7: User 6 performed Follow-Back-All. At the moment, User 6 was followed by two users, User 1 and 5, so User 6 followed back these two users.

In the end, we have the follow-lists shown in the output above.

Warning

Do not make any mention of this problem until December 29, 2019, 05:00 a.m. JST. In case of violation, compensation may be demanded.

After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

Given is a string S, which is a concatenation of one or more words (without any extra characters such as spaces in between). Each word here is at least two characters long. The first and last characters are uppercase, and all the other characters are lowercase.

Write a program that sorts these words in lexicographical order (ignoring the case), concatenates them in the same manner as in S, and prints it.

For example, consider the case S = FisHDoGCaTAAAaAAbCAC. This string is a concatenation of seven words: FisH, DoG, CaT, AA, AaA, AbC, and AC. We sort them in the lexicographical order: AA, AaA, AbC, AC, CaT, DoG, FisH, and print AAAaAAbCACCaTDoGFisH.

Constraints

• S is a string of length between 2 and 100000 (inclusive).
• Each character of S is an uppercase or lowercase English letter.
• S is a concatenation of words as described in Problem Statement.

Sample Input 1

FisHDoGCaTAAAaAAbCAC

Sample Output 1

AAAaAAbCACCaTDoGFisH

This is the example used in Problem Statement.

Sample Input 2

AAAAAjhfgaBCsahdfakGZsZGdEAA

Sample Output 2

AAAAAAAjhfgaBCsahdfakGGdEZsZ

Note that the same word may occur multiple times.

Warning

Do not make any mention of this problem until December 29, 2019, 05:00 a.m. JST. In case of violation, compensation may be demanded.

After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

You are writing a program that optimally divides N employees in your company, Employee 1, \ldots, N, into at most three groups.

For all pairs of employees i, j (1 \leq i < j \leq N), an AI has already computed the happiness A_{i,j} (not necessarily positive) that will arise if those two employees belong to the same group.

Let the desirability of a grouping be the sum of A_{i,j} over all pairs of employees i, j that belong to the same group (if no such pair exists, the desirability is 0). Find the maximum possible desirability of a grouping.

Constraints

• 2 \leq N \leq 10
• -10^6 \leq A_{i,j} \leq 10^6
• All values in input are integers.

Sample Input 1

6
10 10 -10 -10 -10
10 -10 -10 -10
-10 -10 -10
10 -10
-10

Sample Output 1

40

Consider making the following three groups: a group with Employee 1, 2,3, a group with Employee 4, 5, and a group with Employee 6. There are four pairs of employees belonging to the same group: (1,2), (1,3), (2,3), (4,5), for the desirability of A_{1,2} + A_{1,3} + A_{2,3} + A_{4,5} = 10 + 10 + 10 + 10 = 40. This is the optimal grouping.

Sample Input 2

3
1 1
1

Sample Output 2

3

All employees may belong to the same group.

Warning

Do not make any mention of this problem until December 29, 2019, 05:00 a.m. JST. In case of violation, compensation may be demanded.

After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

You are going to sell trading cards. You have N kinds of cards, Card 1, \ldots, N, and you have C_i copies of Card i (1 \leq i \leq N) in stock initially.

Now, you have to process Q requests S_1, \ldots, S_Q in order. Each request is in one of the following forms:

• Single Kind: Sell a copies of Card x, or do nothing if you do not have enough copies in stock. Given in the format 1 x a.
• Many Kinds: Sell a copies of Card x for every odd number x between 1 and N (inclusive), or do nothing if you do not have enough copies of one or more of those kinds in stock. Given in the format 2 a.
• All Kinds: Sell a copies of Card x for every number x between 1 and N, or do nothing if you do not have enough copies of one or more of those kinds in stock. Given in the format 3 a.

Print the total number of cards that will be sold in these requests.

Constraints

• 1 \leq N \leq 200000
• 1 \leq C_i \leq 10^9
• 1 \leq Q \leq 200000
• S_i is a string in one of the following formats:
  • 1 x a (1 \leq x \leq N and 1 \leq a \leq 10^9)
  • 2 a (1 \leq a \leq 10^9)
  • 3 a (1 \leq a \leq 10^9)
• All values in input are integers.

Sample Input 1

4
5 3 3 5
6
1 2 1
2 2
2 2
3 100
3 1
1 1 3

Sample Output 1

9

Initially, you have 5,3,3,5 copies of Card 1,2,3,4, respectively. Each request will be processed as follows:

1. Sell one copy of Card 2. You have now 5,2,3,5 copies of Card 1,2,3,4 in stock.
2. Sell two copies of Card 1 and 3 each. You have now 3,2,1,5 copies in stock.
3. You do not have enough copies of Card 3 in stock. Do nothing.
4. Not enough copies in stock. Do nothing.
5. Sell one copy of every kind of card. You have now 2,1,0,4 copies in stock.
6. Not enough copies in stock. Do nothing.

As seen above, we will sell 1, 4, 4 cards in the first, second, fifth requests, for a total of 9 cards.

Sample Input 2

10
241 310 105 738 405 490 158 92 68 20
20
2 252
1 4 36
2 69
1 5 406
3 252
1 3 8
1 10 10
3 11
1 4 703
3 1
2 350
3 10
2 62
2 3
2 274
1 2 1
3 126
1 4 702
3 6
2 174

Sample Output 2

390

Sample Input 3

2
3 4
3
1 2 9
2 4
3 4

Sample Output 3

0

Warning

Do not make any mention of this problem until December 29, 2019, 05:00 a.m. JST. In case of violation, compensation may be demanded.

After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

You want to buy N kinds of parts to make some objects: Part 1, \ldots, N. After searching online, you found M packages of parts on sale.

The i-th package (1 \leq i \leq M) is described by a string S_i of length N and an integer C_i. The j-th character (1 \leq j \leq N) of S_i is Y if the package contains Part j, and N otherwise. This package is sold for C_i yen (the currency of Japan).

Write a program that finds the minimum amount of money needed to buy some of these packages and get all N kinds of parts (or reports that it is impossible). It is fine to get more than one part of the same kind.

Constraints

• 1 \leq N \leq 10
• 1 \leq M \leq 1000
• S_i is a string of length N.
• Each character of S_i is Y or N.
• 1 \leq C_i \leq 10^9
• C_i is an integer.

Sample Input 1

3 4
YYY 100
YYN 20
YNY 10
NYY 25

Sample Output 1

30

If we buy the second and third packages, we get all kinds of parts 1, 2, 3 for 20 + 10 = 30 yen.

Sample Input 2

5 4
YNNNN 10
NYNNN 10
NNYNN 10
NNNYN 10

Sample Output 2

-1

Part 5 is not contained in any package, so we cannot get all kinds of parts.

Sample Input 3

10 14
YNNYNNNYYN 774472905
YYNNNNNYYY 75967554
NNNNNNNNNN 829389188
NNNNYYNNNN 157257407
YNNYNNYNNN 233604939
NYYNNNNNYY 40099278
NNNNYNNNNN 599672237
NNNYNNNNYY 511018842
NNNYNNYNYN 883299962
NNNNNNNNYN 883093359
NNNNNYNYNY 54742561
NYNNYYYNNY 386272705
NNNNYYNNNN 565075143
NNYNYNNNYN 123300589

Sample Output 3

451747367

Warning

Do not make any mention of this problem until December 29, 2019, 05:00 a.m. JST. In case of violation, compensation may be demanded.

After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

There is a rectangular piece of land divided into a grid of H \times W squares with H horizontal rows and W vertical columns. Except for the three squares at the bottom-left, bottom-right, and top-right corners of the grid, all the squares are unpaved. Paving the square at the i-th row from the top and the j-th column from the left (1 \leq i \leq H, 1 \leq j \leq W) costs A_{i,j} yen (the currency of Japan).

We have an object in the square at the bottom-left corner of the grid. You want to carry it to the square at the bottom-right corner, then to the square at the top-right corner.

To carry the object, you need to repeat moving it from a square to another square that is horizontally or vertically adjacent to the square currently occupied. Here, all the squares that the object goes through must be paved. Once a square is paved, the object may go through that square any number of times.

Find the minimum amount of money needed to pave squares for your objective.

Constraints

• 2 \leq H, W \leq 50
• 0 \leq A_{i,j} \leq 100000
• A_{H,1} = A_{H,W} = A_{1,W} = 0
• All values in input are integers.

Sample Input 1

5 6
9 9 9 9 1 0
9 9 9 9 1 9
9 9 9 1 1 1
9 1 1 1 9 1
0 1 9 9 9 0

Sample Output 1

10

It is optimal to pave all the squares costing 1 yen to pave.

Sample Input 2

10 10
1 2 265 1544 0 1548 4334 9846 58 0
21 0 50 44 2 388 5 0 0 4
170 0 2 1 54 1379 50 3 41 0
310 0 1 0 2163 0 226 26 3 12
151 33 0 9 0 0 0 36 365 2286
0 3 12 3 9 317 645 100 21 4
52 1 569 0 144 0 6 202 25 0
8869 19 2058 1948 1252 1002 7 1750 0 5
0 3 8 29 2 4403 0 0 0 5
0 17 93 9367 159 6 1 216 0 0

Sample Output 2

246

Warning

Do not make any mention of this problem until December 29, 2019, 05:00 a.m. JST. In case of violation, compensation may be demanded.

After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

A certain company has N members, Member 1, \ldots, N. One of them is the president and has no boss. Each of the other members has exactly one immediate boss. According to your database, the immediate boss of Member i (1 \leq i \leq N) is Member p_i (p_i = -1 if Member i is the president). There is no cyclic relationship among those members.

Based on this database, you want to create a web service that, when two numbers a and b representing two members are given, determines whether Member a is junior to Member b. Here, Member a is said to be junior to Member b if and only if Member b can be reached from Member a by tracing the relationship between the members in upward direction only.

Given are Q pairs of numbers (a_1, b_1), \ldots, (a_Q, b_Q), each representing two members. Write a program that prints Yes or No for each of them.

Constraints

• 2 \leq N \leq 150000
• For each i = 1, \ldots, N, p_i = -1 or 1 \leq p_i \leq N.
• There exists a unique i such that p_i = -1.
• There is no cyclic relationship among the members.
• 1 \leq Q \leq 100000
• 1 \leq a_i, b_i \leq N
• a_i \neq b_i

Sample Input 1

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

Sample Output 1

Yes
Yes
No
Yes
Yes
No

The immediate juniors of Member 1 (the president) are Member 2, 3, the immediate juniors of Member 2 are Member 4, 5, and the immediate juniors of Member 3 are Member 6, 7.

For example, for the first pair (7, 1), Member 1 is the immediate boss of "the immediate boss of Member 7" (Member 3), so we print Yes.

Sample Input 2

20
4
11
12
-1
1
13
13
4
6
20
1
1
20
10
8
8
20
10
18
1
20
18 14
11 3
2 13
13 11
10 15
9 5
17 11
18 10
1 16
9 4
19 6
5 10
17 8
15 8
5 16
6 20
3 19
10 12
5 13
18 1

Sample Output 2

No
No
No
No
No
No
No
Yes
No
Yes
No
No
No
Yes
No
Yes
No
No
No
Yes

Warning

Do not make any mention of this problem until December 29, 2019, 05:00 a.m. JST. In case of violation, compensation may be demanded.

After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

There are N large towers and M small towers built on a two-dimensional coordinate plane. The i-th large tower (1 \leq i \leq N) has the coordinate (x_i, y_i) and the color c_i, and the i-th small tower (1 \leq i \leq N) has the coordinate (X_i, Y_i) and the color C_i. Here, the color of a tower is given as an integer, where 1, 2, 3 stand for red, green, blue, respectively. There may be multiple towers at the same coordinates.

You want to construct some bridges connecting two towers so that any large tower can be reached from any other large tower using some number of bridges. (The small towers can be treated in any way you like.)

The cost needed to construct a bridge connecting two towers is equal to the Euclidean distance between them, multiplied by 10 if the colors of the towers are different. (The cost does not depend on the sizes of the towers. Also, we do not consider the crossing of bridges.)

Find the minimum total cost needed to achieve your objective.

Constraints

• 2 \leq N \leq 30
• 1 \leq M \leq 5
• 0 \leq x_i, y_i \leq 1000
• 0 \leq X_i, Y_i \leq 1000
• 1 \leq c_i, C_i \leq 3
• All values in input are integers.

Sample Input 1

3 1
0 0 1
0 1 1
1 0 1
1 1 1

Sample Output 1

2.000000000000

We should directly connect the first and second large towers, then the first and third large towers, for a total cost of 1 + 1 = 2.

Sample Input 2

3 1
0 10 1
10 0 2
10 20 3
10 10 1

Sample Output 2

210.000000000000

We should connect the small tower to each of the large towers, for a total cost of 10 + 10 \times 10 + 10 \times 10 = 210.

Warning

Do not make any mention of this problem until December 29, 2019, 05:00 a.m. JST. In case of violation, compensation may be demanded.

After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

You run a social game, which features many monsters. Each monster has two parameters: Mass and Magic Power (MP).

A user owns N monsters. The Mass and MP of the i-th monster owned (1 \leq i \leq N) are A_i and B_i, respectively.

Additionally, there are M helper monsters. The Mass and MP of the i-th helper monster (1 \leq i \leq M) are C_i and D_i, respectively.

The user can choose exactly five out of these N + M monsters and combine them into one new monster. However, among those five monsters, there should be at most one helper monster. Let us define the strength of the new monster as the sum of the MPs of the monsters used, divided by the sum of the Masses of the monsters used.

You want to implement a function that automatically chooses monsters to combine so that the strength of the new monster is maximized. Write a program to find the maximum possible strength of the new monster when combining monsters only once.

Constraints

• 5 \leq N \leq 1000
• 1 \leq M \leq 100
• 1 \leq A_i, B_i \leq 100000
• 1 \leq C_i, D_i \leq 100000
• All values in input are integers.

Sample Input 1

6 2
10 30
20 60
10 10
30 100
50 140
40 120
10 3
30 1

Sample Output 1

3.0000000000000

It is optimal to do without the helper monsters and choose the 1-st, 2-nd, 4-th, 5-th, and 6-th monsters owned.

Sample Input 2

6 2
1 20
1 3
32 100
1 1
1 2
2 5
10 100
96 874

Sample Output 2

9.0000000000000

We have powerful helper monsters this time and should use one.

Warning

Do not make any mention of this problem until December 29, 2019, 05:00 a.m. JST. In case of violation, compensation may be demanded.

After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

There is a gate of width W. Below, we will regard this gate as a segment, and assume that a point on this segment has a coordinate between 0 and W (inclusive).

We have N stones scattered on the gate. The i-th stone (1 \leq i \leq N) occupies the segment (l_i, r_i), and it costs p_i yen (the currency of Japan) to remove it. Multiple stones may occupy the same point.

You want to allow a car to pass through this gate by removing some stones so that there will be a segment of length C not overlapping with a stone. Write a program to find the minimum amount of money to do so.

Constraints

• 1 \leq N \leq 100000
• 10 \leq W \leq 10^9
• 1 \leq C \leq W
• 0 \leq l_i < r_i \leq W
• 1 \leq p_i \leq 10^9
• All values in input are integers.

Sample Input 1

3 10 5
1 3 100
8 10 123
4 6 3

Sample Output 1

3

If we remove the third stone for 3 yen, no stone will overlap the segment [3, 8] of length 5. This is the optimal choice.

Sample Input 2

22 30 10
0 30 1000000000
0 30 1000000000
0 30 1000000000
7 30 261806
6 19 1
5 18 1238738
12 28 84
10 14 5093
9 20 9
15 26 8739840
6 8 240568
14 19 198
2 4 1102
1 29 5953283
9 20 183233
9 13 44580
6 23 787237159
12 14 49
28 29 9020727
14 20 318783
2 19 9862194
9 30 166652

Sample Output 2

3805189325

The amount of money may not fit into a 32-bit integer type.

Warning

Do not make any mention of this problem until December 29, 2019, 05:00 a.m. JST. In case of violation, compensation may be demanded.

After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

We have N unbiased six-sided dice. The j-th face (1 \leq j \leq 6) of the i-th die (1 \leq i \leq N) has an integer A_{i,j} written on it.

Takahashi repeats the following operation: choose a die and toss it. However, in the second and subsequent operations, if the die shows a number that is less than or equal to the number shown in the previous operation, the process ends. The die to toss each time can be chosen after seeing the previous number shown.

Takahashi wants to toss a die as many times as possible. Find the expected number of operations done when the choices are made to maximize this number.

Constraints

• 1 \leq N \leq 30000
• 1 \leq A_{i,j} \leq {10}^{9}
• A_{i,j} are all different.
• All values in input are integers.

Sample Input 1

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

Sample Output 1

3.64925355954377