Masha wants to wallpaper a wall without windows and doors that is $$$a$$$ centimeters long and $$$h$$$ centimeters high. Masha has already chosen beautiful wallpaper with a pattern, and now she needs to calculate how many rolls to buy.
Each roll has a width of $$$m$$$ centimeters and a length of $$$s$$$ centimeters. The wallpaper has a pattern that repeats every $$$k$$$ centimeters along the roll.
The process of wallpapering proceeds as follows. A strip of length $$$h$$$ is cut from the roll, which will be glued to the wall vertically from floor to ceiling. Then the next strip is cut for gluing next to it, and so on. However, it is not that simple! To make it look nice, the pattern on the next strip must align with the pattern on the previous one. To achieve this, it may be necessary to first cut off an extra piece of the roll (which will have to be discarded) before cutting the next strip.
The illustration shows an example. Two strips have been cut from a long roll for gluing. After cutting the first strip, an additional piece had to be cut from the roll (shown crossed out) so that the pattern on the next strip starts exactly the same as on the previous one.
Note that horizontal seams on walls look bad, so the length of the glued strip must always be strictly equal to the height of the room $$$h$$$. If the last glued strip turns out to be wider than the remaining length of the room, it can be cut lengthwise. Also, note that all rolls in the store are absolutely identical.
Determine how many rolls of wallpaper Masha needs to buy to have enough to wallpaper the wall without taking extra rolls.
Five integers are given in five lines: $$$a$$$ — the length of the wall, $$$h$$$ — the height of the wall, $$$k$$$ — the length of the pattern period, $$$m$$$ — the width of the wallpaper roll, $$$s$$$ — the length of the roll.
Constraints: $$$1 \leq a, m, s \leq 2*10^9$$$, $$$1 \leq h \leq s$$$, $$$1 \leq k \leq s$$$.
Output a single integer — the minimum number of rolls of wallpaper required to wallpaper the wall.
Solutions that work correctly under the additional constraint $$$a, m, s \leq 1000$$$ will score at least 50 points.
933320
1
54128
2
Vladimir Borisovich works as a manager in a very large company. One of his duties is the review and approval of requests submitted by employees through a special information system. Vladimir Borisovich approves requests of different types: there are $$$n$$$ types of requests in total. He opened the application for approving requests and saw that there are $$$a_1$$$ requests of the first type, $$$a_2$$$ of the second type, and so on.
The approval process works as follows: requests are marked with checkboxes, and the "Approve" button is pressed. This button only works when all marked requests are of the same type, meaning that it is not possible to approve several requests of different types at the same time. Approved requests disappear from the list of requests. By pressing the checkbox button next to a request, it can be marked or unmarked. There is also a "Mark All" button that marks all requests at once.
What is the minimum number of button presses in the application that Vladimir Borisovich needs to approve all requests?
The first line of input contains the number $$$n$$$ — the number of types of requests ($$$1 \leq n \leq 10^5$$$). The following $$$n$$$ lines each contain one number: $$$a_1, a_2, a_3$$$, and so on — the number of requests received for each type ($$$1 \leq a_i \leq 10^4$$$ for all $$$i$$$).
The program should output a single number — the minimum possible number of button presses required to approve all requests.
Solutions that work correctly under the additional constraint $$$n \leq 1000$$$ will score at least 70 points.
232
5
3111
6
Explanation of the Example
In the first example, the most advantageous approach is to first mark two requests of the second type and press the "Approve" button, which takes a total of three button presses. After that, press the "Mark All" button and then the "Approve" button again, spending two more presses, thus approving all requests using a total of five button presses. It is not difficult to verify that any other method of approval requires more button presses.
All that is required in this task is to find the number of triangles whose side lengths are integers in the range from $$$P$$$ to $$$Q$$$ inclusive.
For example, for $$$P=1$$$, $$$Q=2$$$, the answer will be 3 — these are the triangles with side lengths (1, 1, 1), (1, 2, 2), and (2, 2, 2).
Note: The triplet (1, 2, 2) could also be written as (2, 1, 2) or (2, 2, 1) — they all represent the same triangle.
Two integers $$$P$$$ and $$$Q$$$ are given, each on a separate line ($$$1 \le P \le Q \le 2 \cdot 10^5$$$).
Output a single integer — the required number of triangles.
Solutions that work correctly for $$$Q \le 100$$$ will score at least 30 points.
Solutions that work correctly for $$$Q \le 2000$$$ will score at least 60 points.
12
3
Note that the answer may exceed the possible value of a 32-bit integer variable, so it is necessary to use a 64-bit integer data type (type int64 in Pascal, type long long in C++, type long in Java and C#). In Python, no additional steps are required.
Masha and Gleb decided to move to city M and are considering purchasing land there. There are a total of $$$n$$$ plots of land for sale, located consecutively along the road. The price of each plot is known. Some prices may even be negative — in such cases, the city is willing to pay the buyer just to relieve itself of the responsibilities of maintaining problematic plots.
Masha wants to choose one or several plots that are necessarily consecutive so that they can be merged into one. Gleb wants to do the same. Additionally, Masha and Gleb want to be neighbors — that is, after merging, their combined plots must be adjacent.
Gleb is very lazy, so he asked Masha to select the plots for both of them. Masha, tired of Gleb's laziness, decided to teach him a lesson and choose the plots in such a way that the difference in the total costs of Gleb's plots and Masha's plots is as large as possible. Write a program to find this maximum difference.
The first line contains the number $$$n$$$ $$$(2 \le n \le 10^5)$$$. The next $$$n$$$ lines contain the numbers $$$a_1$$$, $$$a_2$$$, ... $$$a_n$$$ — the prices of the plots ($$$-10^9 \le a_i \le 10^9)$$$.
Output a single integer — the maximum possible difference in the total costs of Gleb's plots and Masha's plots.
Solutions that work correctly for $$$n \le 10$$$ will score at least 15 points. Solutions that work correctly for $$$n \le 200$$$ will score at least 30 points. Solutions that work correctly for $$$n \le 3000$$$ will score at least 60 points.
3123
4
712-36105-100
121
Note that the answer may exceed the possible value of a 32-bit integer variable. Therefore, it is necessary to use a 64-bit integer data type (type int64 in Pascal, type long long in C++, type long in Java and C#). In Python, no additional actions are required.
Compiler Choice. If you are submitting a solution to this problem in Python, do not forget about the option to choose the pypy compiler — using it may significantly speed up your program.
In the middle of the Great Lake lies a remarkable island called Fishland. Dima loves to fish on this island. To ensure a good catch, he set up $$$n$$$ fishing rods on the shore and created a path from the center of the island to each of them. For each fishing rod, the time required to reach it from the center of the island or back is known.
Fishland is a special island, so exactly one of the fishing rods gets a bite every minute. If Dima is at that fishing rod at that moment, he catches a fish; otherwise, the fish swims away.
During one of his fishing trips, Dima collected information on which fishing rod had a bite at each moment in time. He wants to determine the maximum number of fish he could have caught if he had acted optimally. Help Dima determine this.
At the beginning of the fishing trip (at time zero), Dima is at the center of the island. He can only move between the fishing rods via the paths through the center. Catching a fish from the water is instantaneous.
The first line contains one natural number $$$1 \leq t \leq 10^5$$$ — the number of minutes the fishing lasted.
The second line contains one natural number $$$1 \leq n \leq 10^5$$$ — the number of fishing rods set up.
The next $$$t$$$ lines contain one number $$$a_i$$$ ($$$1 \leq a_i \leq n$$$) — the numbers of the fishing rods that had bites at moments in time 1, 2, 3, ..., $$$t$$$.
The last $$$n$$$ lines contain one number $$$d_j$$$ ($$$1 \leq d_j \leq t$$$) — the time in minutes it takes to get from the center of the island to the fishing rods numbered 1, 2, 3, ..., $$$n$$$.
You need to output one number — the maximum number of fish that Dima could have caught.
The grading for the problem is test-based. The problem is checked against all tests. The tests are divided into groups corresponding to the subproblems listed below. For each subproblem, the maximum score that can be obtained for passing all tests corresponding to that subproblem is indicated. Partial scores for a subproblem are possible.
Subproblem 1 (10 points): $$$n=1$$$.
Subproblem 2 (20 points): $$$n=2$$$.
Subproblem 3 (20 points): $$$n, t \leq 100$$$.
Subproblem 4 (20 points): all $$$d_j=1$$$.
Subproblem 5 (30 points): no additional constraints.
221211
1
63332321123
2
Explanation of the example
In the first example, no matter where Dima goes, he can only catch one fish. For instance, in one minute he can reach the first fishing rod just as it gets a bite. But after that, he won't have time to reach another fishing rod, as it gets a bite at time 2, which is just one minute later, while it takes him two minutes to get there.
In the second example, it is beneficial for Dima to go to the second fishing rod right from the start and catch fish while staying there until the end of the fishing.