# A. Restoring Three Numbers

## Description:

Polycarp has guessed three positive integers $a$, $b$ and $c$. He keeps these numbers in secret, but he writes down four numbers on a board in arbitrary order — their pairwise sums (three numbers) and sum of all three numbers (one number). So, there are four numbers on a board in random order: $a+b$, $a+c$, $b+c$ and $a+b+c$.
You have to guess three numbers $a$, $b$ and $c$ using given numbers. Print three guessed integers in any order.
Pay attention that some given numbers $a$, $b$ and $c$ can be equal (it is also possible that $a=b=c$).

## Input:

The only line of the input contains four positive integers $x_1, x_2, x_3, x_4$ ($2 \le x_i \le 10^9$) — numbers written on a board in random order. It is guaranteed that the answer exists for the given number $x_1, x_2, x_3, x_4$.

## Output

Print such positive integers $a$, $b$ and $c$ that four numbers written on a board are values $a+b$, $a+c$, $b+c$ and $a+b+c$ written in some order. Print $a$, $b$ and $c$ in any order. If there are several answers, you can print any. It is guaranteed that the answer exists.

3 6 5 4

2 1 3

40 40 40 60

20 20 20

201 101 101 200

1 100 100

## AC代码:

#include <bits/stdc++.h>

int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr); std::cout.tie(nullptr);

std::vector<int> arr(4);
for (auto &v : arr) std::cin >> v;
std::sort(arr.begin(), arr.end());

std::cout << arr[3] - arr[0] << ' ' << arr[3] - arr[1] << ' ' << arr[3] - arr[2] << '\n';
return 0;
}

# B. Make Them Equal

## Description:

You are given a sequence $a_1, a_2, \dots, a_n$ consisting of $n$ integers.

You can choose any non-negative integer $D$ (i.e. $D \ge 0$), and for each $a_i$ you can:

• add $D$ (only once), i. e. perform $a_i := a_i + D$, or
• subtract $D$ (only once), i. e. perform $a_i := a_i - D$, or
• leave the value of $a_i$ unchanged.

It is possible that after an operation the value $a_i$ becomes negative.
Your goal is to choose such minimum non-negative integer $D$ and perform changes in such a way, that all $a_i$ are equal (i.e. $a_1=a_2=\dots=a_n$).

Print the required $D$ or, if it is impossible to choose such value $D$, print -1.

For example, for array $[2, 8]$ the value $D=3$ is minimum possible because you can obtain the array $[5, 5]$ if you will add $D$ to $2$ and subtract $D$ from $8$. And for array $[1, 4, 7, 7]$ the value $D=3$ is also minimum possible. You can add it to $1$ and subtract it from $7$ and obtain the array $[4, 4, 4, 4]$.

## Input:

The first line of the input contains one integer $n$ ($1 \le n \le 100$) — the number of elements in $a$.
The second line of the input contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 100$) — the sequence $a$.

## Output

Print one integer — the minimum non-negative integer value $D$ such that if you add this value to some $a_i$, subtract this value from some $a_i$ and leave some $a_i$ without changes, all obtained values become equal.
If it is impossible to choose such value $D$, print -1.

6
1 4 4 7 4 1

3

5
2 2 5 2 5

3

4
1 3 3 7

-1

2
2 8

3

## AC代码:

#include <bits/stdc++.h>

int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr); std::cout.tie(nullptr);

int n; std::cin >> n;
std::vector<int> arr(n);
for (auto &v : arr) std::cin >> v;
std::sort(arr.begin(), arr.end());
arr.erase(unique(arr.begin(), arr.end()), arr.end());

int size = (int)arr.size();
if (size > 3) {
std::cout << -1 << '\n';
return 0;
}
if (size == 3) {
if (abs(arr[2] - arr[1]) == abs(arr[1] - arr[0])) {
std::cout << arr[1] - arr[0] << '\n';
return 0;
}
std::cout << -1 << '\n';
return 0;
}
if (size == 2) {
if ((arr[1] - arr[0]) & 1) {
std::cout << arr[1] - arr[0] << '\n';
return 0;
}
std::cout << (arr[1] - arr[0]) / 2 << '\n';
return 0;
}
if (size == 1) {
std::cout << 0 << '\n';
return 0;
}
return 0;
}

# C. Gourmet Cat

## Description:

Polycarp has a cat and his cat is a real gourmet! Dependent on a day of the week he eats certain type of food:

• on Mondays, Thursdays and Sundays he eats fish food;
• on Tuesdays and Saturdays he eats rabbit stew;
• on other days of week he eats chicken stake.

Polycarp plans to go on a trip and already packed his backpack. His backpack contains:

• $a$ daily rations of fish food;
• $b$ daily rations of rabbit stew;
• $c$ daily rations of chicken stakes.

Polycarp has to choose such day of the week to start his trip that his cat can eat without additional food purchases as long as possible. Print the maximum number of days the cat can eat in a trip without additional food purchases, if Polycarp chooses the day of the week to start his trip optimally.

