Professor Oak has two words of length $$$n$$$, $$$a_{1}$$$ and $$$a_{2}$$$. Both words are made up of lowercase letters from a to z. Some of the letters are unreadable, and the professor has replaced them with a $$$?$$$.
The professor wonders if it is possible to replace the $$$?$$$ with lowercase letters so that the word $$$a_{1}$$$ is strictly lexicographically smaller than $$$a_{2}$$$.
The input consists of several cases.
Each case starts with an integer $$$n$$$ followed by the words $$$a_{1}$$$ and $$$a_{2}$$$.
For each case, write a line with the answer 'si' if it is possible and 'no' otherwise.
The sum of all $$$n$$$ is less than 10,000,000.
2 ib ?b 5 pbi?v pbiav
si no
In the country of Enelogonia, there is a problem: every year, the sea level rises. This has caused the country to be divided into islands. The government wants to know the number of islands the country will be divided into at the end of each year.
Initially, the country is a line divided into $$$n$$$ segments; each segment has a height of $$$a_{i}$$$ meters. At the beginning of the first year, the sea level is at $$$0$$$, and at the end of the i-th year, the level is at $$$m_{i}$$$. It holds that if $$$i \lt j$$$, then $$$m_{i} \lt m_{j}$$$.
Given the $$$n$$$ heights of the segments and the sea levels at the end of each year, determine how many islands there are at the end of each year.
When the i-th segment goes underwater, the (i+1)-th and (i-1)-th segments become part of different islands because they are separated by water (this is in case both segments are above sea level).
A segment goes underwater when the sea level is equal to or greater than its height.
The input consists of several cases.
Each case starts with a line containing the integers $$$n$$$ and $$$k$$$. On the second line, there are the $$$n$$$ integers $$$a_{i}$$$, and on the third line the $$$k$$$ integers $$$m_{i}$$$.
For each case, write a line with $$$k$$$ integers separated by a space, where the i-th integer is the number of islands at the end of the i-th year.
$$$1 \leq a_{i}, m_{i} \leq 1000000$$$
Case 1: 30 points
$$$1 \leq n \leq 1000$$$
$$$k = 1$$$
Case 2: 30 points
$$$1 \leq n \leq 1000$$$
$$$1 \leq k \leq 1000$$$
Case 3: 40 points
$$$1 \leq n \leq 100000$$$
$$$1 \leq k \leq 100000$$$
7 1 9 1 6 1 3 7 2 5 10 5 9 5 4 10 3 2 5 6 2 6 3 4 6 8 9
3 3 4 2 2 1
Baq is a very diligent student who is faced with the difficult task of choosing subjects for the next year. Since he is very interested in learning mathematics, he wants to choose the maximum number of subjects possible. Additionally, he does not want to skip any classes, so he does not want any subjects to overlap (although he has no problem attending multiple subjects consecutively). Classes must start and end on the hour, but since Baq lives in a somewhat strange universe, days do not necessarily have 24 hours.
Knowing the start and end times of each subject, can you determine the maximum number of subjects that Baq will be able to take?
The input consists of several cases. Each case starts with $$$n$$$, the number of subjects offered, and $$$m$$$, the number of hours in a day. This is followed by $$$n$$$ lines with two integers $$$a_i$$$ $$$b_i$$$, representing the start and end times of the i-th subject. It is guaranteed that $$$0 \leq a_i \lt b_i \leq m$$$.
For each case, print a line with the maximum number of subjects that can be taken.
A (5 points): Cases where $$$n = 2$$$, $$$1 \leq m \leq 10$$$.
B (5 points): Cases where $$$0 \leq n \leq 10$$$, $$$m = 2$$$.
C (15 points): Cases where $$$0 \leq n \leq 10$$$, $$$1 \leq m \leq 10$$$.
D (30 points): Cases where $$$0 \leq n \leq 1000$$$, $$$1 \leq m \leq 1000$$$.
E (45 points): Cases where $$$0 \leq n \leq 5 \cdot 10^5$$$, $$$1 \leq m \leq 5 \cdot 10^5$$$.
3 2 0 1 0 2 1 2 2 2 0 1 0 2 4 8 0 1 1 2 3 7 4 7
2 1 3
After a night of incessant substance abuse, Pickle Rick must reach his spacecraft as soon as possible to leave the planet, as his insolence has earned him half a dozen dangerous enemies. Pickle Rick is a pickle, and we can consider his shape to be that of a cuboid with dimensions $$$1\times 1\times 2$$$. He is standing on the cell $$$(0, 0)$$$ of an infinite grid of $$$1\times 1$$$ cells. When we say he is standing, we mean that he is resting on either of his two square faces with dimensions $$$1\times 1$$$.
His spacecraft is located at position $$$(x, y)$$$ on the grid, and he wants to reach it standing up and in the least number of moves. To move, Pickle Rick chooses one of his edges in contact with the ground and rotates around it until he touches the ground again. For example, from his initial position, he can rotate around the right edge to lie flat on the cells $$$(1, 0)$$$ and $$$(2, 0)$$$ and then rotate again around the right edge to stand on cell $$$(3, 0)$$$. This is a total of two moves.
Due to his state of inebriation, Pickle Rick does not reason clearly. Help him. You must calculate the minimum number of moves he must make to reach the cell where his spacecraft is located while standing.
The input starts with an integer $$$t$$$, the number of cases. This is followed by $$$t$$$ lines, one for each case, with the coordinates $$$x$$$ and $$$y$$$ of the cell where the spacecraft is located.
For each case, print a line with a single integer: the minimum number of moves that Pickle Rick must make to reach his spacecraft while standing.
$$$1\leq t\leq 10^5$$$
10 points: $$$0\leq x, y \lt 1000$$$ and both are multiples of $$$3$$$
20 points: $$$0\leq x, y \lt 10$$$
20 points: $$$0\leq x, y \lt 100$$$
40 points: $$$0\leq x, y \lt 1000$$$
10 points: $$$0\leq x, y \lt 10^9$$$
3 0 0 3 1 0 2
0 3 4