---
# System prepended metadata

title: 'TROC #33 [EN]'
tags: [Contest]

---

# TROC #33 [EN]

## A. Careless

### Description

Sayed just participated in the municipal stage of the National Olympiad 2023. Currently, he is anxious about whether he will pass the selection or not.

Sayed answered $N$ out of the $20$ multiple-choice problems and $M$ out of the $15$ short-answer problems. Sayed is sure that he made mistakes, namely he answered $X$ multiple-choice problems and $Y$ short-answer problems incorrectly. Other than that, the remaining problems he answered are answered correctly.

One multiple-choice problem is worth $1$, and one short-answer problem is worth $2$ if answered correctly. An unanswered problem or a problem that is answered incorrectly is worth $0$. Sayed will pass the selection if and only if his total score is **strictly greater than half** of the maximum total score possible for all problems. 

Determine whether Sayed will pass the selection or not.

### Constraints

- $0 \leq X \leq N \leq 20$
- $0 \leq Y \leq M \leq 15$

### Input

<pre>
N M X Y
</pre>

### Output

Output `LOLOS` (means pass) if Sayed will pass the selection, or `TIDAK LOLOS` (means do not pass) if Sayed will not pass the selection.

### Sample Input 1

```
11 14 2 4
```

### Sample Output 1

```
LOLOS
```

### Explanation of Sample 1

Sayed answered $9$ multiple-choice problems and $10$ short-answer problems correctly, so the total score is $29$, which means he will pass the selection.

### Sample Input 2

```
0 15 0 4
```

### Sample Output 2

```
TIDAK LOLOS
```

### Explanation of Sample 2

Sayed answered $0$ multiple-choice problems and $11$ short-answer problems correctly, so the total score is $22$, which means he will not pass the selection.

### Sample Input 3

```
19 4 2 0
```

### Sample Output 3

```
TIDAK LOLOS
```

### Explanation of Sample 3

Sayed answered $17$ multiple-choice problems and $4$ short-answer problems correctly, so the total score is $25$, which means he will not pass the selection.

<!--
A few months ago Sayed participated in the The first stage of the National Olympiad in Informatics. Due to his tendency to make careless mistakes, he is anxiously thinking whether he will pass the stage or not.

He remembers that he answered $N$ multiple choice problems out of $20$ and $M$ short answer problems out of $15$. After rethinking about the problems, unfortunately he remembered and certain that he made silly mistakes in $x$ multiple choice problems and $y$ short answer problems. It is guaranteed that he answered those $x + y$ problems incorrectly.

He will pass the stage if and only if he got points of more than half of the maximal points. Multiple choices and short answers are worth $1$ and $2$ point respectively and there is no minus system for incorrect answer.

Determine if Sayed pass or fail the stage.

Not related to the problem, In the real life case Sayed failed to pass the stage unfortunately.

### Constraints

- $x \le N \le 20$
- $y \le M \le 15$

### Input

<pre>
N M x y
</pre>
-->

## B. Sitting Position

### Description

It is the start of a new school year. Neb's class has $M$ tables. For each table, at most $2$ students can sit at the table. There are $A$ male students and $B$ female students in his class.

Now Neb wants to know, if all $A+B$ students have to sit at the $M$ available tables and the sitting positions can be arranged freely, what is the minimum and maximum number of tables with a male student and a female student sitting together?

### Constraints

- $1 \leq M \leq 10^9$
- $0 \leq A, B \leq 10^9$
- $A+B \leq 2M$

### Input

<pre>
M A B
</pre>

### Output

One line containing two integers, with the two integers respectively representing the minimum and maximum number of tables with a male student and a female student sitting together.

### Sample Input 1

```
6 3 4
```

### Sample Output 1

```
0 3
```

### Explanation of Sample 1


We can get $0$ tables with a male student and a female student sitting together if we arrange them like this.

We can get $3$ tables with a male student and a female student sitting together if we arrange them like this.

It can be proven that $0$ and $3$ are the minimum and maximum possible respectively.

### Sample Input 2

```
4 1 7
```

### Sample Output 2

```
1 1
```

### Explanation of Sample 2

No matter how we arrange the sitting positions, there will always be exactly $1$ table with a male student and a female student sitting together.

## C. Digit War

### Description

Neb and Rep are playing a game. Initially, an integer $N$ will be given. Then, the players take turns playing the game, with Neb going first.

For each turn, the player on that turn chooses a non-zero digit from the current integer and subtracts the value of that digit from the integer. The player that is the first to turn the integer into $0$ wins the game.

Determine who will win the game if both players play optimally.

### Constraints

- $1 \leq N \leq 10^{9}$

### Input

<pre>
N
</pre>

### Output

Output `Neb` if Neb wins the game, or `Rep` otherwise.

### Sample Input 1

```
11
```

### Sample Output 1

