По каналу связи передавались положительные целые числа, не превышающие 10000 — результаты измерений, полученных в ходе эксперимента (количество измерений N известно заранее, гарантируется, что N > 2). После окончания эксперимента передаётся контрольное значение — наибольшее число R, удовлетворяющее следующим условиям.
1. R — сумма двух различных переданных элементов последовательности («различные» означает, что нельзя просто удваивать переданные числа, суммы различных, но равных по величине элементов допускаются).
2. R кратно 3.
3. Если в последовательности нет двух чисел, сумма которых кратна 3, контрольное значение считается равным 1.
В результате помех при передаче как сами числа, так и контрольное значение могут быть искажены.
Входные данные.
На вход программе в первой строке подаётся количество чисел N (N > 2). В каждой из последующих N строк записано одно натуральное число, не превышающее 10 000.
Пример организации исходных данных во входном файле:
6
100
8
33
145
19
84
Пример выходных данных для приведённого выше примера входных данных:
153
В ответе укажите два числа: сначала контрольное для значений из файла А, затем из файла B.
Ответ:
Сумма двух чисел может быть кратна 3 в двух случаях: либо оба слагаемых кратны 3, либо остаток от деления на 3 одного из них равен 1, а другого — 2.
Программа, вычисляющая контрольное значение, читает все входные данные один раз, не запоминая их в массиве. Для прочитанного фрагмента входной последовательности программа хранит значения самых больших чисел, дающих при делении на 3 остатки 1 и 2, и два самых больших числа, кратных 3.
М1 — самое большое число, дающее при делении на 3 остаток 1;
М2 — самое большое число, дающее при делении на 3 остаток 2;
M3A — самое большое число, кратное 3;
M3B — второе по величине число, кратное 3.
После того, как все данные прочитаны, искомое контрольное значение вычисляется, как большая из сумм M1 + M2 и M3A + M3B, но прежде чем вычислять каждую из этих сумм, нужно убедиться, что входящие в неё слагаемые определены, то есть в последовательности были числа с соответствующими остатками.
Приведём решение задачи на языке Pascal.
var M1,M2,M3A,M3B,R,r1,r2,res,i,N,x: longint;
f: text;
begin
M1 := 0; M2:=0;
M3A := 0; M3B:=0;
assign(f,'28128_A.txt');
reset(f);
readln(f, n);
while not eof(f) do begin
readln(f, x);
case x mod 3 of
0:
if x>M3A then begin
M3B:=M3A; M3A:=x
end
else if x>M3B then M3B:=x;
1:
if x>M1 then M1:=x;
2:
if x>M2 then M2:=x;
end;
end;
if (M1>0) and (M2>0) then r1:=M1+M2
else r1:=1;
if (M3A>0) and (M3B>0) then r2:=M3A+M3B
else r2:=1;
if r1>r2 then res:=r1
else res:=r2;
writeln(res);
end.
В результате работы данного алгоритма при вводе данных из файла A ответ — 19020, из файла B — 19998.
Примечание. Путь к файлу необходимо указать согласно расположению файла на Вашем компьютере.