On Planet E, people counts in base $$$\phi$$$!
We are all familiar with decimal representations. In decimal representation, each digit $$$x_i$$$ satisfies $$$0 \le x_i \le 9$$$ and $$$\overline{x_q x_{q - 1} x_{q - 2} \ldots x_0 . x_{-1} x_{-2} \ldots x_p}$$$ represents $$$$$$ \sum_{i = p}^q x_i 10^i = x_q 10^q + x_{q - 1} 10^{q - 1} + \ldots + x_p 10^p. $$$$$$
This can be naturally extended to any integer base $$$b \ge 2$$$. In base $$$b$$$, each digit $$$x_i$$$ satisfies $$$0 \le x_i \le b - 1$$$ and $$$\overline{x_q x_{q - 1} x_{q - 2} \ldots x_0 . x_{-1} x_{-2} \ldots x_p}$$$ represents $$$$$$ \sum_{i = p}^q x_i b^i = x_q b^q + x_{q - 1} b^{q - 1} + \ldots + x_p b^p. $$$$$$
Now it comes to non-integral bases! Let $$$\phi = (1 + \sqrt 5) / 2$$$ be the golden ratio. It can be shown that every positive integer $$$n$$$ can be represented in $$$$$$ n = \sum_{i = p}^q x_i \phi^i = x_q \phi^q + x_{q - 1} \phi^{q - 1} + \ldots + x_p \phi^p, $$$$$$ where each digit $$$x_i$$$ is either $$$0$$$ or $$$1$$$, and any adjacent digits $$$x_i$$$ and $$$x_{i + 1}$$$ are not both $$$1$$$. This representation is unique and is called the base $$$\phi$$$ representation.
Can you help the people on Planet E to convert a positive number in base $$$\phi$$$?
The first line contains a positive integer $$$T$$$ ($$$T \le 10$$$), the number of testcases.
Each testcase contains a positive integer $$$n$$$ ($$$n \le 100000$$$).
For each testcase, output a single line consisting of the representation of $$$n$$$ in base $$$\phi$$$.
5 1 2 3 100000 123
1 10.01 100.01 101010001010100000100000.101000101000000010000001 10000000000.0000000001
On Planet E, there are many stars!
To be precise, the sky is a 2-d plane and there are infinitely many stars, one at each integral point ($$$(x, y)$$$ where both $$$x$$$ and $$$y$$$ are integers).
People on Planet E have a hobby of drawing straight segments between the stars. One day, they are curious about how many stars their straight segments have covered.
Can you help the people on Planet E to count the number of stars on their straight segments?
The first line contains a positive integer $$$T$$$ ($$$T \le 100$$$), the number of testcases.
Each testcase contains 4 integers $$$x_0, y_0, x_1, y_1$$$ ($$$|x_i| \le 10^9$$$ and $$$|y_i| \le 10^9$$$ for $$$i = 0, 1$$$), representing the segment $$$(x_0, y_0)$$$ to $$$(x_1, y_1)$$$.
For each testcase, output a single line consisting of the number of stars on the segment.
4 1 1 1 1 1 2 3 6 -1 -1 50 101 -10000 1 1000000000 0
1 3 52 2
In the first testcase, the only covered star is $$$(1, 1)$$$.
In the second testcase, the covered stars are $$$(1, 2), (2, 4), (3, 6)$$$.
On Planet E, people enjoy playing snooker!
Unlike snooker on Earth, there is only one ball on Planet E, and no pockets on the table. Let the length of the table be $$$m$$$ and the width of the table be $$$n$$$. Then the positions on the table can be represented by $$$(x, y)$$$ where $$$0 \le x \le m$$$ and $$$0 \le y \le n$$$. We view the ball as a point without radius.
The goal is to move the ball from $$$(x_0, y_0)$$$ to $$$(x_1, y_1)$$$, with exactly $$$k$$$ bounces from the table walls.
This figure demonstrates 2 bounces. The ball moves in straight line and the reflection angle must be the same. Note that if the ball moves to a corner, it will move back in the exactly opposite direction with 2 bounces. See testcase 2 in the sample.
Can you help the people on Planet E to find the shortest distance the ball has to travel to achieve the goal?
The first line contains a positive integer $$$T$$$ ($$$T \le 100$$$), the number of testcases.
Each testcase contains 7 integers $$$m, n, x_0, y_0, x_1, y_1, k$$$ ($$$2 \le m \le 100$$$, $$$2 \le n \le 100$$$, $$$0 \lt x_i \lt m$$$ and $$$0 \lt y_i \lt n$$$ for $$$i = 0, 1$$$, and $$$0 \le k \le 100$$$), representing the table size (length $$$m$$$, width $$$n$$$) and the goal $$$(x_0, y_0)$$$ to $$$(x_1, y_1)$$$ with exactly $$$k$$$ bounces.
For each testcase, output a single line consisting of the shortest distance the ball has to travel, corrected to $$$2$$$ decimal places.
4 100 100 1 1 1 1 0 100 100 1 2 1 2 2 100 100 1 1 1 1 3 100 50 1 2 3 4 5
0.00 4.47 200.01 198.04
On Planet E, people share messages secretly!
In order not to allow others to read their messages easily, they encode their messages before sending, and decode the received texts to get back the message. To make things simpler, they decide to make the encoding method and decoding method the same! They have thought of three different methods.
The first is to swap the lower case and upper case characters. For example, Hello would become hELLO using this encoding.
The second is to reverse the word. For example, Hello would become olleH using this encoding.
The third is to use the ROT13 (rotate 13) encoding. In this method, each character would be moved to the 13-th character after it, with A being the next character of Z (and a being the next character of z). The case remains unchanged. Since there are 26 English characters, applying ROT13 twice would give back the original word. For example, Hello would become Uryyb using this encoding.
Since all three methods look nice and the people on Planet E do not want to give up any of them. Hence they decide to use all three encodings together!
Can you help the people on Planet E to do the encoding?
The first line contains a positive integer $$$T$$$ ($$$T \le 100$$$), the number of testcases.
Each testcase contains a string $$$s$$$ with at least $$$1$$$ character and at most $$$100$$$ characters. Each of characters is either a lower case English character or an upper case English character.
For each testcase, output a single line consisting of the encoded string.
3 HelloWorld QYEBjBYYRu pcpvBgRZBPYRj
QYEBjBYYRu HelloWorld WelcomeToICPC
On Planet E, people travel by horses!
There are $$$n$$$ cities on Planet E, labeled $$$0, 1, \dots, n - 1$$$, and $$$m$$$ roads connecting the cities. For each $$$j = 0, 1, \dots, m - 1$$$, road $$$j$$$ connects city $$$x_j$$$ and city $$$y_j$$$, meaning that we can travel from city $$$x_j$$$ to city $$$y_j$$$ (and from city $$$y_j$$$ to city $$$x_j$$$) in one step. Note that $$$x_j$$$ can be the same as $$$y_j$$$, meaning that both ends of the road is city $$$x_j$$$.
Now the people on Planet E wants to build some stable for the horses. However the horses on Planet E has a strange habit: they must move exactly $$$k$$$ steps everyday. For each step, a horse must choose one of the roads that connects to its current city, and moves to the city on other end of the road. Hence we shall only build stables at city $$$i$$$ if a horse at city $$$i$$$ can move back to city $$$i$$$ after $$$k$$$ steps.
Can you help the people on Planet E to determine how many cities they can build stables at?
The first line contains a positive integer $$$T$$$ ($$$T \le 20$$$), the number of testcases.
Each testcase starts with a line consisting of three integers $$$n, m, k$$$ ($$$1 \le n \le 50$$$, $$$0 \le m \le 2500$$$, $$$0 \le k \le 10^9$$$), the number of cities and roads, and the number of steps a horse must move everyday. Then there are $$$m$$$ lines followed, each consisting of two integers $$$x_j, y_j$$$ ($$$0 \le x_j \le n - 1$$$, $$$0 \le y_j \le n - 1$$$), meaning that the $$$j$$$-th road connects city $$$x_j$$$ and city $$$y_j$$$.
For each testcase, output a single line consisting of the number of cities that can have a stable built.
3 3 2 3 0 1 0 2 3 2 4 0 1 0 2 5 5 5 0 1 1 2 2 0 3 4 4 0
0 3 4
In the last testcase, we can build stables at every cities but city $$$3$$$.
City $$$0$$$: $$$0 \to 1 \to 2 \to 0 \to 1 \to 0$$$.
City $$$1$$$: $$$1 \to 2 \to 0 \to 1 \to 2 \to 1$$$.
City $$$2$$$: $$$2 \to 0 \to 1 \to 2 \to 0 \to 2$$$.
City $$$4$$$: $$$4 \to 0 \to 1 \to 2 \to 0 \to 4$$$.
On Planet E, people like shopping a lot!
However they do not have electronic payments and can only pay by coins. There are $$$n$$$ different coins on Planet E, with different integral values $$$c_0, c_1, \dots, c_{n - 1}$$$ respectively. The cashiers on Planet E always have infinite number of each coins for changes, and hence very often there are multiple ways to give an $$$m$$$ dollar change.
The people on Planet E believe that the number of ways to give change affect their luck throughout the day, but it is too hard for them to count the number.
Can you help the people on Planet E to count the number of ways to give change? Since the number may be huge, you only need to answer the number module $$$1000000007$$$ ($$$10^9 + 7$$$).
The first line contains a positive integer $$$T$$$ ($$$T \le 10$$$), the number of testcases.
Each testcase starts with a line consisting of two integers $$$n, m$$$ ($$$1 \le n \le 100$$$, $$$1 \le m \le 10000$$$), the number of coins and the amount of change. Then the following line consists of $$$n$$$ integers $$$c_0, c_1, \dots, c_{n - 1}$$$ ($$$1 \le c_i \le 10000$$$), the coin values.
For each testcase, output a single line consisting of the number of ways to give exactly $$$m$$$ dollar change, module $$$10^9 + 7$$$.
5 1 100 1 4 10 5 7 2 3 3 100 1 2 3 4 100 101 102 103 104 5 10000 5 4 3 2 1
1 5 884 0 649632988
In the second case, the five ways are 3 + 7, 5 + 5, 2 + 3 + 5, 2 + 2 + 3 + 3 and 2 + 2 + 2 + 2 + 2.
On Planet E, snails are born in infinitely deep wells!
Initially a snail is at $$$n$$$ meters below the ground. During the daytime the snail try very hard to climb up, and goes up by $$$a$$$ meters. It can escape the well once it touches the ground. However during the night the snail has to sleep and falls back by $$$b$$$ meters. Hence it may happens that an unfortunate snail stucks in the well forever.
Can you help the snails on Planet E to determine the number of days they need to escape the well?
The first line contains a positive integer $$$T$$$ ($$$T \le 10$$$), the number of testcases.
Each testcase contains three integers $$$n, a, b$$$ ($$$1 \le n \le 1000$$$, $$$0 \le a \le 1000$$$, $$$0 \le b \le 1000$$$), the initial position of the snail, the length it climbs up during the daytime, and the length it falls during the night.
For each testcase, output a single line consisting of the number of days the snail need to escape the well. Output "-1" (without quotes) if it is impossible.
3 10 5 2 10 5 5 5 5 6
3 -1 1