## Input:

The first line of the input contains three positive integers $a$, $b$ and $c$ ($1 \le a, b, c \le 7\cdot10^8$) — the number of daily rations of fish food, rabbit stew and chicken stakes in Polycarps backpack correspondingly.

## Output

Print the maximum number of days the cat can eat in a trip without additional food purchases, if Polycarp chooses the day of the week to start his trip optimally.

2 1 1

4

3 2 2

7

1 100 1

3

30 20 10

39

## AC代码:

#include <bits/stdc++.h>

std::vector<int> arr, buf;
std::vector<int> d = {-1, 0, 1, 2, 0, 2, 1, 0};

int Calc(int s) {
int ret = 0;
for (int i = s; i <= 7; ++i) {
if (buf[d[i]]) --buf[d[i]];
else return ret;
++ret;
}
int cir = std::min(buf[0] / 3, std::min(buf[1] / 2, buf[2] / 2));
buf[0] -= cir * 3; buf[1] -= cir * 2; buf[2] -= cir * 2;
ret += 7 * cir;
for (int i = 1; i <= 7; ++i) {
if (buf[d[i]]) --buf[d[i]];
else return ret;
++ret;
}
}

int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr); std::cout.tie(nullptr);

arr.assign(3, 0);
for (auto &v : arr) std::cin >> v;

int ans = 0;
for (int i = 1; i <= 7; ++i) {
buf = arr;
ans = std::max(ans, Calc(i));
}

std::cout << ans << '\n';
return 0;
}

# D. Walking Robot

## Description:

There is a robot staying at $X=0$ on the $Ox$ axis. He has to walk to $X=n$. You are controlling this robot and controlling how he goes. The robot has a battery and an accumulator with a solar panel.
The $i$-th segment of the path (from $X=i-1$ to $X=i$) can be exposed to sunlight or not. The array $s$ denotes which segments are exposed to sunlight: if segment $i$ is exposed, then $s_i = 1$, otherwise $s_i = 0$.
The robot has one battery of capacity $b$ and one accumulator of capacity $a$. For each segment, you should choose which type of energy storage robot will use to go to the next point (it can be either battery or accumulator). If the robot goes using the battery, the current charge of the battery is decreased by one (the robot can't use the battery if its charge is zero). And if the robot goes using the accumulator, the current charge of the accumulator is decreased by one (and the robot also can't use the accumulator if its charge is zero).
If the current segment is exposed to sunlight and the robot goes through it using the battery, the charge of the accumulator increases by one (of course, its charge can't become higher than it's maximum capacity).
If accumulator is used to pass some segment, its charge decreases by 1 no matter if the segment is exposed or not.
You understand that it is not always possible to walk to $X=n$. You want your robot to go as far as possible. Find the maximum number of segments of distance the robot can pass if you control him optimally.

## Input:

The first line of the input contains three integers $n, b, a$ ($1 \le n, b, a \le 2 \cdot 10^5$) — the robot's destination point, the battery capacity and the accumulator capacity, respectively.
The second line of the input contains $n$ integers $s_1, s_2, \dots, s_n$ ($0 \le s_i \le 1$), where $s_i$ is $1$ if the $i$-th segment of distance is exposed to sunlight, and $0$ otherwise.

## Output

Print one integer — the maximum number of segments the robot can pass if you control him optimally.

5 2 1
0 1 0 1 0

5

6 2 1
1 0 0 1 0 1

3

## AC代码:

#include <bits/stdc++.h>

int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr); std::cout.tie(nullptr);

int n, init_b, init_a; std::cin >> n >> init_b >> init_a;
int a = init_a, b = init_b;
std::vector<int> s(n);
for (auto &v : s) std::cin >> v;

for (int i = 0; i < n; ++i) {
if (b == 0 && a == 0) {
std::cout << i << '\n';
return 0;
}
if (s[i] == 0) {
if (a) --a;
else --b;
}
else {
if (b) {
if (a < init_a) {
--b;
++a;
else --a;
}
else --a;
}
}
std::cout << n << '\n';
return 0;
}

# E. Two Teams

## Description:

There are $n$ students standing in a row. Two coaches are forming two teams — the first coach chooses the first team and the second coach chooses the second team.
The $i$-th student has integer programming skill $a_i$. All programming skills are distinct and between $1$ and $n$, inclusive.
Firstly, the first coach will choose the student with maximum programming skill among all students not taken into any team, and $k$ closest students to the left of him and $k$ closest students to the right of him (if there are less than $k$ students to the left or to the right, all of them will be chosen). All students that are chosen leave the row and join the first team. Secondly, the second coach will make the same move (but all students chosen by him join the second team). Then again the first coach will make such move, and so on. This repeats until the row becomes empty (i. e. the process ends when each student becomes to some team).
Your problem is to determine which students will be taken into the first team and which students will be taken into the second team.

## Input:

