TROC #33 [EN] - HackMD

# 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.  ## 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 A1 A2 A3 … AN </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 C1,1 C1,2 … C1,K C2,1 C2,2 … C2,K ︙ ⋱ ︙ CN,1 CN,2 … CN,K </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  ### 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 A1 A2 A3 … AN P1 P2 P3 … PK </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 Pj</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 Pj</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 U1 V1 U2 V2 ⋮ UN-1 VN-1 Q T1 P1 T2 P2 ⋮ TQ PQ </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)$.

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.