Гарантируется, что искомую сумму получить можно. Программа должна
Условие
Имеется набор данных, состоящий из пар положительных целых чисел. Необходимо выбрать из каждой пары ровно одно число так, чтобы сумма всех выбранных чисел не делилась на 3 и при этом была минимально возможной. Гарантируется, что искомую сумму получить можно. Программа должна напечатать одно число — минимально возможную сумму, соответствующую условиям задачи.
Входные данные.
Файл AФайл BДаны два входных файла (файл A и файл B), каждый из которых содержит в первой строке количество пар N (1 ≤ N ≤ 100000). Каждая из следующих N строк содержит два натуральных числа, не превышающих 10 000. Пример организации исходных данных во входном файле:61 35 126 95 43 31 1Для указанных входных данных значением искомой суммы должно быть число 20.В ответе укажите два числа: сначала значение искомой суммы для файла А, затем для файла B. Предупреждение: для обработки файла B не следует использовать переборный алгоритм, вычисляющий сумму для всех возможных вариантов, поскольку написанная по такому алгоритму программа будет выполняться слишком долго. Ответ:
Ответ
Ответ и полный разбор откроются после входа
Посмотреть ответРешение по шагам
Как рассуждать
Решение. Последовательно считывая данные из файла, будем прибавлять к сумме минимальное число в паре. Также заметим, что в случае, если получившееся в результате суммирование минимальных чисел во всех парах число будет кратно трём, достаточно будет прибавить к этой сумме минимальную разницу между какими-либо двумя числами. Для этого при считывании пар помимо минимального числа в каждой паре будем искать минимальную разницу среди пар, не кратную трём. Приведём решение задачи на языке Pascal.var x, y: integer;n: integer;sum: integer;mindif: integer;f: text;begin assign(f,'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 <>
Осталось ещё 2 шага
then mindif := abs(x-y); end; if sum mod 3 <>…
Приведём решение Романа Князева на языке…
Бесплатно · займёт минуту