Question

На вход даны пары чисел. Нужно выбрать из каждой пары по одному числу так, чтобы сумма всех выбранных чисел не была кратна 4 и при этом была максимально возможной. Напишите программу, выводящую такую сумму на экран. Если же ее невозможно получить, выведите 0. Баллы начисляются за ту из подзадач, что решена на большее количество баллов. Задача А дает 2 балла, задача Б - 4 балла. В задаче А приведите неэффективный алгоритм. При решении указывайте, какую подзадачу делаете. За алгоритм, неэффективный по времени ИЛИ памяти, дается 3 балла, по времени И памяти - 2 балла.

Задача А. Количество пар известно заранее и равно 6. Числа не превышают 30 000.

Задача Б. Количество пар N не известно заранее и может принимать значения 2 <= N <= 200 000. На вход подается сначала количество пар, затем сами пары. Числа по модулю не превышают 30 000.

Задача А. Количество пар известно заранее и равно 6. Числа не превышают 30 000.

Задача Б. Количество пар N не известно заранее и может принимать значения 2 <= N <= 200 000. На вход подается сначала количество пар, затем сами пары. Числа по модулю не превышают 30 000.

Accepted Answer

Answer

### СТАТЕМЕНТ

На вход даны пары чисел. Требуется выбрать из каждой пары по одному числу так, чтобы сумма всех выбранных чисел была максимально возможной и при этом не делилась на 4. Если такую сумму получить невозможно, вывести 0.

**Задача А (2 балла).** Количество пар фиксировано и равно 6. Числа не превышают 30 000.

**Задача Б (4 балла).** Количество пар $N$ неизвестно заранее, $2 \le N \le 200\,000$. На вход подаётся сначала количество пар, затем сами пары. Числа по модулю не превышают 30 000.

### РЕШЕНИЕ

Идея решения: выбрать из каждой пары максимальное число и сложить их; если сумма делится на 4, заменить одно из слагаемых на его пару, выбрав замену с наименьшей разностью, которая сама не делится на 4.

**Обоснование.** При замене максимума $\max$ на минимум $\min$ из пары сумма изменяется на величину $\min - \max = -(\max - \min)$. Чтобы новая сумма не делилась на 4, нужно вычесть разность, остаток которой от деления на 4 не равен нулю. Для максимизации результата выбираем наименьшую такую разность.

**Алгоритм:**
1. Вычислить сумму $S$ максимальных элементов из всех пар.
2. Найти минимальную разность $d = \max - \min$ в паре, такую что $d 
ot\equiv 0 \pmod{4}$.
3. Если $S \equiv 0 \pmod{4}$:
   - Если $d$ найдена, вывести $S - d$.
   - Иначе вывести 0.
4. Если $S 
ot\equiv 0 \pmod{4}$, вывести $S$.

**Решение для задачи Б (оптимизированное, $O(n)$):**

```python
n = int(input())
d = 30001
s = 0

for i in range(n):
    a, b = map(int, input().split())
    ma = max(a, b)
    mi = min(a, b)
    if (ma - mi) % 4 != 0 and ma - mi < d:
        d = ma - mi
    s += ma

if s % 4 == 0:
    if d == 30001:
        s = 0
    else:
        s -= d

print(s)
```

Сложность: $O(n)$ — один проход по входным данным.

**Решение для задачи А (неоптимизированное, $O(2^6) = O(64)$):**

```python
pairs = []
for _ in range(6):
    a, b = map(int, input().split())
    pairs.append((a, b))

best = -1

for mask in range(1 << 6):
    current_sum = 0
    for i in range(6):
        if mask & (1 << i):
            current_sum += pairs[i][0]
        else:
            current_sum += pairs[i][1]
    
    if current_sum % 4 != 0:
        best = max(best, current_sum)

print(best if best != -1 else 0)
```

Сложность: $O(2^n)$ где $n = 6$ — перебор всех $2^6 = 64$ вариантов выбора.

### ОТВЕТ

Задание №27ПрограммированиеЕГЭ по информатике