You are the creator of a famous programming contest platform and have recently suffered a DDoS attack. Faced with this problem, you have decided to implement an anti-DDoS system on your platform to be able to ignore requests from malicious IPs before they cause problems. In a few hours, an important contest is scheduled to start, which has taken a long time to prepare and people from all over the world have been waiting for months, but the platform is still in danger! As a great programmer, you have announced that before the start of the contest, the anti-DDoS system will be up and running and the contest will continue. You must implement it on time!
A byte consists of 8 digits in binary that encode a number between 0 and 255. In current computers, they function as the minimum unit of information, as the computer's memory works with bytes.
An IP consists of a string formed by four numbers representable in a single byte (that is, numbers between 0 and 255, without leading zeros) separated by dots (Examples: "192.168.1.1", "127.0.0.1"). These are used to identify different computers on the internet and to know to whom each packet belongs.
The system constantly receives data packets, which consist of the sender's IP, the exact time it was sent, and the size of the packet in bytes. The system can accept them to reach the main server or ignore them. It is based on the parameters $$$\alpha$$$, $$$\beta$$$, and $$$\delta$$$ to decide which packets to ignore.
It is also possible for the server to receive a new configuration of the parameters $$$\alpha$$$, $$$\beta$$$, and $$$\delta$$$ at any time.
A packet should be ignored if, in the last $$$\delta$$$ units of time, one or more of the following conditions are met:
- $$$\alpha$$$ or more packets from the same IP have been accepted. - $$$\beta$$$ or more bytes from the same IP have been accepted.
When we talk about the last $$$\delta$$$ units of time, we refer to the moments in time (if the current packet has time $$$t$$$) from $$$t-\delta+1$$$ to $$$t$$$.
For example, if $$$t=8$$$, and $$$\delta=3$$$, only packets at times 6, 7, and 8 would be considered.
An integer $$$T$$$ indicates the number of cases.
For each case, an integer $$$Q$$$, followed by $$$Q$$$ lines with the following format:
First, an integer $$$T_i$$$ denoting the type of query for the $$$i$$$-th line. Followed by the following depending on $$$T_i$$$:
- If $$$T_i$$$ = 1, a string and two integers: IP, current time, and packet size (in bytes) in this order. - If $$$T_i$$$ = 2, three integers: the new values of $$$\alpha$$$, $$$\beta$$$, and $$$\delta$$$ in this order.
The first line will always be of type 2 to set the initial values of $$$\alpha$$$, $$$\beta$$$, and $$$\delta$$$.
All given times are strictly increasing values with respect to previous queries.
For each query of type 1 ($$$T_i$$$ = 1):
- If a packet is accepted, you have to display the line 'ac' on the screen. - If a packet should be ignored, you must display the line 'ig' on the screen.
At the end of each case, put a line with '–'
$$$1 \leq T \leq 5$$$
For every time $$$t$$$ that appears in any query: $$$0 \leq t \leq 10^{12}$$$
For every packet size $$$s$$$ that appears in any query: $$$1 \leq s \leq 10^{12}$$$
For every $$$\alpha$$$, $$$\beta$$$, $$$\delta$$$ that appears in any query: $$$1 \leq \alpha, \beta, \delta \leq 10^{12}$$$
18 points: $$$1 \leq Q \leq 10^4$$$
21 points: $$$1 \leq Q \leq 10^5$$$, $$$\alpha = \beta = 1$$$
29 points: $$$1 \leq Q \leq 10^5$$$, all IPs in a case are the same
32 points: $$$1 \leq Q \leq 10^5$$$
1 4 2 10 7 24 1 253.70.210.43 12158 5 1 253.70.210.43 12162 2 1 253.70.210.43 12170 1
ac ac ig --
1 15 2 2105082674 2007068026 1625093961 1 103.73.59.80 5745 59350582 1 21.2.88.218 5848 417030385 2 4158745174 347394302 820605438 1 33.8.233.115 6002 599300816 2 689106729 77607978 3957107113 1 21.2.88.218 8729 2665793048 1 75.141.72.177 15173 16722561 1 75.141.72.177 22673 3015565887 1 100.226.246.150 23729 2710901173 2 2510564959 2153623029 2464461242 1 23.125.221.98 26766 2777545804 2 3731636496 2747428512 2847248015 1 100.226.246.150 33554 1717343080 1 100.226.246.150 40000 2539933220
ac ac ac ig ac ac ac ac ac ig --
On a bridge there are $$$n$$$ holes, the $$$i$$$-th hole goes from point $$$a_i$$$ to point $$$b_i$$$. The company in charge of repairing the holes is considering placing wooden pieces to cover the holes. To make the budget, they need to know how many meters of wood they need to cover all the holes, and this number depends on the number of wooden pieces they want to make (a single piece covering all the holes, two pieces covering half and half, one piece for each hole, etc).
Write $$$n$$$ numbers where the $$$i$$$-th number indicates the minimum number of meters needed to cover all the holes with $$$i$$$ wooden pieces.
The input starts with an integer $$$t$$$ indicating the number of cases.
Each case starts with an integer $$$n$$$, followed by $$$n$$$ lines with two integers $$$a_i, b_i$$$.
It holds that $$$a_i \lt b_i$$$ and $$$b_i \lt a_{i+1}$$$.
For each case, write a line with $$$n$$$ integers separated by a space.
$$$1 \leq t \leq 100$$$
21 Points: $$$1 \leq n \leq 100$$$ , $$$0 \leq a_i, b_i \leq 1000$$$
32 Points: $$$1 \leq n \leq 1000$$$ , $$$0 \leq a_i, b_i \leq 10^4$$$
47 Points: $$$1 \leq n \leq 10^4$$$ , $$$0 \leq a_i, b_i \leq 10^9$$$
3 3 0 1 3 5 6 7 7 0 5 9 10 12 15 25 26 30 35 37 38 40 44 5 0 20 21 30 31 40 41 50 55 60
7 5 4 44 34 30 26 24 22 20 60 55 54 53 52
María has a sequence of $$$n$$$ integers $$$a_i$$$. María only likes VonitA sequences, which consist of either an increasing sequence (i.e., $$$a_i \leq a_{i+1}$$$) until a certain point, and then a decreasing sequence (i.e., $$$a_i \geq a_{i+1}$$$), or a decreasing sequence followed by an increasing one.
Formally, they must satisfy one of the following properties:
- There is an integer $$$0 \leq k \lt n$$$ such that if $$$0 \leq i \lt k$$$ then $$$a_i \leq a_{i+1}$$$, and if $$$k \leq i \lt n-1$$$ then $$$a_i \geq a_{i+1}$$$.
- There is an integer $$$0 \leq k \lt n$$$ such that if $$$0 \leq i \lt k$$$ then $$$a_i \geq a_{i+1}$$$, and if $$$k \leq i \lt n-1$$$ then $$$a_i \leq a_{i+1}$$$.
What is the minimum number of elements $$$a_i$$$ that María needs to modify in order for her sequence to be VonitA?
The input begins with an integer $$$t$$$ indicating the number of cases.
Each case begins with an integer $$$n$$$, and the next line contains $$$n$$$ integers $$$a_i$$$.
For each case, output a line with the answer.
$$$1 \leq t \leq 100$$$
$$$1 \leq n \leq 10^5$$$
$$$0 \leq a_i \leq 10^9$$$
11 Points: $$$n \leq 15$$$
15 Points: $$$a_i,n \leq 100$$$
10 Points: $$$n \leq 100$$$
15 Points: $$$a_i,n \leq 1000$$$
10 Points: $$$n \leq 1000$$$
39 Points: No restrictions
3 7 1 2 3 4 3 2 1 8 1 2 1 2 1 2 1 2 6 1 4 3 2 3 4
0 3 1
A group of $$$n$$$ friends has gathered to exchange Pokémon tazos. Each of them has brought $$$n_i$$$ identical tazos. Fortunately, each of the $$$n$$$ friends has brought a different type of tazo.
The exchange works as follows:
Initially, all friends have their $$$n_i$$$ tazos in their hands, from there they repeat the following steps until no one has tazos in their hands:
- Among the tazos they have in their hands, they keep the ones they want in their pocket, in the same turn they cannot choose to keep more than one tazo of each type. - The tazos they do not want are given to one of the other friends.
The $$$n$$$ friends want to get the maximum number of tazos, so in each turn they will keep the maximum number of tazos they can. It does not matter if they have repeated tazos in their pocket.
In addition, each one will always give the tazos they have in their hands to their best friend, $$$a_i$$$.
At the end of the exchange, how many tazos does each friend have?
The input starts with an integer $$$t$$$ indicating the number of cases.
Each case starts with a line with an integer $$$n$$$.
The next line contains $$$n$$$ integers $$$n_i$$$ indicating the number of tazos for each friend.
The last line of the case contains $$$n$$$ integers $$$a_i$$$ indicating the best friend of each friend.
For each case, write a line with $$$n$$$ integers, where each integer indicates the number of tazos that each friend ends up with.
$$$1 \leq t \leq 100$$$
$$$0 \leq a_i \leq n-1$$$
$$$1 \leq n_i \leq 10^{12}$$$
$$$2 \leq n \leq 10^5$$$
5 Points: $$$n_i \leq 2$$$
11 Points: $$$n,n_i \leq 500$$$
13 Points: $$$n \leq 500$$$
7 Points: For $$$i \gt 0$$$, we have $$$a_i = i-1$$$, and $$$a_0 = n-1$$$
10 Points: For $$$i \gt 0$$$, we have $$$a_i = i-1$$$
13 Points: For $$$i \gt 0$$$, we have $$$a_i \lt i$$$, and $$$a_0 = 1$$$
41 Points: no restrictions
5 3 2 1 2 1 0 1 4 3 4 4 2 3 2 0 1 10 1 2 3 4 5 6 7 8 9 10 9 0 1 2 3 4 5 6 7 8 5 100000000 123456789 987654321 12 3 2 3 0 1 0 5 234125 45234 2345 5623 435 2 0 1 2 3
1 3 1 3 4 2 4 10 9 8 7 6 5 4 3 2 1 543827161 61728401 543827162 61728400 1 95919 95919 95921 2 1
Pedro has $$$n$$$ stones forming a line and wants to paint them with $$$c$$$ different colors in such a way that there are no $$$k \geq 2$$$ consecutive stones of the same color.
He wants to know in how many ways he can paint the stones.
The input starts with a line with an integer $$$t$$$ indicating the number of cases.
Each case consists of four integers $$$n$$$, $$$c$$$, $$$k$$$, and $$$p$$$. Where $$$p$$$ is a prime number with $$$10^8 \leq p \leq 10^9$$$.
The answer can be very large, write the result modulo $$$p$$$.
For each case, write a line with the result modulo $$$p$$$.
$$$1 \leq t \leq 100$$$
$$$2 \leq k \leq n \leq 10^6$$$
$$$1 \leq c \leq 10^9$$$
$$$10^8 \leq p \leq 10^9$$$
11 Points: $$$n,c \leq 10$$$ and $$$c^n \leq 10^4$$$
13 Points: $$$n,c \leq 100$$$
19 Points: $$$n \leq 1000$$$
12 Points: $$$n \leq 50000$$$ and $$$c \leq 10$$$
7 Points: $$$n \leq 50000$$$ and $$$c \leq 100$$$
38 Points: no restrictions
5 7 3 6 100000007 10 2 5 100000037 100 100 50 100000039 1000 123456789 345 100000049 1000000 987654321 123456 100000073
2172 802 62324845 55895361 81968913