TeamsCode's problem setters are very evil and enjoy creating problems for others, so they have kidnapped Litusiano and given him a chance to escape if he is clever enough to solve their task. The task consists of the following:
Litusiano knows the address of the building, denoted by $$$x$$$, in which they are keeping him and he needs to transmit it to his savior Danx. The TeamsCode problem setters have designed a system for him to get in contact with Danx, who is trying to rescue him, and tell him the address of the building. Unfortunately, this system can only transmit information through clues. Each clue is a triplet of the form $$$(a, b, c)$$$, which means that $$$|a - b|$$$ is divisible by $$$x$$$ if $$$c = 1$$$, or not divisible if $$$c = 0$$$.
Unfortunately, Litusiano is not clever enough to transmit the address, so he has asked you to help him transmit the address.
You must output an integer $$$k$$$, the minimum number of clues needed to determine the value $$$x$$$. Additionally, you must a provide a set of clues of size $$$k$$$ such that Danx can know the value $$$x$$$.
In the original contest, the problem didn't ask for a construction. That was because it's hard to implement custom checkers for the TeamsCode judge, but we intended to ask for a construction to make sure that the idea is right.
On the first line there's an integer $$$t (1 \le t \le 10^{3}) $$$ $$$-$$$ the number of tests.
For each test, there's one line containing the integer $$$x$$$. $$$(1 \le x \le 10^{6})$$$.
For each test, output an integer $$$k \le 10^3$$$, the minimum number of clues needed to leave exactly one possible value of $$$x$$$. Then, on each of the following $$$k$$$ lines output three integers $$$a$$$, $$$b$$$ and $$$c$$$, representing each of the clues. $$$(1 \le a, b \le 10^9; c \in \{0, 1\})$$$.
2 1 5
1 2 3 1 2 3 8 1 1 3 0
—
Problem Idea: Esomer
Problem Preparation: Esomer
Occurrences: Novice 9, Advanced 2
| Teamscode Summer 2023 Contest |
|---|
| Закончено |
