# Динамика ЕГЭ
*задачи 1-67 с сайта [Полякова](https://kpolyakov.spb.ru/school/ege.htm)*
## Часть 1. Основанные на большой таблице
Т.е. Задачи, основанные на хранении максимальных/минимальных сумм чисел с фиксированными остатками от делания на число n.
### Примером такой задачи является задача №1:
#### Условие:
Имеется набор данных, состоящий из пар положительных целых чисел. Необходимо выбрать из каждой пары ровно одно число так, чтобы сумма всех выбранных чисел не делилась на 3 и при этом была минимально возможной. Гарантируется, что искомую сумму получить можно. Программа должна напечатать одно число – минимально возможную сумму, соответствующую условиям задачи.
##### Входные данные:
Даны два входных файла: файл A (27-1a.txt) и файл B (27-1b.txt), каждый из которых содержит в первой строке количество пар N (1 ≤ N ≤ 100000). Каждая из следующих N строк содержит два натуральных числа, не превышающих 10 000.
##### Пример входного файла:
6
1 3
5 12
6 9
5 4
3 3
1 1
Для указанных входных данных значением искомой суммы должно быть число 20.
В ответе укажите два числа: сначала значение искомой суммы для файла А, затем для файла B.
#### Решение
Чтобы решить эту задачу мы составляли таблицу, в которой хранятся все минимально возможные суммы, которые можно получить, выбирая одно число из пары.
##### Пример такой таблицы
| Ввод | 0 | 1 | 2 |
| -------- | -------- | -------- | --- |
| 1 3 |3 |1| -1|
5 12 | 6,~~15~~ | 13| 8
6 9| 12, ~~15~~ |19, ~~22~~| 14, ~~17~~
5 4[^1] | ~~24~~, 18 |~~19~~, 16| 17, ~~23~~
3 3| 21| 19 |20
1 1 |21| 22| 20
[^1]: второй ряд является примером, когда выгоднее увеличить сумму на бОльшее из чисел (остаток 2)
При составлении таблицы мы, опираясь на предыдущий ряд, к каждой непустой ячейке прибавляли новое прочитанное число, брали остаток от деления на 3 у этого числа и обновляли соответствующее значение в ячейке таблицы (выбирая минимальное, если в этой ячейке уже что-то есть)
##### Пример кода
```cpp=
#include <fstream>
#include <iostream>
#include <string>
using namespace std;
int main() {
fstream file;
file.open("./27data/1/27-1b.txt", ios::in);
// file.open("./test.txt", ios::in);
string line;
getline(file, line);
int N = stoi(line);
int diff[3];
int diff_past[3];
// fill the arrays
for (int i = 0; i < 3; i++) {
diff_past[i] = -1;
diff[i] = -1;
}
// main loop
int values[2]; // array with vales from next line
for (int line_index = 0; line_index < N; line_index++) {
getline(file, line, ' ');
values[0] = stoi(line);
getline(file, line);
values[1] = stoi(line);
// special case - the first row
if (line_index == 0) {
diff_past[values[0] % 3] = values[0];
diff_past[values[1] % 3] = values[1];
continue;
}
// for all out of 2 values
for (int v_index = 0; v_index < 2; v_index++) {
int value = values[v_index];
for (int i = 0; i < 3; i++) {
if (diff_past[i] == -1) {
continue;
}
int new_value = value + diff_past[i];
// index to be updated
int new_index = new_value % 3;
// old value within a cell
int old_value = diff[new_index];
if (old_value == -1 || old_value > new_value) {
diff[new_index] = new_value;
}
}
}
// copy diff to diff_past:
for (int i = 0; i < 3; i++) {
diff_past[i] = diff[i];
diff[i] = -1;
}
}
file.close();
// find min out of the cell 1 and 2;
int min_sum = diff_past[1] < diff_past[2] ? diff_past[1] : diff_past[2];
cout << min_sum << endl;
return 0;
}
```
#### Альтернативное решение:
- Найти минимальную сумму и хранить минимальную разность элементов, не кратную трём
##### Пример кода:
```cpp=
#include <fstream>
#include <iostream>
#include <math.h>
#include <string>
using namespace std;
int main() {
fstream file;
file.open("./27data/1/27-1b.txt", ios::in);
// file.open("./test.txt", ios::in);
string line;
getline(file, line);
int N = stoi(line);
int min_sum = 0; // max possible current sum
int min_diff = 100000; // min difference between numbers in paris, which %3!=0
for (int i = 0; i < N; i++) {
getline(file, line, ' ');
int a = stoi(line);
getline(file, line);
int b = stoi(line);
min_sum += a < b ? a : b;
int diff = abs(a - b);
if (diff < min_diff && diff % 3 != 0) {
min_diff = diff;
}
}
file.close();
if (min_sum % 3 != 0) {
cout << min_sum << endl;
} else {
cout << min_sum + min_diff << endl;
}
return 0;
}
```
### Какие подтипы этой задачи существуют
#### Задачи 1-5 - накопительная сумма
#### Задачи 10-11, 30, 32
особенность задач - нужно выбрать одно число из **тройки**
#### 14-15 - ещё проще:
нужно подсчитать, сколько есть в ведёной последовательности чисел с определённым остатком от деления
Для входных данных
7
5
6
12
24
Получим таблицу (`arr`)
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
| ---- | --- | --- | --- | --- | --- | --- | --- | --- | ---- | --- | -------- |
| 2 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 0 |0| 0 |
Получим кол-во результатов следующим образом:
```cpp=
int res = arr[0] + int(arr[6]/2);
for(int i=1; i< 6; i++){
res += arr[i]*arr[12-i];
}
```
#### 21-28 + 32 - сумма заканчивается на...
#### 29, 31 + 33-34
Тут тоже тройки, но условие немного интереснее (задача 29):
##### Условие
Имеется набор данных, состоящий из троек положительных целых чисел. Необходимо выбрать из каждой тройки два числа так, чтобы сумма всех выбранных чисел не делилась на 5 и при этом была максимально возможной. Гарантируется, что искомую сумму получить можно. Программа должна напечатать одно число – максимально возможную сумму, соответствующую условиям задачи.
##### Входные данные:
Даны два входных файла: файл A (27-29a.txt) и файл B (27-29b.txt), каждый из которых содержит в первой строке количество троек N (1 ≤ N ≤ 100000). Каждая из следующих N строк содержит три натуральных числа, не превышающих 10 000.
##### Пример входного файла:
6
8 3 4
4 8 12
9 5 6
2 8 3
12 3 5
1 4 11
Для указанных входных данных значением искомой суммы должно быть число 89.
В ответе укажите два числа: сначала значение искомой суммы для файла А, затем для файла B.
##### Решение:
- нам нужна максимальная сумма, поэтому можно найти сумму всех-всех-всех элементов и вычесть из неё минимальную сумму, состоящую из одного из элементов тройки с шужным остатком
- т.е. решаем задачу - нацти минимальную сумму, которую можно получать, выбирая один из элементов тройки, но в ответе пишем разность общей суммы (для примера эта сумма = 108) и минимальной суммы с некоторомы остатком от деления на 5 (любой, кроме 3 в нашем случае)
- если не понятно, могу написать
#### 36
- Вместо самих чисел нужно использовать из три НОД-а, а так - как в 10, допустим. Советую вспомнить алгоритм Евклида
#### 46-47
*Дана последовательность, которая состоит из пар натуральных чисел. Необходимо выбрать из каждой пары ровно одно число так, чтобы сумма всех выбранных чисел имела такой же остаток от деления на 7, как наименьшая возможная, и при этом была максимальной возможной.*
Т.е. нужно сочитать минимальную и максимальную возможную сумму под остаток от деления на 7.
#### 48-51
##### Условие (48)
Набор данных состоит из нечётного количества пар натуральных чисел. Необходимо выбрать из каждой пары ровно одно число так, чтобы сумма выбранных чисел была максимальной при условии, что чётность этой суммы совпадает с чётностью большинства выбранных чисел. Определите максимальную сумму, которую можно получить при таком условии. Гарантируется, что удовлетворяющий условиям выбор возможен.
##### Входные данные:
Даны два входных файла: файл A (27-48a.txt) и файл B (27-48b.txt), каждый из которых содержит в первой строке количество чисел N (1 ≤ N ≤ 100000). Каждая из следующих N строк содержит два натуральных числа, не превышающих 10000.
##### Пример входного файла:
5
13 8
5 11
6 9
7 2
9 14
Для указанных данных надо выбрать числа 13, 11, 6, 7 и 14. Большинство из них нечётны, их сумма 51 тоже нечётна. В ответе укажите два числа: сначала искомое значение для файла А, затем для файла B.
##### Решение
- находим максимальную сумму и количество её чётных и нечётных составляющих
- если разность количеств чётных и нечётных велика (>1), и максимальная сумма нас ещё не удовлетворяет, то уменьшаем сумму на минимальную нечётную разность (чётность суммы меняется, а количества чётных-нечётных соотносятся примерно так же)
- если разность 1, то есть два сценария
1. `2н+1ч = ч`
* меняем `2н` на `2ч`
* меняем `ч` на `н`
2. `2ч+1н = н`
* меняем `2ч` на `2н`
* меняем `н` на `ч`
- выбираем наименьший из подпунктов
Итог:
- нужно хранить 4 минимальных нечётных разности:
- 2 из чётного в нечётное
- 2 из нечётного в чётное
##### Код
```cpp=
#include <fstream>
#include <iostream>
#include <string>
using namespace std;
int main() {
fstream file;
file.open("./27data/48/27-48b.txt", ios::in);
string line;
getline(file, line);
int N = stoi(line);
int odd_diffs[2][2]; // [from]: {min_1, min_2}
int max_sum = 0;
int n_odd = 0;
for (int line_index = 0; line_index < N; line_index++) {
getline(file, line, ' ');
int v1 = stoi(line);
getline(file, line);
int v2 = stoi(line);
int max_v = v1 > v2 ? v1 : v2;
int min_v = v1 < v2 ? v1 : v2;
max_sum += max_v;
if (max_v % 2) {
n_odd++;
}
if ((max_v - min_v) % 2 == 1) {
int d = max_v - min_v;
int min1 = odd_diffs[max_v % 2][0];
int min2 = odd_diffs[max_v % 2][1];
if (min1 == -1 || d < min1) {
odd_diffs[max_v % 2][0] = d;
} else if (min2 == -1 || d < min2) {
odd_diffs[max_v % 2][1] = d;
}
}
}
file.close();
int n_even = N - n_odd;
int d1, d2;
if ((max_sum % 2) != (n_odd > n_even)) {
// if need modification
// complex_case:
// 1. -2 of the most common
// 2. -1 of the least common
if ((n_odd - n_even == 1)) {
d1 = odd_diffs[1][0] + odd_diffs[1][1];
d2 = odd_diffs[0][0];
} else if ((n_odd - n_even == -1)) {
d1 = odd_diffs[0][0] + odd_diffs[0][1];
d2 = odd_diffs[1][0];
} else {
d1 = odd_diffs[0][0];
d2 = odd_diffs[1][0];
}
int min_d = d1 < d2 ? d1 : d2;
max_sum -= min_d;
}
cout << max_sum << endl;
return 0;
}
```
#### 58-59 - считаем количество
Пример таблицы для задачи 58:
#### 60, 61 - классика
#### 66
##### Условие:
Набор данных состоит из пар натуральных чисел. Необходимо выбрать из каждой пары одно число так, чтобы сумма выбранных чисел была максимально возможной и не делилась на 5, при этом сумма невыбранных чисел не делилась на 3. Какую наибольшую сумму выбранных чисел можно при этом получить?
##### Входные данные:
Даны два входных файла: файл A (27-66a.txt) и файл B (27-66b.txt), каждый из которых содержит в первой строке количество чисел N (N ≤ 12000). Каждая из следующих N строк файлов содержит два натуральных числа, не превышающих 500.
##### Пример входного файла:
5
13 18
18 10
15 8
19 11
7 15
Для указанных входных данных значением искомой суммы должно быть число 18+18+8+19+15=78 (сумма остальных элементов 13+10+15+11+7=56). В ответе укажите два числа: сначала искомое значение для файла А, затем для файла B.
##### Решение
1. Хочется по-старинке найти максимальную сумму, и, если не устраивает её сдвинуть, но нас интересует не тольно остаток от деления на 5, но и остаток от деления на 5 совместно с остатком от деления на 3. В этом случае "цикл" повторится через $15=НОК(5, 3)$.
2. Таким образом, мы заполняем обычную таблицу из 15 элементов и ищем подходящее решение нашей проблемы
##### Код:
```cpp=
#include <algorithm>
#include <fstream>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int main() {
fstream file;
file.open("./27data/66/27-66.txt", ios::in);
string line;
getline(file, line);
int N = stoi(line);
int arr_old[15];
int arr[15];
for (int i = 0; i < 15; i++) {
arr[i] = -1;
arr_old[i] = -1;
}
int total_sum = 0;
int max_sum = 0;
for (int index = 0; index < N; index++) {
getline(file, line, ' ');
int v1 = stoi(line);
getline(file, line);
int v2 = stoi(line);
// swap
if (v1 > v2) {
int t = v1;
v1 = v2;
v2 = t;
}
max_sum += v2;
total_sum += v2 + v1;
int d = v2 - v1;
// copy
for (int i = 0; i < 15; i++) {
arr[i] = arr_old[i];
}
// update
for (int i = 0; i < 15; i++) {
if (arr_old[i] == -1) {
continue;
}
int new_val = arr_old[i] + d;
int past_val = arr[new_val % 15];
if (past_val == -1 || past_val > new_val) {
arr[new_val % 15] = new_val;
}
}
// the vatiavle itself
if (arr[d % 15] == -1 || arr[d % 15] > d) {
arr[d % 15] = d;
}
// copy back
for (int i = 0; i < 15; i++) {
arr_old[i] = arr[i];
}
}
file.close();
arr[0] = 0;
int sum1 = max_sum;
int sum2 = total_sum - max_sum;
if (sum1 % 5 != 0 && (sum2) % 3 != 0) {
cout << max_sum << endl;
return 0;
}
vector<int> ans;
for (int i = 0; i < 15; i++) {
if (arr[i] == -1) {
continue;
}
int s1 = sum1 - arr[i];
int s2 = sum2 + arr[i];
if (s1 % 5 != 0 && s2 % 3 != 0) {
ans.push_back(s1);
}
}
sort(ans.begin(), ans.end());
cout << max_sum << " " << total_sum << endl;
cout << ans[ans.size() - 1] << endl;
}
```
#### 67 - сложная читка
Читка в этой задаче, пожалуй, является единственной сложностью
## Часть 2. Другие типы задач
### Задачи 6-7
##### Условие (6)
Имеется набор данных, состоящий из положительных целых чисел, каждое из которых не превышает 1000. Требуется найти для этой последовательности контрольное значение – наибольшее число R, удовлетворяющее следующим условиям:
– R – произведение двух различных переданных элементов последовательности («различные» означает, что не рассматриваются квадраты переданных чисел, произведения различных, но равных по величине элементов допускаются);
– R делится на 6.
##### Входные данные:
Даны два входных файла: файл A (27-6a.txt) и файл B (27-6b.txt), каждый из которых содержит в первой строке количество чисел N (1 ≤ N ≤ 100000). Каждая из следующих N строк содержит одно натуральное число, не превышающее 1000.
##### Пример входного файла:
6
60
17
3
7
9
60
Для указанных данных искомое контрольное значение равно 3600.
В ответе укажите два числа: сначала контрольное значение для файла А, затем для файла B.
##### Решение
Список множителей шестёрки: 1, 2, 3, 6
Нам нужно найти максимальное значение R.
Список искомых переменных:
- (`n6_1` и `n6_2`)два максимальных числа кратных 6
- (`n3`) максимальное число, кратное 3, но не кратное 2
- (`n2`) максимальное число, кратное 2, но не кратное 3
- (`n1`) максимальное число, не кратное 6, 2 или 3
Ответ вычисляется по формуле
`max(n6_1*max(n6_2, n3, n2, n1), n2*n3)`
##### Пример кода
```cpp=
#include <fstream>
#include <iostream>
#include <string>
using namespace std;
int max(int a, int b, int c, int d) {
int res = a;
res = res > b ? res : b;
res = res > c ? res : c;
res = res > d ? res : d;
return res;
}
int main() {
string line;
fstream file;
file.open("./27data/6/27-6a.txt", ios::in);
//file.open("test.txt", ios::in);
getline(file, line);
int N = stoi(line);
int max6_1 = 0;
int max6_2 = 0;
int max3 = 0;
int max2 = 0;
int max_n = 0;
for (int i = 0; i < N; i++) {
getline(file, line);
int x = stoi(line);
if (x % 6 == 0) {
if (x > max6_1) {
max6_1 = x;
} else if (x > max6_2) {
max6_2 = x;
}
} else if (x % 3 == 0 && x > max3) {
max3 = x;
} else if (x % 2 == 0 && x > max2) {
max2 = x;
} else if (x % 2 != 0 && x % 3 != 0 && x > max_n) {
max_n = x;
}
}
file.close();
int n23 = max3 * max2;
int n6n = max(max6_2, max2, max3, max_n) * max6_1;
int res = n6n > n23 ? n6n : n23;
cout << res << endl;
return 0;
}
```
#### Примечание к задаче 7
##### Условие
Имеется набор данных, состоящий из положительных целых чисел, каждое из которых не превышает 1000. Требуется найти для этой последовательности контрольное значение – наибольшее число R, удовлетворяющее следующим условиям:
– R – произведение двух различных переданных элементов последовательности («различные» означает, что не рассматриваются квадраты переданных чисел, произведения различных, но равных по величине элементов допускаются);
– R делится на 7 и не делится на 49.
Если такое произведение получить невозможно, считается, что контрольное значение R = 1.
###### Входные данные:
Даны два входных файла: файл A (27-7a.txt) и файл B (27-7b.txt), каждый из которых содержит в первой строке количество чисел N (1 ≤ N ≤ 100000). Каждая из следующих N строк содержит одно натуральное число, не превышающее 1000.
##### Пример входного файла:
6
60
17
3
7
9
60
Для указанных данных искомое контрольное значение равно 420.
В ответе укажите два числа: сначала контрольное значение для файла А, затем для файла B.
##### Описание решения
- храним максимум, кратный 7, но не кратный 49
- хнаним максимум не кратный 7
- умножаем их
### Задачи 8-9 - колонка текущих минимумов
##### Условие
Имеется набор данных, состоящий из положительных целых чисел, каждое из которых не превышает 1000. Они представляют собой результаты измерений, выполняемых прибором с интервалом 1 минута. Требуется найти для этой последовательности контрольное значение – наименьшую сумму квадратов двух результатов измерений, выполненных с интервалом не менее, чем в 5 минут.
##### Входные данные:
Даны два входных файла: файл A (27-8a.txt) и файл B (27-8b.txt), каждый из которых содержит в первой строке количество чисел N (5 ≤ N ≤ 100000). Каждая из следующих N строк содержит одно натуральное число, не превышающее 1000.
##### Пример входного файла:
9
12
45
5
4
21
20
10
12
26
Для указанных данных искомое контрольное значение равно 169.
В ответе укажите два числа: сначала контрольное значение для файла А, затем для файла B.
##### Решение:
| ввод(`input`) | текущий минимум (`arr`) |
|:------------- |:----------------------- |
| 12 | 12 |
| 45 | 12 |
| 5 | 5 |
| 4 | 4 |
| 21 | 4 |
| 20 | 4 |
| 10 | 4 |
| 12 | 4 |
| 26 | 4 |
код после заполнения массива:
```cpp=
int result = -1;
for(int i = 5; i < N; i++) {
int new_value = input[i]*input[i] + arr[i-5]*arr[i-5];
if(result == -1 || result < new_value) {
result = new_value;
}
}
```
#### Комменттарии к задаче 9
Что меняется в условии:
- нужно найти минимальное нечётное произведение двух показаний сделанных с разностью хотя бы 6 минут
- Следовательно, в массиве храним минимальное нечётное число (произведение нечётно, если оба множителя нечётны)
Пример заполнения таблицы
| ввод(`input`) | текущий нечётный минимум (`arr`) |
|:------------- |:-------------------------------- |
| 12 | -1 |
| 45 | 45 |
| 5 | 5 |
| 4 | 5 |
| 21 | 5 |
| 20 | 5 |
| 19 | 5 |
| 12 | 5 |
| 26 | 5 |
19*5=95 - ответ
Пример кода после заполнения таблицы
```cpp=
int result = -1;
for(int i = 6; i < N; i++) {
// нас интересуют только нечётные
if(intput[i] % 2 == 0) {
continue;
}
int new_value = input[i]*arr[i-6];
if(result == -1 || result < new_value) {
result = new_value;
}
}
```
### Задачи 12-13
- аналогично задачам 6-7, но нужно обновлять переменную с результатом прямо в основном цикле (т.к. важен порядок)
- для задачи 13 нужно держать в пямяти последние 7 проичтанных элементов и побновлять массив по прошлым
### 16-17
##### Условие
Имеется набор данных, состоящий из положительных целых чисел. Необходимо определить количество пар элементов (ai, aj) этого набора, в которых 1 ≤ i < j ≤ N и сумма элементов нечётна, а произведение делится на 13.
##### Входные данные:
Даны два входных файла: файл A (27-16a.txt) и файл B (27-16b.txt), каждый из которых содержит в первой строке количество чисел N (1 ≤ N ≤ 100000). Каждая из следующих N строк содержит натуральное число, не превышающее 1000.
##### Пример входного файла:
5
4
13
27
39
7
Для указанных входных данных количество подходящих пар должно быть равно 2. В приведённом наборе имеются две пары (4, 13) и (4, 39), сумма элементов которых нечётна, и произведение кратно 13.
В ответе укажите два числа: сначала количество подходящих пар для файла А, затем для файла B.
##### Решение
- переменные:
- `n_13_odd`
- `n_13_even`
- `n_not_13_even`
- `n_not_13_odd`
- `result = n_13_odd*(n_13_even + n_not_13_even) + n_13_even*(n_13_odd+n_not_13_odd)`
### 18 - задача с подвохом
Имеется набор данных, состоящий из положительных целых чисел. Необходимо определить количество пар элементов (ai, aj) этого набора, в которых 1 ≤ i < j ≤ N, сумма элементов нечётна, произведение делится на 13, а номера элементов в последовательности отличаются **МЕНЕЕ**, чем на 5.
##### Входные данные:
Даны два входных файла: файл A (27-18a.txt) и файл B (27-18b.txt), каждый из которых содержит в первой строке количество чисел N (1 ≤ N ≤ 100000). Каждая из следующих N строк содержит натуральное число, не превышающее 1000.
##### Пример входного файла:
7
4
14
27
33
7
2
13
Для указанных входных данных количество подходящих пар должно быть равно 1. В приведённом наборе имеются одна пара (2, 13), сумма элементов которой нечётна, произведение кратно 13 и индексы элементов последовательности отличаются менее, чем на 5.
В ответе укажите два числа: сначала количество подходящих пар для файла А, затем для файла B.
##### Решение:
Хочется перебрать просто все пятёрки, в них найти количество кратных/ некратных двум и 13, потом найти итоговое количество. Внутри пяти элементов найти такое количество - O(5) ( в крайнем случае O(25)), т.е константная сложность. Этот алгоритм надо повторить для всех последовательных пятёрок. Получаем сложнось `O(n*5)=O(n)`, т.е. даже достаточно простой перебор будет линеен.
Возможные ускорения - не обнулять переменные для каждой пятёрки, а обновлять их "назад", в зависимости от -6-ого занчения и "вперёд" - в зависимости от нулевого.
Если непонятно, то могу написать код.
### 19 (умеренно сложная)
##### Условие
Имеется набор данных, состоящий из целых чисел. Необходимо определить максимальное произведение подпоследовательности, состоящей из одного или более смежных элементов.
##### Входные данные:
Даны два входных файла: файл A (27-19a.txt) и файл B (27-19b.txt), каждый из которых содержит в первой строке количество чисел N (1 ≤ N ≤ 100000). Каждая из следующих N строк содержит натуральное число, не превышающее по модулю 100.
##### Пример входного файла:
7
2
3
-2
-3
-1
4
6
Для указанных входных данных наибольшее произведение равно 72. Его можно получить для последовательности -3 -1 4 6.
##### Решение
- разделить на блоки, ограниченные нулями
- в каждом блоке найти три произведения:
- (0) влоное произведение элементов
- (1) произведение от первого отрицательного, до конца части
- (2) произведение от самого начала части до её последнего отрицательного элемента (см.рисунок)
Так для блока `1 -2 4 -1 4 -2 7` произведение (1) равно `4 * -1 * 4 * -2 * 7`, а произведение (2) равно `1 * -2 * 4 * -1 * 4`.
##### Код
```cpp=
/**
* IMPORTANT: FILES COULD CONTAIN 0's
* for each block around 0 => track vars: begin_i and end_i;
* track index of first negative and last negative (if there are)
* track total product
* output max of 3 numbers
*
* */
#include <fstream>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
long product_in_rage(int i_start, int i_end, int *arr) {
int prod = 1;
for (int i = i_start; i < i_end; i++) {
prod *= arr[i];
}
return prod;
}
long max_prod_between0(int i_start, int i_end, int *arr) {
int index_first_negative = 0; // index of the first negative number
bool was_negative = false; // if there was a negative number before
int index_last_negative = 0; // index of the last negative number
long total_mult = 1; // total product of all numbers
// main loop
for (int i = i_start; i < i_end; i++) {
if (!was_negative && arr[i] < 0) {
index_first_negative = i;
was_negative = true;
}
if (arr[i] < 0) {
index_last_negative = i;
}
total_mult *= arr[i];
}
// if ok
if (total_mult > 0) {
return total_mult;
}
// find prduct before the first and after the last negative number
long prod_before_first = product_in_rage(i_start, index_first_negative + 1, arr);
long prod_after_last = product_in_rage(index_last_negative, i_end, arr);
// find the best among actual products
long prod1 = total_mult / prod_before_first;
long prod2 = total_mult / prod_after_last;
long best = prod1 > prod2 ? prod1 : prod2;
return best;
}
int main() {
fstream file;
file.open("./27data/19/27-19b.txt", ios::in);
string line;
getline(file, line);
int N = stoi(line);
int arr[N];
// main loop
vector<int> zeros;
zeros.push_back(-1);
for (int i = 0; i < N; i++) {
getline(file, line);
arr[i] = stoi(line);
if (arr[i] == 0) {
zeros.push_back(i);
}
}
zeros.push_back(N);
file.close();
long best = 1;
for (int i = 1; i < zeros.size(); i++) {
long local_max = max_prod_between0(zeros[i - 1] + 1, zeros[i], arr);
if (best < local_max) {
best = local_max;
}
}
cout << best << endl;
return 0;
}
```
### 20 (сложная)
См [презентацию](https://docs.google.com/presentation/d/1D_pjUcJExOYQsvUmQrAqnsfEpkEHZwnxBg4ftXPVJ-Y/edit?usp=sharing)
##### код
```cpp=
#include <fstream>
#include <iostream>
#include <string>
using namespace std;
int sum_for_matrix(int old_val, int new_val) {
if (new_val == 0) {
return 0;
}
return old_val + new_val;
}
int max_value_5(int n1, int n2, int n3, int n4, int n5) {
/**
* Returns masimum of the given 5 values
*/
int res = n1;
res = n2 > res ? n2 : res;
res = n3 > res ? n3 : res;
res = n4 > res ? n4 : res;
res = n5 > res ? n5 : res;
return res;
}
int main() {
fstream file;
file.open("./27data/20/27-20a.txt", ios::in);
string line;
getline(file, line);
int N = stoi(line);
int matrix[2][2]; // comments would be added to the slide
matrix[0][0] = 0;
matrix[0][1] = 0;
matrix[1][0] = 0;
matrix[1][1] = 0;
int previous[2]; // first digit - second digit
int current[2]; // first digit - second digit
int best_score = 0;
// read first row
getline(file, line, ' ');
previous[0] = stoi(line);
getline(file, line);
previous[1] = stoi(line);
int max_value = 0;
for (int i = 1; i < N; i++) {
// read next line
getline(file, line, ' ');
current[0] = stoi(line);
getline(file, line);
current[1] = stoi(line);
// find max on rows
int max1 = matrix[0][0] > matrix[0][1] ? matrix[0][0] : matrix[0][1];
int max2 = matrix[1][0] > matrix[1][1] ? matrix[1][0] : matrix[1][1];
// update matrix
matrix[0][0] = sum_for_matrix(max1, int(previous[1] == current[0])); // non-swapped - non-swapped
matrix[1][0] = sum_for_matrix(max1, int(previous[1] == current[1])); // non-swapped - swapped
matrix[0][1] = sum_for_matrix(max2, int(previous[0] == current[0])); // swapped - non-swapped
matrix[1][1] = sum_for_matrix(max2, int(previous[0] == current[1])); // swapped - swapped
// print matrix
//cout << " |" << previous[0] << previous[1] << " | " << previous[1] << previous[0] << endl;
//cout << current[0] << current[1] << " | " << matrix[0][0] << " | " << matrix[0][1] << endl;
//cout << current[1] << current[0] << " | " << matrix[1][0] << " | " << matrix[1][1] << endl;
//cout << endl;
// swap old and new values
previous[0] = current[0];
previous[1] = current[1];
// update max
max_value = max_value_5(max_value, matrix[0][0], matrix[0][1], matrix[1][0], matrix[1][1]);
}
file.close();
cout << max_value + 1 << endl;
return 0;
}
```
### 35
##### Условие
Дана последовательность N целых неотрицательных чисел. Необходимо определить количество пар положительных элементов этой последовательности, сумма которых четна, при этом между элементами пары есть хотя бы один ноль.
Входные данные: Даны два входных файла: файл A (27-35a.txt) и файл B (27-35b.txt), каждый из которых содержит в первой строке натуральное число N (1 < N < 10000) – количество чисел в последовательности. В следующих N строках записаны числа, входящие в последовательность, по одному в каждой строке.
##### Выходные данные:
Программа должна вывести одно число – количество найденных пар.
##### Пример входных данных:
6
2
1
4
0
3
4
Пример выходных данных для приведённого примера входных данных:
3
В ответе укажите два числа: сначала значение искомой суммы для файла А, затем для файла B.
##### Решение
- количество пар
- сумма чётна
- между ними есть 0
Создадим структуру, куда будем сохранять количество чётных и нечётных чисел в каждом блоке, разделённом нулями: `vector<vector<int> > arr`, где вложенный вектор будет иметь длину 2.
Допустим, мы собрали эти данные и получилась така матрица:
| Even | Odd |
|:---- | --- |
| 7 | 5 |
| 4 | 3 |
| 8 | 2 |
| 1 | 7 |
Тогда, чтобы найти количество пар, то кужно найти значение выражения (сумма чётна, если оба слагаемых имеют одинаковую чётность): $5*(3+2+7)+7*(4+8+1) + 3*(2+7)+4*(8+1)+ 2*7 + 8*1$.
Что можно записать в виде кода так
```cpp=
// найти суммы O(n)
int sum_even = 0;
int sum_odd = 0;
for(int i = 0; i < arr.size(); i++) {
sum_even += arr[i][0];
sum_odd += arr[i][1];
}
// найти количество комбинаций O(n)
int counter = 0;
for(int i = 0; i < arr.size() - 1; i++) {
// for even
sum_even -= arr[i][0];
counter += arr[i][0] * sum_even;
// for odd
sum_odd -= arr[i][1];
counter += arr[i][1] * sum_odd;
}
```
##### Полный код
```cpp=
#include <fstream>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int main() {
fstream file;
file.open("./27data/35/27-35b.txt");
string line;
getline(file, line);
int N = stoi(line);
// вместо двух колонок можно использовать два вектора
vector<int> odd_counts;
vector<int> even_counts;
int n_odd = 0;
int n_even = 0;
for (int line_index = 0; line_index < N; line_index++) {
getline(file, line);
int value = stoi(line);
if (value == 0) {
// end of block
odd_counts.push_back(n_odd);
even_counts.push_back(n_even);
n_odd = 0;
n_even = 0;
} else {
// update of the counters
if (value % 2 == 0) {
n_even++;
} else {
n_odd++;
}
}
}
// last append
odd_counts.push_back(n_odd);
even_counts.push_back(n_even);
// summation oaf arrays
int sum_even = 0;
int sum_odd = 0;
for (int i = 0; i < even_counts.size(); i++) {
sum_even += even_counts[i];
sum_odd += odd_counts[i];
}
// найти количество комбинаций O(n)
int counter = 0;
for (int i = 0; i < even_counts.size() - 1; i++) {
// for even
sum_even -= even_counts[i];
counter += even_counts[i] * sum_even;
// for odd
sum_odd -= odd_counts[i];
counter += odd_counts[i] * sum_odd;
}
cout << counter << endl;
}
```
### 37 - умеренно сложная
#### Условие
Имеется набор данных, состоящий из положительных целых чисел, не превышающих 10000. Необходимо найти количество троек, в которых сумма первых двух элементов равна третьему элементу. Порядок элементов тройки должен соответствовать порядку в последовательности.
##### Входные данные:
Даны два входных файла: файл A (27-37a.txt) и файл B (27-37b.txt), каждый из которых содержит в первой строке количество чисел N (1 ≤ N ≤ 100000). Каждая из следующих N строк содержит одно натуральное число, не превышающее 10 000.
##### Пример входного файла:
7
1
2
3
5
8
7
9
Для указанных входных данных таких троек 6: { 1 + 2 = 3, 1 + 8 = 9, 2 + 3 = 5, 2 + 5 = 7, 2 + 7 = 9, 3 + 5 = 8 }. В ответе укажите два числа: сначала количество троек для файла А, затем для файла B.
#### Решение
Важным фактором в этой задаче является то, что порядок элементов в последовательности меняться не должен. Иначе мы бы получили простую задачу на бинарный поиск.
Предлагаемый алгоритм:
- создаём таблицу из 10000 элементов
- заполняем её нулями
- в таблице считаем частоты встречающихся чисел
- для прочитанного числа `x` идём от 1 до `x/2` и ищем, есть ли пары, которые дают в сумме число `x`.
- сложность полученного алгоритма `O(n*x)`, где x - среднее значение чисел
- Если бы мы делали пребор, то это было бы `O(n^3)`, если с бин.поиском - `O(n^2log_n)` (квадрат из-за того, что массив должен быть всегда отсортирован)
#### Код
```cpp=
#include <fstream>
#include <iostream>
#include <string>
using namespace std;
int main() {
fstream file;
file.open("./27data/37/27-37b.txt", ios::in);
string line;
getline(file, line);
int N = stoi(line);
int arr[10001];
// fill array
for (int i = 0; i < 10000; i++) {
arr[i] = 0;
}
int counter = 0;
for (int line_index = 0; line_index < N; line_index++) {
getline(file, line);
int value = stoi(line);
for (int i = 1; i <= value / 2; i++) {
if (i == (value - i) && arr[i]) {
// 1 1 1 2 -> 2
// 1 1 1 1 2 -> 3+2+1 = (1+3)*3/2 = n(n-1)/2
// 1 1 -> 1
// 1 1 1 1 1 2-> 4+3+2+1
counter += arr[i] * (arr[i] - 1) / 2;
// cout << i << " " << value - i << " " << value << " " << arr[i] * (arr[i] - 1) / 2 << endl;
} else if (arr[i] && arr[value - i]) {
counter += arr[i] * arr[value - i];
// cout << i << " " << value - i << " " << value << " " << arr[i] * arr[value - i] << endl;
}
}
arr[value]++;
}
cout << counter << endl;
}
```
### 38-39
Примерно тот же подход, что и в 37. Создаём массив, встречаем, как часто встречается какое-то из чисел. Вопрос лишь в том, что считать в самом конце :slightly_smiling_face:.
##### Код
```cpp=
#include <fstream>
#include <iostream>
#include <string>
using namespace std;
int main() {
fstream file;
file.open("./27data/38/27-38b.txt", ios::in);
string line;
getline(file, line);
int N = stoi(line);
int frequency[10];
for (int i = 0; i < 10; i++) {
frequency[i] = 0;
}
for (int line_index = 0; line_index < N; line_index++) {
getline(file, line);
int v = stoi(line);
frequency[v]++;
}
file.close();
int counter = 0;
for (int i = 0; i < 10; i++) {
int update = frequency[i] / 2;
counter += update * 2 * i;
}
// find the digit in the center
for (int i = 9; i >= 0; i++) {
if (frequency[i] % 2 != 0) {
counter += i;
break;
}
}
cout << counter << endl;
return 0;
}
```
### 40-45 - умеренно сложная
#### Условие
Дана последовательность, которая состоит из троек натуральных чисел. Необходимо распределить все числа на три группы, при этом в каждую группу должно попасть ровно одно число из каждой исходной тройки. Сумма всех чисел в первой группе должна быть нечётной, во второй – чётной. Определите максимально возможную сумму всех чисел в третьей группе.
##### Входные данные:
Даны два входных файла: файл A (27-40a.txt) и файл B (27-40b.txt), каждый из которых содержит в первой строке количество чисел N (1 ≤ N ≤ 100000). Каждая из следующих N строк содержит три натуральных числа, не превышающих 10000.
##### Пример входного файла:
3
1 6 9
10 4 16
15 12 7
Для указанных данных искомая сумма равна 37, она соответствует такому распределению чисел по группам: (1, 4, 7), (9, 10, 12), (6, 16, 15). В ответе укажите два числа: сначала искомое значение для файла А, затем для файла B.
#### Решение
1. нечётная сумма
2. чётная сумма
3. максимальная сумма
Что нам мешает и составить сумму изначально максимальной? Тогда для данных из примера мы получим сумму $9+16+15=40$, и у нас останутся две колонки цифр:
1 6
10 4
12 7
Из представленных выше чисел только два нечётных:
- если их отнести к одной группе, то получатся две группы с нечётной суммой
- если их отнести к разным группам, то получатся две группы с нечётной суммой
В итоге, для данного случая, не получается разделить на нужные группы.
В каких случаях возможно разделить на группы, а в каких нет?
Обозначим за `1 1` ряды с двумя нечётными значениями, `0 0` - два чётных значения, а `0 1` - разные чётности. Получается, что можно разделить на группы разной чётности, если количество `0 1` нечётно.
Получается, для получения ответа на задачу нам нужно:
- сосчитать максимальную сумму (40 в примере)
- счтиаем минимальную нечётную разность между максимальным и немаксимальными элементами ряда (6 и 9 -> 3, или 15 - 12 = 3)
- считаем количество элементов `0 1` (2)
- если нужно, обновляем результат
##### Код
```cpp=
#include <fstream>
#include <iostream>
#include <string>
using namespace std;
bool is_median(int a, int b, int c) {
return (b <= a && a <= c) || (c <= a && a <= b);
}
int median(int a, int b, int c) {
if (is_median(a, b, c)) {
return a;
}
if (is_median(b, a, c)) {
return b;
}
return c;
}
int max(int a, int b, int c) {
int res = a;
res = res > b ? res : b;
res = res > c ? res : c;
return res;
}
int min(int a, int b, int c) {
int res = a;
res = res < b ? res : b;
res = res < c ? res : c;
return res;
}
int main() {
fstream file;
file.open("./27data/40/27-40a.txt", ios::in);
string line;
getline(file, line);
int N = stoi(line);
int v1, v2, v3;
int max_sum = 0;
int min_diff = -1;
int count_01 = 0;
for (int line_index = 0; line_index < N; line_index++) {
getline(file, line, ' ');
int v1 = stoi(line);
getline(file, line, ' ');
int v2 = stoi(line);
getline(file, line);
int v3 = stoi(line);
int max_v = max(v1, v2, v3);
int median_v = median(v1, v2, v3);
int min_v = min(v1, v2, v3);
// check median difference
int local_diff = max_v - median_v;
if (local_diff % 2 == 1 && (min_diff > local_diff || min_diff == -1)) {
min_diff = local_diff;
}
// check min diff
local_diff = max_v - min_v;
if (local_diff % 2 == 1 && (min_diff > local_diff || min_diff == -1)) {
min_diff = local_diff;
}
max_sum += max_v;
if ((median_v - min_v) % 2 != 0) {
count_01++;
}
}
if (count_01 % 2 == 0) {
max_sum -= min_diff;
}
cout << max_sum << endl;
return 0;
}
```
#### Комментарий к задачам того же типа
* Для задачи 41, но сумма чисел минимальна
* Для задачи 42: кол-во `1 1` должно стать чётно, кол-во `0 0` не имеет значения, а кол-во `0 1` должно стать чётным. Если условие не удовлетворяется, нужно или от `1 1` прийти к `0 1`, или от `0 1` прийти к `1 1`.
### 52-57 - странная задача
#### Условие
В файле записана последовательность натуральных чисел. Гарантируется, что все числа различны. Из этой последовательности нужно выбрать три числа, чтобы их сумма делилась на 3 и была наибольшей. Какую наибольшую сумму можно при этом получить?
##### Входные данные:
Даны два входных файла: файл A (27-52a.txt) и файл B (27-52b.txt), каждый из которых содержит в первой строке количество чисел N (1 ≤ N ≤ 100000). Каждая из следующих N строк содержит одно натуральное число, не превышающее $10^8$.
##### Пример входного файла:
5
5
4
13
7
10
Для указанных данных можно выбрать тройки 4, 13 и 7 (сумма 24), 4, 13 и 10 (сумма 27), 4, 7 и 10 (сумма 21) или 13, 7 и 10 (сумма 30). Наибольшая из сумм – 30. В ответе укажите два числа: сначала искомое значение для файла А, затем для файла B.
#### Решение:
5
4
13
7
10
Три минимаксимальных числа: 13, 10, 7 - их сумма 30.
Как можно из трёх чисел набрать сумму, кратную трём?
- все три числа имеют одинаковый остаток от деления на 3
- все три числа имеют разный остаток от деления на 3
Следовательно, в худшем случае нам надо хранить 9 числел (три минимума для каждого из трёх остатков).
##### Код
```cpp=
#include <algorithm>
#include <fstream>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int summ_if(int a, int b, int c) {
if (a == -1 || b == -1 || c == -1) {
return -1;
}
return a + b + c;
}
int main() {
fstream file;
file.open("./27data/52/27-52a.txt", ios::in);
string line;
getline(file, line);
int N = stoi(line);
int maximums[3][3];
// fill -1
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
maximums[i][j] = -1;
}
}
// main loop
for (int line_index = 0; line_index < N; line_index++) {
getline(file, line);
int v = stoi(line);
int remainder = v % 3;
for (int i = 0; i < 3; i++) {
if (maximums[remainder][i] < v || maximums[remainder][i] == -1) {
// shift back
for (int j = i + 1; j < 3; j++) {
maximums[remainder][j] = maximums[remainder][j - 1];
}
// set new value
maximums[remainder][i] = v;
break;
}
}
}
// print
// for (int i = 0; i < 3; i++) {
// for (int j = 0; j < 3; j++) {
// cout << maximums[i][j] << " ";
// }
// cout << endl;
// }
// count results
int r = summ_if(maximums[0][0], maximums[1][0], maximums[2][0]);
int r0 = summ_if(maximums[0][0], maximums[0][1], maximums[0][2]);
int r1 = summ_if(maximums[1][0], maximums[1][1], maximums[1][2]);
int r2 = summ_if(maximums[2][0], maximums[2][1], maximums[2][2]);
// I'm lazy to sort 4 numbers
vector<int> res;
if (r > 0) {
res.push_back(r);
}
if (r0 > 0) {
res.push_back(r0);
}
if (r1 > 0) {
res.push_back(r1);
}
if (r2 > 0) {
res.push_back(r2);
}
sort(res.begin(), res.end());
cout << res[res.size() - 1] << endl;
}
```
##### Примечание к задаче 54:
Сумма четырёх чисел делится на 4, если
- Все 4 числа имеют одинаковую чётность
- Остатки имеют вид:
- 1+3+2+2
- 1+3+0+0
- 2+2+0+0
(нужно обновлять 16 значений)
### 62
#### Условие
Имеется набор данных, состоящий из N различных положительных чисел. Необходимо из этих чисел построить самую длинную возрастающую арифметическую прогрессию c шагом от 1 до 100 включительно и вывести её длину.
##### Входные данные:
Даны два входных файла: файл A (27-62a.txt) и файл B (27-62b.txt), каждый из которых содержит в первой строке количество чисел N (1 ≤ N ≤ 100000). Каждая из следующих N строк содержит одно натуральное число, не превышающее $10^8$.
##### Пример входного файла:
6
1
4
7
3
20
5
Для указанных входных данных самая большая арифметическая прогрессия будет {1, 3, 5, 7} с шагом 2 и длиной 4. Программа должна вывести ответ 4. В ответе укажите два числа: сначала искомое значение для файла А, затем для файла B.
#### Решение
Как можно заметить из примера, порядок данных нам не важен, поэтому можно завести boolean массив из $10^8$ элементов и проверить наличие прогрессий от 1 до 100:
Получившая сложность будет составлять `100*O(n)=O(n)`.
Проблема - $10^8$ - очень большое значение, у меня не вышло выделить столько памяти.
Решение проблемы - решение "в лоб":
- сохраняем прочитанные значения в массив
- сортируем, O(nlog(n))
- используя бин. поиск ищем длину последовательности (O(nlog(n)))
##### Код:
```cpp=
#include <algorithm>
#include <fstream>
#include <iostream>
#include <string>
using namespace std;
int main() {
fstream file;
file.open("./27data/62/27-62a.txt");
string line;
getline(file, line);
int N = stoi(line);
int arr[N];
// reading
for (int line_index = 0; line_index < N; line_index++) {
getline(file, line);
arr[line_index] = stoi(line);
}
file.close();
sort(arr, arr + N);
int max_length = 1;
for (int step = 2; step <= 100; step++) {
for (int i = 0; i < N; i++) {
int current_val = arr[i];
int length = 0;
// log(n)
while (binary_search(arr + i, arr + N, current_val)) {
current_val += step;
length++;
}
if (length > max_length) {
max_length = length;
}
}
}
// total - nlog(n)
cout << max_length << endl;
}
```
### 63
#### Условие
В файле записана последовательность натуральных чисел. Из этой последовательности нужно выбрать четыре числа так, чтобы их сумма при делении на число 9 не давала остаток ноль и была наименьшей. Какова сумма этой четверки чисел?
###### Входные данные:
Даны два входных файла: файл A (27-63a.txt) и файл B (27-63b.txt), каждый из которых содержит в первой строке количество чисел N (4 ≤ N ≤ 100000). Каждая из следующих N строк файлов содержит одно натуральное число, не превышающее число $10^8$.
###### Пример входного файла:
6
7
23
2
8
12
5
Для указанных данных искомая четвёрка – 5, 7, 2, 8 (сумма 22). В ответе укажите два числа: сначала искомое значение для файла А, затем для файла B.
##### Решение
Можно решать, как задачу 52, например, но у этого есть свои недостатки - много вариантов перебора. Может есть идеи лучше?
Другой подход - найти 4 минимума и пока не наёдётся подходящая сумма - ищем другой минимум (худший случай - O(n^2))
Как можно оптимизировать? - Отстртировать -> O(nlogn)
Всё же, вариант с матрицей 9х4 не тка уж плох:
Всего можно будет выбрать одну из $36*35*34*33$ комбинаций, но количество вариантов сокращается, если выбирать вначале остаток ($9^4$ комбинаций), а потом из колонки брать минимум.
Покажу вариант с матрицей минимумов (можно записать это более элегантно, но пока так):
```cpp=
#include <fstream>
#include <iostream>
#include <string>
using namespace std;
int main() {
fstream file;
file.open("./27data/63/27-63b.txt", ios::in);
string line;
getline(file, line);
int N = stoi(line);
int minimums[9][4];
// fill -1
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 4; j++) {
minimums[i][j] = -1;
}
}
// main loop
for (int line_index = 0; line_index < N; line_index++) {
getline(file, line);
int v = stoi(line);
int remainder = v % 9;
for (int i = 0; i < 4; i++) {
if (minimums[remainder][i] > v || minimums[remainder][i] == -1) {
// shift back
for (int j = 3; j > i; j--) {
minimums[remainder][j] = minimums[remainder][j - 1];
}
// set new value
minimums[remainder][i] = v;
break;
}
}
}
file.close();
int min_sum = -1;
for (int i0 = 0; i0 < 9; i0++) {
for (int i1 = i0; i1 < 9; i1++) {
for (int i2 = i1; i2 < 9; i2++) {
for (int i3 = i2; i3 < 9; i3++) {
int indexes[9];
for (int i = 0; i < 9; i++) {
indexes[i] = -1;
}
indexes[i0]++;
indexes[i1]++;
indexes[i2]++;
indexes[i3]++;
int sum = 0;
for (int i = 0; i < 9; i++) {
while (indexes[i] != -1) {
if (minimums[i][indexes[i]] == -1) {
sum = 0;
break;
}
sum += minimums[i][indexes[i]];
indexes[i]--;
}
if (indexes[i] >= 0 && minimums[i][indexes[i]] == -1) {
sum = 0;
break;
}
}
if (sum == 0) {
continue;
}
if (sum % 9 != 0 && (min_sum == -1 || sum < min_sum)) {
min_sum = sum;
}
}
}
}
}
cout << min_sum << endl;
}
```
### 64-65
На первый взгляд, относится к первому типу, но на самом деле - нет
#### Условие
Набор данных состоит из пар натуральных чисел. Необходимо выбрать из набора некоторые пары так, чтобы первое число в каждой выбранной паре было нечётным, сумма бо́льших чисел во всех выбранных парах была нечётной, а сумма меньших – чётной. Какую наибольшую сумму чисел во всех выбранных парах можно при этом получить?
##### Входные данные:
Даны два входных файла: файл A (27-64a.txt) и файл B (27-64b.txt), каждый из которых содержит в первой строке количество чисел N (N ≤ 100000). Каждая из следующих N строк файлов содержит два натуральных числа, не превышающих 10000.
##### Пример входного файла:
4
7 3
4 11
9 12
15 9
В данном случае есть три подходящие пары: (7, 3), (9, 12) и (15, 9). Пара (4, 11) не подходит, так как в ней первое число чётное. Чтобы удовлетворить требования, надо взять пары (9, 12) и (15, 9). Сумма бо́льших чисел в этом случае равна 27, сумма меньших равна 18. Общая сумма равна 45. В ответе надо указать число 45. В ответе укажите два числа: сначала искомое значение для файла А, затем для файла B.
##### Код
```cpp=
#include <fstream>
#include <iostream>
#include <string>
using namespace std;
int main() {
fstream file;
file.open("27-64a.txt", ios::in);
string line;
getline(file, line);
int N = stoi(line);
// pairs with min summ
int pairs[2][2][2] = {{{0, 0}, {10000, 10000}},
{{10000, 10000}, {10000, 10000}}};
int min_sum = 0;
int max_sum = 0;
for (int i = 0; i < N; i++) {
getline(file, line, ' ');
int el1 = stoi(line);
if (el1 % 2 == 0) {
getline(file, line);
continue;
}
getline(file, line);
int el2 = stoi(line);
if (el1 > el2) {
// swap
int t = el2;
el2 = el1;
el1 = t;
}
// el1 < el2
min_sum += el1;
max_sum += el2;
// update array
if ((pairs[el1 % 2][el2 % 2][0] + pairs[el1 % 2][el2 % 2][1]) > (el1 + el2)) {
pairs[el1 % 2][el2 % 2][0] = el1;
pairs[el1 % 2][el2 % 2][1] = el2;
}
}
int sum = min_sum + max_sum;
// min_sum should be even, max_sum should be odd
int index_min = min_sum % 2;
int index_max = int((max_sum % 2 != 1));
int subPair0 = pairs[index_min][index_max][0];
int subPair1 = pairs[index_min][index_max][1];
if ((min_sum - subPair0) % 2 != 0 || (max_sum - subPair1) % 2 == 0) {
cout << "Something went wrong" << endl;
}
cout << sum - subPair0 - subPair1 << endl;
cout << min_sum - subPair0 << endl;
cout << max_sum - subPair1 << endl;
}
```
Sign in with Wallet
Connect another wallet