```
Neb
```

### Explanation of Sample 1

One possible game can go like this:
- The integer is initially $11$.
- Neb chooses the digit $1$ from $11$ and changes the number into $11-1=10$.
- Rep chooses the digit $1$ from $10$ and changes the number into $10-1=9$.
- Neb chooses the digit $9$ from $9$ and changes the number into $9 - 9 = 0$.
- Neb wins the game.

### Sample Input 2

```
14
```

### Sample Output 2

```
Neb
```

### Explanation of Sample 2

One possible game can go like this:
- The integer is initially $14$.
- Neb chooses the digit $1$ from $14$ and changes the number into $14-1=13$.
- Rep chooses the digit $3$ from $13$ and changes the number into $13-3=10$.
- Neb chooses the digit $1$ from $10$ and changes the number into $10 - 1 = 9$.
- Rep chooses the digit $9$ from $9$ and changes the number into $9 - 9 = 0$.
- Rep wins the game.

Note that the game above does not reflect an optimal playing strategy for each player. In fact, there exists a strategy Neb can do to always win the game if $N=14$.

## D. Compatible Product

### Description

Given an array $A$ of size $N$ consisting of integers.

We define the compatibility property as follows:
- Let there be a positive integer $Z$ and a positive integer $k$.
- Create an array $B$ of size $N$ such that $B_i = A_i + k$ for all $i$.
- Calculate $P$ as the product of all the elements in $B$.
- $Z$ is said to be compatible with $k$ if and only if $P - Z$ is divisible by $k$.

From the given array $A$, find a positive integer $Z$ that is simultaneously compatible with every possible positive integer $k$ ($1$, $2$, $3$, and so on). It can be proven that there is only one possible solution for $Z$. Because the answer can be very large, print the answer modulo $998\,244\,353$.

### Constraints

- $1 \leq N \leq 200\,000$
- $1 \leq A_i \leq 200\,000$

### Input

<pre>
N
A<sub>1</sub> A<sub>2</sub> A<sub>3</sub> … A<sub>N</sub>
</pre>

### Output

A positive integer $Z$ that is simultaneously compatible with every possible positive integer $k$, modulo $998\,244\,353$.

### Sample Input

```
3
1 2 1
```

### Sample Output

```
2
```

### Explanation

$Z=2$ is a valid solution. For example:
- If $k=1$, then $B=[2,3,2]$, $P=12$, and $P-Z=10$, is divisible by $1$.
- If $k=2$, then $B=[3,4,3]$, $P=36$, and $P-Z=34$, is divisible by $2$.
- If $k=3$, then $B=[4,5,4]$, $P=80$, and $P-Z=78$, is divisible by $3$.

It can be proven that if $Z=2$, the same property will apply for any positive integer $k$.

For example, $Z=8$ is not a valid solution. One counter case is $k=4$, then $B=[5,6,5]$, $P=150$, and $P-Z=142$ which is not divisible by $4$.

## E. Satu

### Description

In his spare time, Sayed enjoys watching people play card games. Today, he is observing a card game called Satu. In this game, $N$ players take turns placing cards onto a center pile. The players are numbered from $1$ to $N$. Initially, for each $i$, the $i$-th player is given exactly $K$ cards, with values $C_{i,1}, C_{i,2}, \ldots, C_{i,K}$. It is known that the values of all cards are between $1$ and $N\times K$ (inclusive) and all $N\times K$ cards have distinct values.

The game follows these rules:
- Initially, the center pile is empty.
- During each turn, the player on that turn must choose and place exactly one of his/her cards onto the top of the center pile.
- During the first turn of the game, the newly placed card can have any value.
- During each next turn, the newly placed card must have a value that is a multiple of the current value of the card on the top of the center pile.
- Any previously used card cannot be used again.
- After the $p$-th player's turn, it is the $((p\bmod N)+1)$-th player's turn.
- The first player who is unable to place any valid card during his/her turn is the loser of the game.

Sayed knows the values of the cards given to each player. He wonders, how many pairs $(x,y)$ ($1\leq x,y\leq N$) such that there exists a valid game where the $x$-th player starts on the first turn and the $y$-th player loses? Help him calculate this!

### Constraints

- $2\leq N\leq200\,000$
- $1\leq K\leq200\,000$
- $N\times K \leq200\,000$
- $1 \leq C_{i,j} \leq N\times K$
- All values of $C_{i,j}$ are distinct.

### Input

<pre>
N K
C<sub>1,1</sub> C<sub>1,2</sub> … C<sub>1,K</sub>
C<sub>2,1</sub> C<sub>2,2</sub> … C<sub>2,K</sub>
︙       ⋱ ︙
C<sub>N,1</sub> C<sub>N,2</sub> … C<sub>N,K</sub>
</pre>

### Output

