Question

Имеется набор данных, состоящий из пар положительных целых чисел. Необходимо выбрать из каждой пары ровно одно число так, чтобы сумма всех выбранных чисел не делилась на 3 и при этом была максимально возможной. Гарантируется, что искомую сумму получить можно.

**Входные данные.** Два входных файла (файл A и файл B). Каждый содержит в первой строке количество пар $N$ ($1 \le N \le 100\,000$). Каждая из следующих $N$ строк содержит два натуральных числа, не превышающих 10 000.

**Пример входных данных:**
```
6
1 3
5 12
6 9
5 4
3 3
1 1
```

Для указанных данных ответ — 32.

**Выходные данные.** Одно число — максимально возможная сумма, удовлетворяющая условиям.

**Примечание.** Для обработки файла B не следует использовать переборный алгоритм, вычисляющий сумму для всех возможных вариантов, так как программа будет выполняться слишком долго.

---

Accepted Answer

Answer

Идея решения: выбрать из каждой пары максимальное число; если полученная сумма делится на 3, вычесть из неё минимальную разницу между числами в паре, которая сама не делится на 3. **Логика алгоритма:** 1. Суммируем максимальные значения из всех пар — это даёт верхнюю границу. 2. Если сумма не делится на 3, это и есть ответ. 3. Если сумма делится на 3, нужно уменьшить её на минимальную разницу $|x - y|$ в какой-либо паре, при условии, что эта разница сама не делится на 3. Вычитание такой разницы изменит остаток суммы при делении на 3 ровно на 1 или 2, что гарантирует результат, не кратный 3. **Решение на Python:** ```python f = open("27_A.txt") lines = f.readlines() n = int(lines[0]) total_sum = 0 min_diff = 10**6 for i in range(1, n + 1): x, y = map(int, lines[i].split()) total_sum += max(x, y) diff = abs(x - y) if diff % 3 != 0: min_diff = min(min_diff, diff) if total_sum % 3 != 0: print(total_sum) else: print(total_sum - min_diff) ``` **Решение на Pascal:** ```pascal var x, y: longint; n: longint; sum: longint; mindif: longint; f: text; begin assign(f, 'C:\27_A.txt'); reset(f); readln(f, n); sum := 0; mindif := 20001; while not eof(f) do begin readln(f, x, y); if x > y then sum := sum + x else sum := sum + y; if (abs(x - y) < mindif) and (abs(x - y) mod 3 <> 0) then mindif := abs(x - y); end; if sum mod 3 <> 0 then writeln(sum) else writeln(sum - mindif); end. ``` **Прогон на примере:** Пары: (1, 3), (5, 12), (6, 9), (5, 4), (3, 3), (1, 1). Максимумы: 3, 12, 9, 5, 3, 1. Сумма = 33. Разницы, не кратные 3: $|1-3|=2$, $|5-12|=7$, $|6-9|=3$ (кратна 3, пропускаем), $|5-4|=1$, $|3-3|=0$ (кратна 3, пропускаем), $|1-1|=0$ (кратна 3, пропускаем). Минимальная разница = 1. Так как 33 делится на 3, вычитаем 1: $33 - 1 = 32$. Сложность: $O(n)$ — один проход по всем парам. ---

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