Имеется набор данных, состоящий из троек положительных целых чисел.
Условие
Имеется набор данных, состоящий из троек положительных целых чисел. Необходимо выбрать из каждой тройки ровно одно число так, чтобы сумма всех выбранных чисел не делилась на k = 109 и при этом была максимально возможной. Гарантируется, что искомую сумму получить можно. Программа должна напечатать одно число — максимально возможную сумму, соответствующую условиям задачи.Входные данные.Файл AФайл BДаны два входных файла (файл A и файл B), каждый из которых содержит в первой строке количество троек N (1 ≤ N ≤ 1 000 000). Каждая из следующих N строк содержит три натуральных числа, не превышающих 20 000. Пример организации исходных данных во входном файле:61 3 75 12 66 9 115 4 83 5 41 1 1Для указанных входных данных, в случае, если k = 5, значением искомой суммы является число 44. В ответе укажите два числа: сначала значение искомой суммы для файла А, затем для файла B. Ответ:
Ответ
7845948819088760
Решение по шагам
Как рассуждать
Решение. Будем последовательно считывать тройки чисел из файла и прибавлять к переменной sum максимальное число в тройке. Также будем находить минимальную разницу между максимальным числом в тройке и минимальным числом в тройке, между максимальным числом в тройке и средним по значению числом в тройке. Разница между числами при этом не должна делиться на 109 без остатка. В конце выполнения программы будем проверять, делится ли найденная сумма на 109 без остатка, и если не делится — будем выводить найденную сумму, иначе будем выводить найденную сумму, вычтя из неё найденную минимальную разницу между числами. Приведём решение задачи на языке Pascal.var x, y, z: integer;n: integer;sum: int64;minDif: integer;f: text;begin assign(f,'C:\27_B.txt'); reset(f); readln(f, n); sum := 0; minDif := 40001; while not eof(f) do begin readln(f, x, y, z); if (x >= y) and (x >= z) then begin sum := sum + x; if (((abs(x - y)) mod 109 <>
Осталось ещё 7 шагов — откроются после входа:
- Шаг 2
- Шаг 3
- Шаг 4
- Шаг 5
- Шаг 6
- Шаг 7
- Шаг 8
Бесплатно · займёт минуту