The first line of the input contains two integers $n$ and $k$ ($1 \le k \le n \le 2 \cdot 10^5$) — the number of students and the value determining the range of chosen students during each move, respectively.
The second line of the input contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$), where $a_i$ is the programming skill of the $i$-th student. It is guaranteed that all programming skills are distinct.

## Output

Print a string of $n$ characters; $i$-th character should be 1 if $i$-th student joins the first team, or 2 otherwise.

5 2
2 4 5 3 1

11111

5 1
2 1 3 5 4

22111

7 1
7 2 1 3 5 4 6

1121122

5 1
2 4 5 3 1

21112

## AC代码:

#include <bits/stdc++.h>

int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr); std::cout.tie(nullptr);

int n, k; std::cin >> n >> k;
std::vector<int> arr(n + 1);
std::vector<int> l(n + 2), r(n + 2);
std::map<int, int> pos, rev;
for (int i = 1; i <= n; ++i) {
std::cin >> arr[i];
pos[arr[i]] = i;
l[i] = i - 1; r[i] = i + 1;
}

int max = n, cur = 1;
std::vector<int> ans(n + 1, 0);
std::vector<bool> vis(n + 1, false);
while (max) {
int m = pos[max];
for (int t = 0; m && t <= k; ++t, m = l[m]) {
vis[arr[m]] = true;
ans[m] = cur;
}
int l_lim = m;
m = pos[max];
for (int t = 0; m <= n && t <= k; ++t, m = r[m]) {
vis[arr[m]] = true;
ans[m] = cur;
}
int r_lim = m;
r[l_lim] = r_lim; l[r_lim] = l_lim;
while (max >= 0 && vis[max]) --max;
cur = cur == 1 ? 2 : 1;
}

for (int i = 1; i <= n; ++i) std::cout << ans[i];
std::cout << '\n';
return 0;
}

# F. Shovels Shop

## Description:

There are $n$ shovels in the nearby shop. The $i$-th shovel costs $a_i$ bourles.
Misha has to buy exactly $k$ shovels. Each shovel can be bought no more than once.
Misha can buy shovels by several purchases. During one purchase he can choose any subset of remaining (non-bought) shovels and buy this subset.
There are also $m$ special offers in the shop. The $j$-th of them is given as a pair $(x_j, y_j)$, and it means that if Misha buys exactly $x_j$ shovels during one purchase then $y_j$ most cheapest of them are for free (i.e. he will not pay for $y_j$ most cheapest shovels during the current purchase).
Misha can use any offer any (possibly, zero) number of times, but he cannot use more than one offer during one purchase (but he can buy shovels without using any offers).
Your task is to calculate the minimum cost of buying $k$ shovels, if Misha buys them optimally.

## Input:

The first line of the input contains three integers $n, m$ and $k$ ($1 \le n, m \le 2 \cdot 10^5, 1 \le k \le min(n, 2000)$) — the number of shovels in the shop, the number of special offers and the number of shovels Misha has to buy, correspondingly.
The second line of the input contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 2 \cdot 10^5$), where $a_i$ is the cost of the $i$-th shovel.
The next $m$ lines contain special offers. The $j$-th of them is given as a pair of integers $(x_i, y_i)$ ($1 \le y_i \le x_i \le n$) and means that if Misha buys exactly $x_i$ shovels during some purchase, then he can take $y_i$ most cheapest of them for free.

## Output

Print one integer — the minimum cost of buying $k$ shovels if Misha buys them optimally.

7 4 5
2 5 4 2 6 3 1
2 1
6 5
2 1
3 1

7

## Sample Input:

9 4 8
6 8 5 1 8 1 1 2 1
9 2
8 4
5 3
9 7

17

5 1 4
2 5 7 4 6
5 4

## Sample Output:

17

### 题目链接

$n$ 个商品，$m$ 个优惠：每满 $a$ 件商品其中花费最少的 $b$ 个就会免费，求最少花费

## AC代码:

#include <bits/stdc++.h>

int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr); std::cout.tie(nullptr);

int n, m, k; std::cin >> n >> m >> k;
std::vector<int> arr(n + 1, 0), pref(n + 1, 0);
for (int i = 1; i <= n; ++i) std::cin >> arr[i];
std::sort(arr.begin(), arr.end());
for (int i = 1; i <= n; ++i) pref[i] = pref[i - 1] + arr[i];
std::map<int, int> mp;
for (int i = 1, a, b; i <= m; ++i) {
std::cin >> a >> b;
if (a <= k) mp[a] = std::max(mp[a], b);
}

std::vector<int> dp(k + 1);
for (int i = 1; i <= k; ++i) {
dp[i] = pref[i];
for (int j = 0; j < i; ++j) {
dp[i] = std::min(dp[i], dp[j] + pref[i] - pref[j + mp[i - j]]);
}
}

std::cout << dp[k] << '\n';
return 0;
}
Last modification：April 22nd, 2019 at 02:07 pm