You are a researcher at Chime Labs, a premier private-sector facility operating under the wing of a major telecommunications giant. The fiscal year is ending, the market is down, and your department is facing massive layoffs. To save your career, you have "discovered" a revolutionary copper wire formulation that supposedly eliminates signal noise.
According to your falsified white paper, a series of electrical signals $$$e_1, e_2, \dots, e_n$$$ is considered "perfectly clean" if it follows a strict alternating pattern. Specifically, the signals must satisfy one of the following two conditions:
- $$$e_1 \lt e_2 \gt e_3 \lt e_4 \gt \dots$$$
- $$$e_1 \gt e_2 \lt e_3 \gt e_4 \lt \dots$$$
The issue is that your actual prototype produces a standard, noisy signal that doesn't follow these rules. To maintain the facade during the live demonstration for the board of directors, you intend to manually calibrate the equipment. You can perform a single type of operation: select any signal $$$i$$$ and decrease the value of $$$e_i$$$ by 1. You can perform this operation as many times as you like on the same $$$i$$$, and you may perform it on any number of different $$$i$$$.
Because the board is watching closely, you want to minimize the total number of operations performed so the adjustments aren't noticed. Find the minimum number of operations required to transform the initial signal into a "perfectly clean" one.
The first line contains a single integer $$$n$$$ $$$(1 \le n \le 2 \cdot 10^5)$$$, representing the number of signals recorded. The second line contains $$$n$$$ space-separated integers $$$e_1, e_2, \dots, e_n$$$ $$$(1 \le e_i \le 10^7)$$$, representing the initial values of the signals.
Print a single integer, the minimum number of operations required to make the signal clean.
58 2 10 10 8
3
You've collected a large number of gift certificates to a certain online store. You now want to redeem them for as much swag as possible. Each certificate has a dollar value, as does every item in the online store. One gift certificate can buy only one item of equal or lesser value from the store: you cannot group purchases together to buy multiple items with one certificate, or one item using multiple certificates of lesser value. Two different certificates can be used to buy (two copies of) the same item. A gift certificate with value less than the cheapest item in the store cannot buy anything.
Given the values of your gift certificates, what is the maximum total value of items you can buy with them from the online store?
The first line of input contains two space-separated integers $$$N$$$ and $$$M$$$, the number of items in the store $$$(1 \leq N \leq 200\,000)$$$ and the number of gift certificates that you own $$$(1 \leq M \leq 200\,000)$$$.
The next line contains $$$N$$$ space-separated integers $$$s_i$$$ $$$(1 \leq s_i \leq 10^9)$$$, the value of the items (in dollars) available for purchase from the store. The item values are listed in non-decreasing order.
The final line contains $$$M$$$ space-separated integers $$$c_i$$$ $$$(1 \leq c_i \leq 10^9)$$$, the value of the gift certificates you own (in dollars).
Print the maximum total value (in dollars) of items you can buy using your gift certificates.
3 420 50 1015 50 51 100
150
1 3100010 500 500
0
5 5240239088 241078714 292474933 407965894 817187660157491604 406414444 462613431 308202469 221739029
992915760
In Sample Input 1, you can buy three copies of the $50 item using your $50, $51, and $100 gift certificate. You cannot buy a fourth copy of the $50 item using the $100 gift certificate since each gift certificate can be used to buy only one item. The $5 gift certificate cannot be used to buy anything.
Hint: there are several ways to solve this problem, but think about the big-$$$O$$$ before implementing. An $$$O(MN)$$$ solution is unlikely to fit in the time limit.
You have just finished shopping for groceries and now need to bag your items. You've brought two reusable shopping bags and must place each item into one of the two bags. Your apartment is quite a few blocks away from the grocery store, and you'd like to make the trek back as painless as possible by balancing the weight of the items in the two bags to be equal, if possible.
Given the weight of each item (in ounces), determine if there's a way to place each item into one of the two bags so that the total weight of each bag is the same.
The first line of input contains a single integer $$$N$$$ $$$(1 \leq N \leq 100)$$$, the number of grocery items you need to bag.
The next line contains $$$N$$$ space-separate integers $$$w_i$$$ $$$(1 \leq w_i \leq 1000)$$$, the weight of your grocery items (in ounces). It is guaranteed that the total weight of all of your items $$$\sum_{i=1}^N w_i$$$ does not exceed $$$1000$$$ ounces.
Print a string: yes if it is possible to place each item into one of the two bags in a way that the total weight of each bag is the same, and no otherwise.
630 100 70 20 1 21
yes
3100 100 100
no
61 2 4 8 16 31
yes
For the items in Sample Input 1, here is one way to bag the items so that both bags have the same total weight ($$$121$$$ ounces):
First Bag: $$$\{100, 20, 1\}$$$
Second Bag: $$$\{70, 30, 21\}$$$.
Magikarp has a large pegboard with $$$n$$$ pegs. The $$$i$$$-th peg is located at position $$$(x_i, y_i)$$$.
He wants to run a rope from peg $$$1$$$ to peg $$$n$$$. To do this, he chooses a sequence of peg indices $$$$$$ 1 = i_1 \lt i_2 \lt \cdots \lt i_m = n, $$$$$$ and connects each consecutive pair of chosen pegs with a straight segment of rope.
However, Magikarp doesn't like to skip too many of his pegs, so no two consecutive indices can differ by more than $$$k$$$. Formally, this sequence must satisfy the condition that for every $$$1 \le t \lt m$$$, $$$$$$ i_{t+1} - i_t \le k. $$$$$$
The total rope length is the sum of the Euclidean distances between consecutive chosen pegs. Find the minimum possible total rope length.
Your answer will be accepted if it has absolute or relative error at most $$$10^{-6}$$$.
The first line contains $$$n$$$ and $$$k$$$ $$$(2\le n\le 2\cdot 10^5, 1\le k\le 20)$$$ — the number of pegs and the maximum difference between consecutive indices.
The $$$i$$$th of the next $$$n$$$ lines contains two integers $$$x_i$$$ and $$$y_i$$$ $$$(-10^9\le x_i,y_i\le 10^9)$$$ — the $$$x$$$ and $$$y$$$ coordinates of the $$$i$$$th peg.
Output a single decimal — the minimum possible total rope length.
5 20 0100 1001 12 03 1
3.4142135624
How to print many decimals:
C++:
cout << fixed << setprecision(10) << x << endl;
Java:
System.out.printf("%.10f%n", x);
Python:
print(f"{x:.10f}")
# or
print(format(x, ".10f"))
While bored in class, your friend doodled an $$$N \times N$$$ grid of binary digits 0 and 1. She then computed the sum of each row and column.
You wonder: knowing these row and column sums, can you construct a grid of binary digits whose rows and columns have those sums? (There might not be a unique answer, so your grid doesn't have to exactly match your friend's original grid.)
The first line of input contains a single integer $$$N$$$ $$$(1 \leq N \leq 8)$$$, the size of the grid you need to construct.
The second line contains $$$N$$$ space-separated integers $$$c_i$$$ $$$(0 \leq c_i \leq N)$$$, the sums of the columns of the grid, in order from left to right.
The last line contains $$$N$$$ space-separated integers $$$r_i$$$ $$$(0 \leq r_i \leq N$$$), the sums of the rows of the grid, in order from top to bottom.
It is guaranteed that the $$$r_i$$$ and $$$c_i$$$ were computed from an $$$N\times N$$$ grid of binary digits.
Print $$$N$$$ lines of exactly $$$N$$$ 0 or 1 characters each: a grid whose row and column sums match the sums in the input. If there are multiple possible such grids, you may print any one of them.
41 0 1 00 1 1 0
0000 0010 1000 0000
100
0
85 3 3 4 3 3 2 34 4 1 3 6 2 4 2
00001111 00001111 00000001 10110000 11111100 10010000 11110000 11000000