James has a large rectangular piece of sheet metal; its width is $$$w_1$$$ millimeters, and its height is $$$h_1$$$ millimeters. This massive piece is hard to store and move around, so James and his friends want to make smaller pieces.
They found a machine that could solve this problem. The machine has a rectangular form of width $$$w_2$$$ and height $$$h_2$$$ millimeters. To use it, you put a piece of sheet metal under the form. It's allowed to have some parts of the form not be above the sheet metal. You can rotate the piece of sheet metal, but you have to make sure that the sides of both rectangles (the piece and the form) are parallel to coordinate axes.
After running the machine, everything under the form will get burnt out and be unusable. Everything that was not under the form will fall off; James and his friends must take that away with them. In addition, the remaining part might will apart into several separate pieces. If the form's edge coincides with the sheet metal's edge, we also consider that the sheet metal is disconnected there.
To ease the task of taking everything away, find a way to apply the machine to the piece of sheet metal such that the maximum area of all remaining pieces is as small as possible. In case there are no pieces left, print 0.
The only line of the input contains four integers $$$w_1$$$, $$$h_1$$$, $$$w_2$$$, $$$h_2$$$ ($$$1 \le w_1, h_1, w_2, h_2 \le 10^6$$$) — widths and heights of the piece of sheet metal and the form.
Print the minimum possible area of the largest remaining piece.
| Subtask | Point | Constraints |
| 1 | 50 | $$$w_2 \le h_2 \le w_1 \le h_1$$$ |
| 2 | 50 | No additional constraints |
2 3 1 3
1.5
2 3 3 3
0
2 3 2 2
1
2 3 3 1
1.5
The school canteen has four types of fruits: apricots, bananas, apples, and pears. There are three different possible sets of fruits available for lunch:
The canteen's employees want to assemble as many lunch fruit sets for children as possible. Help them do it!
Since the number of fruits delivered is different every day, you need to solve the problem for multiple test cases.
The first line of the input contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.
The following $$$t$$$ lines contain a description of each test case. Each line contains four integers $$$a$$$, $$$b$$$, $$$c$$$, and $$$d$$$ ($$$1 \le a, b, c, d \le 10^9$$$) — the number of apricots, bananas, apples, and pears, respectively.
For each test case, print the maximum number of fruit sets it's possible to make.
| Subtask | Score | Constraints |
| $$$1$$$ | $$$10$$$ | $$$t \le 10$$$; $$$a, b, c, d \le 10$$$ |
| $$$2$$$ | $$$20$$$ | $$$t \le 10^4$$$; $$$a, b, c, d \le 10$$$ |
| $$$3$$$ | $$$20$$$ | $$$t \le 10$$$; $$$a, b, c, d \le 200$$$ |
| $$$4$$$ | $$$20$$$ | $$$t \le 10$$$; $$$a, b, c, d \le 10^6$$$ |
| $$$5$$$ | $$$30$$$ | No additional constraints |
63 3 3 33 1 4 14 3 2 13 3 6 59 7 6 79 10 10 6
2 2 2 3 5 6
In the first case, you can make two sets of fruits: one of type $$$1$$$ and one of type $$$3$$$.
In the second case, one of the possible answers is $$$(2, 3)$$$.
In the third case, the optimal answer is $$$(1, 1)$$$.
In the fourth case, you can make three sets of type $$$3$$$.
Let's play a game! The game field is a rectangular grid with $$$n$$$ rows and $$$m$$$ columns $$$n$$$ and $$$m$$$ are both odd. There are domino tiles on this grid; each domino covers two horizontally or vertically adjacent cells. At the beginning of the game, every cell, except for one, is covered by precisely one domino tile, and one cell is empty.
During each more, you can slide any domino tile in the direction parallel to its orientation, provided that the cell in that direction is empty. You can perform this move as many times as you like, and you can stop at any time.
Every cell on the game field has a positive or negative cost. When you slide a domino tile, some cell previously covered by that tile becomes empty. If this is the first time this cell becomes empty during the game, you add its cost to the overall score.
Figure out a sequence of moves that maximizes the total score, that is, the sum of the costs of all cells that were empty at least once during the game.
The first line contains two integers $$$n$$$ and $$$m$$$ — the number of rows and columns of the grid ($$$1 \le n, m \le 499$$$; $$$n$$$ and $$$m$$$ are odd). The following $$$n$$$ lines contain $$$m$$$ characters each — the initial arrangement of dominoes. The empty cell is denoted by ., a horizontal tile — by a pair of characters < (the left cell) and > (the right cell), and a vertical tile — by a pair of character ^ (the top cell) and v (the bottom cell). It's guaranteed that the arrangement is correct and there's one empty cell.
The following $$$n$$$ lines contain $$$m$$$ integers each, describing the costs of cells. The cost of each cell is an integer from $$$-1000$$$ to $$$1000$$$ inclusive. The initially empty cell has cost $$$0$$$.
Print a single integer — the maximum possible final score.
| Subtask | Points | Constraints |
| 1 | 10 | $$$n = 1$$$, $$$m \le 3$$$ |
| 2 | 24 | $$$n = 1$$$, $$$m \le 499$$$ |
| 3 | 14 | $$$n, m \le 7$$$ |
| 4 | 23 | $$$n, m \le 499$$$, all costs are non-negative |
| 5 | 29 | No additional constraints |
1 5 <>.<> 5 2 0 9 -2
5
3 3 <>^ ^.v v<> 1 1 1 1 0 1 1 1 1
0
This is a "run-twice" problem; your program will be run twice for each test.
Your task is to implement a program that transmits data through an unreliable channel. On the first end (during the first run), you get a binary string of length $$$n$$$, and your program has to be able to recover it on the other end of the channel (during the second run).
Thankfully, the channel allows you to send strings with $$$k$$$ different types of characters ($$$k \gt 2$$$) and use strings of length $$$m$$$ ($$$m \gt n$$$). But, there is a catch: when you transmit a string, all occurrences of some type of character will be removed. The remaining characters will still follow in the same order. Your job is to develop an algorithm to encode the input string, so it's possible to recover it after the transmission.
To speed up the testing, in each test, you will need to encode and transmit $$$t$$$ binary strings at once. These strings will be transmitted independently, and different strings might have different types of characters removed from them.
During the first run, the first line contains an integer $$$1$$$. The second line contains four integers $$$t$$$, $$$n$$$, $$$m$$$, and $$$k$$$ — the numbers of strings to encode, the length of each string, the maximum possible length of the encoded string, and the number of types of characters you can use ($$$1 \le t \le 100$$$, $$$k = 3$$$ or $$$k = 4$$$).
The following $$$t$$$ lines contain a binary string of length $$$n$$$.
If $$$k = 4$$$, then you can use A, B, C, D in the encoded string. If $$$k = 3$$$, then you can only use A, B, and C.
During the second run, the first line contains an integer $$$2$$$. The second line contains four integers $$$t$$$, $$$n$$$, $$$m$$$, and $$$k$$$, similar to the previous description.
Then, the following $$$t$$$ lines contain strings outputted by your program during the first run, but every string is missing some type of character. These strings are given to you in the same order as during the first run.
During the first run, print $$$t$$$ nonempty strings with at most $$$m$$$ characters from { A, B, C, D } or { A, B, C }, depending on the value of $$$k$$$.
The character to be deleted will be chosen in such a way that the resulting string is not empty. For example, if you output CCCC, all characters of type C will not be removed from the string.
During the second run, you need to decode these strings into initial binary strings of length $$$n$$$.
| {Points} | {Constaints} | |
| 1 | 27 | $$$t = 1$$$, $$$n = 10$$$, $$$k = 4$$$, $$$m = 20$$$ |
| 2 | 14 | $$$t = 100$$$, $$$n = 100$$$, $$$k = 4$$$, $$$m = 200$$$ |
| 3 | 28 | $$$t = 100$$$, $$$n = 100$$$, $$$k = 3$$$, $$$m = 200$$$ |
| 4 | 20 | $$$t = 100$$$, $$$n = 100$$$, $$$k = 3$$$, $$$m = 190$$$ |
| 5 | 11 | $$$t = 100$$$, $$$n = 100$$$, $$$k = 3$$$, $$$m = 180$$$ |
1
2 10 20 4
0111011001
1111111110
BAACBBACDCDDAACCAABD
DABBADCBCBBCCACA
2
2 10 20 4
AACACDCDDAACCAAD
DBBDCBCBBCCC
0111011001
1111111110
In the example, you need to transmit two binary strings 0111011001 and 1111111110, using strings of length $$$m = 20$$$ and $$$k = 4$$$ different characters. For example, suppose that after the first run, your program outputted BAACBBACDCDDAACCAABD for the first string and DABBADCBCBBCCACA for the second string.
Before the second run, the judges' program removes some type of character from each string. For example, here, we removed all B's from the first string and all A's from the second string. You have to restore and print the initial binary strings 0111011001 and 1111111110.
The Innopolis Summer School has announced its new installment. This year, the organization is a little different: there are $$$n$$$ parallels with levels ranging from $$$0$$$ to $$$n - 1$$$. Each parallel is intended to have at most $$$k$$$ students in it.
According to their past performance and training results, each student received their approximate level — also an integer from $$$0$$$ to $$$n - 1$$$.
Based on the experience of past years, the time spent studying at parallel $$$x$$$ for a student of level $$$L$$$ will be beneficial if the student's level differs from the parallel by at most $$$d + L \cdot \frac{p}{100}$$$. In other words, $$$|x - L| \le d + L \cdot \frac{p}{100}$$$.
Every day the admission system is very busy: there are many new applications and cancellations. To help students plan their summer, organizers want to figure out how many students they can invite such that everyone's participation in the summer school is beneficial.
We will describe each day as one of two types of events:
Write a program that finds the maximum number of students the organizers can invite, so everyone's participation is beneficial for them.
The first line contains integers $$$n$$$, $$$k$$$, $$$d$$$ and $$$p$$$ — the number of parallels, the maximum size of every parallel, and the constants that define if the study is beneficial, respectively ($$$1 \le n \le 5 \cdot 10^5$$$, $$$1 \le k \le 10^9$$$, $$$0 \le d \le n$$$, $$$0 \le p \le 100$$$).
The second line contains one integer $$$m$$$ — the number of days you need to process ($$$1 \le m \le 5 \cdot 10^5$$$).
The following $$$m$$$ lines contain descriptions of events of each day. Each line contains either + L v, or - L v, where $$$L$$$ is the student's level, and $$$v$$$ is the number of applications/cancellations ($$$0 \le L \lt n$$$, $$$1 \le v \le 10^9$$$).
Print $$$m$$$ integer: the maximum number of students the organizers can invite after every change.
Let's define $$$C$$$ as the maximum number of applications of the same level present in the system at some moment.
| Subtask | Points | Constraints |
| 1 | 10 | $$$n \le 5$$$, $$$m \le 10$$$, $$$C \le 4$$$ |
| 2 | 10 | $$$n \le 30$$$, $$$m \le 100$$$, $$$C \le 30$$$ |
| 3 | 10 | $$$n, m \le 100$$$, $$$C \le 10^6$$$ |
| 4 | 10 | $$$n, m \le 10^5$$$, $$$d = 0$$$ |
| 5 | 10 | $$$n, m \le 10^5$$$, $$$d \le 1$$$ |
| 6 | 10 | $$$n, m \le 10^5$$$, $$$p = 0$$$ |
| 7 | 10 | $$$n, m \le 10^5$$$, $$$v = 1$$$ |
| 8 | 10 | $$$n, m \le 10^5$$$, only events of type '+' |
| 9 | 10 | $$$n, m \le 10^5$$$ |
| 10 | 10 | No additional constraints |
5 2 1 25 5 + 4 7 - 4 3 + 2 5 + 3 5 - 3 2
6 4 8 8 8
5 2 1 1 6 + 0 4 + 1 3 - 0 2 + 3 7 + 4 1 - 3 6
4 6 5 10 10 7
In the first example, students of level 4 can study in parallels 2, 3, and 4. That means that after the first-day event, 6 students out of 7 can study beneficially.
In the second example, every student can only study at the parallel, which level is either equal to the student's level or differs from it by at most one.