An integer representing the number of pairs $(x,y)$ ($1\leq x,y\leq N$) such that there exists a valid game where the $x$-th player starts on the first turn and the $y$-th player loses.

### Sample Input

```
3 5
5 7 3 4 6
12 1 15 14 10
13 8 9 11 2
```

### Sample Output

```
5
```

### Explanation

One possible game is as follows:
1. Let's say the first player is the $2$-nd player.
2. The $2$-nd player places a card with a value of $1$.
3. The $3$-rd player places a card with a value of $2$.
4. The $1$-st player places a card with a value of $6$.
5. The $2$-nd player places a card with a value of $12$.
6. The $3$-rd player is unable to place any cards, so player $3$ loses.

Therefore, the pair $(2,3)$ is one possible pair, which represents a valid game where the $2$-nd player starts on the first turn and the $3$-rd player loses.

The $5$ possible pairs are $(1,3)$, $(2,1)$, $(2,3)$, $(3,1)$, and $(3,3)$.

## F. Sayed and Billiards

<!--
Having been bored with the traditional form of billiards, Sayed created a unique billiard game. Given a circular billiard table with walls around its circumference, the billiard balls are represented as points. Initially, the ball is placed on the table but does not touch the walls. Note that there is no hole in the this billiard table.

You can poke the ball in a certain direction and determine how far the ball will move. The poked ball will move in a straight line following the direction of the poke. The initial direction of the ball is the same as the poking direction. Each time the ball hits a wall, it will bounce following the following rules.

The ball will stop once it has traveled a predetermined distance.

You are given an integer $K$. The initial position of the ball is considered good if and only if you can determine the direction and distance of the poke in such a way that the ball will bounce exactly $K$ times and end up in the initial position with the same direction as the initial poke.

If the initial position of the ball is randomly determined within the entire area of the table excluding the walls, what is the probability that the initial position of the ball is good?
-->

### Description

Sayed is playing a unique game of billiards. This version of billiards is played on a circular table with walls on its circumference and without holes on the table. Since the size of the ball in this game is very small, the ball can be represented as a point. Initially, the ball is placed in some position inside the table not touching the walls.

Sayed is going to shoot this ball. Specifically, Sayed will determine the direction and distance of the ball's motion. The ball will move in a straight line according to the direction of its movement. The direction of the ball's initial movement is the same as the direction of its shot. Every time the ball hits the wall, the ball will bounce according to the following rules: 
- Define point $O$ as the center of the circle and $P$ as the current point of collision of the ball.
- Define $L_{1}$ as a line passing through point $P$ that is perpendicular to the line $\overline{OP}$, $L_{2}$ as the line segment of the ball's path before the collision, and $L_{3}$ as the line segment of the ball's path after the collision.
- Therefore, the acute angle between $L_{2}$ and $L_{1}$ will be the same as the acute angle between $L_{3}$ and $L_{1}$ as demonstrated by the illustration below.

