In previous meetings of the Independent Organization of Epizootics, also known as the World Organization for Animal Health, everyone gathered in Barcelona to discuss the most relevant topics. However, every year they faced several problems.
Many members do not know the distance from the meeting place to the hotel, so when they want to take a taxi, they do not know how much money to bring. It is clear that they will not bring more than necessary as they fear losing money. For this and other reasons, this year the meeting will be held remotely.
Specifically, we will assume that Barcelona is an infinite grid with the origin at $$$(0,0)$$$, with blocks measuring 10 meters on each side and with an infinite diagonal that crosses the city passing through $$$(0,0)$$$ and $$$(10,10)$$$. Since taxi drivers want to minimize travel time, the taximeter does not count the distance traveled on the Diagonal. For simplicity, we will assume that all streets are bidirectional. Therefore, the distance in Barcelona is the minimum distance between two points traveling along the streets of Barcelona.
To facilitate future meetings, the organization asks you to help them calculate the distance in Barcelona from the meeting place to various hotels.
The input consists of several cases.
The first line of each case contains 2 integers $$$x_r, y_r$$$, the coordinates of the meeting place, followed by $$$Q$$$ integers, the number of hotels to consider. The next line consists of $$$Q$$$ pairs of integers $$$x_i, y_i$$$, the coordinates of the i-th hotel, separated by spaces.
It is guaranteed that:
- All points are on a street, meaning one of the two coordinates is a multiple of ten.
For each case, you must print $$$Q$$$ non-negative integers separated by a newline at the end.
The i-th non-negative integer is the distance in Barcelona between the i-th hotel and the meeting place.
$$$ 1 \leq x_i, y_i, x_r, y_r \leq 10^7 \ \forall i$$$
$$$ 1 \leq Q \leq 10^4 $$$
Subcases
Subcase 1 (10 pt):
- All coordinates are multiples of 10.
- $$$0 \leq x_i, x_r \leq 10^3$$$
- $$$10^6 \leq y_i, y_r \leq 10^6 + 10^3$$$
Subcase 2 (20 pt):
- All coordinates are multiples of 10.
- $$$0 \leq x_i, x_r \leq 10^4$$$
- $$$10^6 \leq y_i, y_r \leq 10^6 + 10^4$$$
Subcase 3 (30 pt):
- All points are multiples of 10.
Subcase 4 (40 pt):
- No additional restrictions.
0 1000000 2 0 1000010 10 1000010 0 1000020 2 0 1000010 10 1000010
10 20 10 20
0 1000000 2 0 1010000 9090 1010000
10000 19090
0 0 2 10 10 20 10
0 10
0 5 2 10 15 6 10
10 9
After spending an hour and a half on the final Mathematics exam, struggling in vain to find the answers to the devilish questions that have come up, you decide it's time to give up, make up the remaining answers, submit, and pray for a passing grade. Fortunately for you, the exam is multiple choice, and each question has three possible options: A, B, or C, and you already know some of the answers. Each correct answer is worth one point, and incorrect answers do not subtract points. You remember from the practice exams you took yesterday that the teacher never puts two consecutive questions with the same answer, meaning that if question 1 is A, then question 2 cannot be A. Your goal is to fill out the exam in such a way that you maximize the number of points you can secure in the worst-case scenario.
The input will consist of an integer $$$t$$$, followed by $$$t$$$ test cases. Each case will have on one line $$$N$$$, the number of questions on the exam, and on the next line a string with $$$N$$$ characters. The $$$i$$$-th character will be 'A', 'B', or 'C' if you know the answer to question $$$i$$$, and '?' if you do not know it.
One line per case with the number of points you can secure on the exam.
33 points: $$$1 \leq N \leq 8$$$, $$$t = 10$$$
11 points: $$$1 \leq N \leq 10^5$$$, $$$t = 50$$$, no two '?' are consecutive.
56 points: $$$1 \leq N \leq 10^5$$$, $$$t = 50$$$
2 6 A??B?C 5 A???A
5 3
Before the battle against the final boss, you are going to buy some items to improve your chances. But this store is a bit different from the ones you are used to: there are $$$N$$$ stacks, the $$$i$$$-th stack contains $$$m_i$$$ items, and the $$$j$$$-th item of the $$$i$$$-th stack adds $$$a_{ij}$$$ attack units to your character. Initially, you can only buy the first item from each stack. When you buy an item, the next one in the stack is unlocked, and you can buy it as well. Additionally, all items have the same price: 15 coins. Your goal is to spend the $$$C$$$ coins you have in order to maximize your attack.
The input will consist of an integer $$$t$$$, followed by $$$t$$$ test cases. In the first line of each case, there will be $$$N$$$ and $$$C$$$. Next, there will be $$$N$$$ lines, the $$$i$$$-th of which describes stack $$$i$$$: first comes $$$m_i$$$, the number of items in that stack, followed by $$$m_i$$$ integers, the $$$j$$$-th of which is $$$a_{ij}$$$.
One line per case with the maximum amount of attack that can be obtained by buying some items in the store.
For all test cases, it holds that $$$-10^9 \leq a_{ij} \leq 10^9$$$.
25 points: $$$1 \leq N \leq 12$$$, $$$1 \leq C \leq 150$$$, $$$1 \leq m_i \leq 12$$$, $$$t = 50$$$.
25 points: $$$1 \leq N \leq 60$$$, $$$1 \leq C \leq 1000$$$, $$$1 \leq m_i \leq 60$$$, $$$t = 100$$$.
50 points: $$$1 \leq N \leq 250$$$, $$$1 \leq C \leq 3000$$$, $$$1 \leq m_i \leq 200$$$, $$$t = 150$$$.
3 1 29 4 1 2 3 4 2 30 2 -2 1 3 -1 -1 3 5 90 3 5 1 10 3 6 1 2 3 7 1 3 3 8 1 4 3 9 1 5
1 0 40
How many words of length $$$n$$$ formed by 'a' and 'b' are there that do not contain the word 'abbaaaba'?
Write the result modulo $$$10^{9}+7$$$.
An integer $$$n$$$.
A line with the result.
$$$1 \leq n \leq 10^{18}$$$
There are 100 cases and each case is worth one point.
8
255