![billiard-illustration](https://media.discordapp.net/attachments/702195345702125679/1120040533214105661/ezgif.com-video-to-gif.gif)

Afterwards, the ball will stop when it has covered the determined movement distance. The initial position of the ball is said to be good if and only if Sayed can determine the direction and the distance of the shot such that in one shot, the ball will bounce exactly $K$ times and end up in its initial position with the **same direction** of movement as the initial shot.

Calculate the probability that the ball gets a good initial position if the initial position of the ball is determined randomly.

### Constraints

- $1 \leq K \leq 200\,000$

### Input

<pre>
K
</pre>

### Output

A real number representing the probability that the ball gets a good initial position. Your answer is considered correct if the absolute or relative difference in comparison with the jury's solution is less than $10^{-6}$.

### Sample Input 1

```
3
```

### Sample Output 1

```
0.75
```

### Explanation of Sample 1

An example of an initial position that is not good is if the ball starts exactly in the center of the table.

The illustration below shows that if the ball starts there, it is possible to make it bounce exactly $3$ times and go back to its initial position, but not with the same direction of movement as the initial shot.

### Sample Input 2

```
2
```

### Sample Output 2

```
1
```

### Explanation of Sample 2

The illustration below shows an example of a good initial position and a valid way to shoot the ball.

## G. LXM

### Description

Neb has an array $[A_1, A_2, \ldots, A_N]$. Neb also has a graph $G$ with $N$ vertices numbered from $1$ to $N$. For every pair of indices $i$ and $j$ ($i<j$), there is an undirected edge that connects vertices $i$ and $j$ in graph $G$ with weight $\text{LCM}(A_i, A_{i+1}, ..., A_j)$. Note: $\text{LCM}(A_i, A_{i+1}, ..., A_j)$ is the smallest positive integer that is divisible by $A_i$, $A_{i+1}$, ..., and $A_j$.

Neb marks $K$ distinct vertices $P_1$, $P_2$, ..., and $P_K$ in graph $G$ as special vertices. Neb wants to choose some edges in $G$ such that every pair of **special vertices** is connected to every other **special vertices** using one or more chosen edges and Neb wants the total weight of the chosen edges to be minimum. Please help Neb figure out that minimum total weight!

### Constraints

- $2 \leq K \leq N \leq 200\,000$
- $1 \leq A_i \leq 200\,000$
- $1 \leq P_j \leq N$
- All values of $P_j$ are distinct.

### Input

<pre>
N K
A<sub>1</sub> A<sub>2</sub> A<sub>3</sub> … A<sub>N</sub>
P<sub>1</sub> P<sub>2</sub> P<sub>3</sub> … P<sub>K</sub>
</pre>

### Output

An integer representing the minimum possible total weight.

### Sample Input

```
8 4
6 3 2 3 1 10 3 15
6 8 2 7
```

### Sample Output

```
61
```

### Explanation

One possible optimal strategy of choosing the edges is as follows:
- Choose the edge connecting vertices $5$ and $6$ with weight $\text{LCM}(A_5,A_6)=\text{LCM}(1,10)=10$
- Choose the edge connecting vertices $5$ and $8$ with weight $\text{LCM}(A_5,A_6,A_7,A_8)=\text{LCM}(1,10,3,15)=30$.
- Choose the edge connecting vertices $7$ and $8$ with weight $\text{LCM}(A_7,A_8)=\text{LCM}(3,15)=15$.
- Choose the edge connecting vertices $2$ and $5$ with weight $\text{LCM}(A_2,A_3,A_4,A_5)=\text{LCM}(3,2,3,1)=6$.

If only the edges above are chosen, the graph will be as follows.

![](https://cdn.discordapp.com/attachments/1108405790383018125/1120688887015165952/lcmst.png)


## H. Her Lost

### Description

After a successful blind date, when Icybear asks for Chloe's phone number, Chloe gives Icybear a challenge.

Chloe has a tree of size $N$, with the vertices numbered from $1$ to $N$. Edge $i$ connects vertex $U_i$ and vertex $V_i$. Chloe has an integer $K$ and she wishes to know the number of vertex pairs $(x,y)$ ($x<y$) which has a distance of exactly $K$.

Since this problem is too simple for Icybear, Chloe will modify the tree $Q$ times. In the $j$-th modification, Chloe will do one of the following things:
- <code>1 P<sub>j</sub></code> -- adding a new vertex numbered $N+j$ and connecting it to vertex $P_j$. It is guaranteed that vertex $P_j$ currently exists in the tree.
- <code>2 P<sub>j</sub></code> -- removing vertex $P_j$ from the tree with vertex $P_j$ currently being a leaf in the tree. This modification will not remove all vertices in the tree.

Chloe wants to know the number of vertex pairs $(x,y)$ ($x<y$) which has a distance of exactly $K$ before any modifications and after each modification of the tree. Help Icybear solve this problem!

Note: a vertex is said to be a leaf if and only if it is only directly connected with one other vertex.

### Constraints

- $2 \leq N \leq 150\,000$
- $1 \leq K \leq N-1$
- $1 \leq U_i, V_i \leq N$
- It is guaranteed that the initial edges form a tree.
- $1 \leq Q \leq 150\,000$
- $1 \leq T_j \leq 2$, with $T_j$ as the type of the $j$-th modification.
- For each type $1$ modification, vertex $P_j$ exists in the tree.
- For each type $2$ modification, vertex $P_j$ exists and is a leaf in the tree.
- A type $2$ modification will not remove all vertices in the tree.

### Input

<pre>
N K
U<sub>1</sub> V<sub>1</sub>
U<sub>2</sub> V<sub>2</sub>
⋮
U<sub>N-1</sub> V<sub>N-1</sub>
Q
T<sub>1</sub> P<sub>1</sub>
T<sub>2</sub> P<sub>2</sub>
⋮
T<sub>Q</sub> P<sub>Q</sub>
</pre>

### Output

Output $Q+1$ lines. The first line contains an integer representing the number of vertex pairs $(x,y)$ ($x<y$) which has a distance of exactly $K$ before any modifications. The $j$-th of the next $Q$ lines contains an integer representing the number of vertex pairs $(x,y)$ ($x<y$) which has a distance of exactly $K$ right after the $j$-th modification.

### Sample Input

```
4 2
1 4
4 3
2 4
2
2 3
1 2
```

### Sample Output

```
3
1
2
```

### Explanation

Before any modifications, the tree looks as follows.

The valid pairs are $(1,2)$, $(1,3)$, and $(2,3)$.

Right after the $1$-st modification, the tree looks as follows.

The only valid pair is $(1,2)$.

Right after the $2$-nd modification, the tree looks as follows.

The valid pairs are $(1,2)$ and $(4,6)$.