Дана последовательность N целых неповторяющихся положительных чисел. Рассматриваются все пары элементов последовательности, разность которых делится на m = 60. Среди всех таких пар нужно найти и вывести пару с максимальной суммой элементов. Если одинаковую максимальную сумму имеют несколько пар, можно вывести любую из них. Если подходящих пар в последовательности нет, нужно вывести два нуля.
Описание входных и выходных данных.
В первой строке входных данных задаётся количество чисел N (2 ≤ N ≤ 10 000). В каждой из последующих N строк записано одно натуральное число, не превышающее 10 000. Гарантируется, что никакое число не встречается в последовательности более одного раза.
Пример входных данных:
8
75
123
5
40
15
3
65
80
Пример выходных данных для приведённого выше примера входных данных:
3 123
Пояснение. Из данных восьми чисел можно составить три пары, удовлетворяющие условию: (15, 75), (3, 123), (5, 65). Наибольшая сумма получается в паре (3, 123).
Требуется написать эффективную по времени и по памяти программу для решения описанной задачи. Программа считается эффективной по времени, если при увеличении количества исходных чисел N в k раз время работы программы увеличивается не более чем в k раз. Программа считается эффективной по памяти, если память, необходимая для хранения всех переменных программы, не превышает 1 Кбайт и не увеличивается с ростом N.
Максимальная оценка за правильную (не содержащую синтаксических ошибок и дающую правильный ответ при любых допустимых входных данных) программу, эффективную по времени и по памяти, — 4 балла. Максимальная оценка за правильную программу, эффективную только по времени — 3 балла. Максимальная оценка за правильную программу, не удовлетворяющую требованиям эффективности, — 2 балла. Вы можете сдать одну программу или две программы решения задачи (например, одна из программ может быть менее эффективна). Если Вы сдадите две программы, то каждая из них будет оцениваться независимо от другой, итоговой станет бо́льшая из двух оценок.
Перед текстом программы обязательно кратко опишите алгоритм решения. Укажите используемый язык программирования и его версию.
Описание входных и выходных данных.
В первой строке входных данных задаётся количество чисел N (2 ≤ N ≤ 10 000). В каждой из последующих N строк записано одно натуральное число, не превышающее 10 000. Гарантируется, что никакое число не встречается в последовательности более одного раза.
Пример входных данных:
8
75
123
5
40
15
3
65
80
Пример выходных данных для приведённого выше примера входных данных:
3 123
Пояснение. Из данных восьми чисел можно составить три пары, удовлетворяющие условию: (15, 75), (3, 123), (5, 65). Наибольшая сумма получается в паре (3, 123).
Требуется написать эффективную по времени и по памяти программу для решения описанной задачи. Программа считается эффективной по времени, если при увеличении количества исходных чисел N в k раз время работы программы увеличивается не более чем в k раз. Программа считается эффективной по памяти, если память, необходимая для хранения всех переменных программы, не превышает 1 Кбайт и не увеличивается с ростом N.
Максимальная оценка за правильную (не содержащую синтаксических ошибок и дающую правильный ответ при любых допустимых входных данных) программу, эффективную по времени и по памяти, — 4 балла. Максимальная оценка за правильную программу, эффективную только по времени — 3 балла. Максимальная оценка за правильную программу, не удовлетворяющую требованиям эффективности, — 2 балла. Вы можете сдать одну программу или две программы решения задачи (например, одна из программ может быть менее эффективна). Если Вы сдадите две программы, то каждая из них будет оцениваться независимо от другой, итоговой станет бо́льшая из двух оценок.
Перед текстом программы обязательно кратко опишите алгоритм решения. Укажите используемый язык программирования и его версию.
💡 Пошаговый разбор и решение:
Сумма двух чисел кратна m, остатки от деления этих чисел на m равны. При этом для получения максимальной суммы нужно взять два наибольших числа с одинаковым остатком.
Будем хранить в одном массиве из m элементов максимальные числа, имеющие соответствующий остаток от деления на m, а в другом — вторые по величине, и из всех таких пар выберем пару с наибольшей суммой
При этом нужно убедиться, что второй максимум существует, — иначе в последовательности нет двух чисел с таким остатком.
Ниже приведена программа на алгоритмическом языке, реализующая этот алгоритм
Пример 1. Программа на языке Паскаль. Программа эффективна по времени и памяти.
const m = 60;
var
m1: array[0..m-1] of integer;
m2: array[0..m-1] of integer;
i, N: integer;
x: integer; | очередное число из последовательности
p: integer; | остаток
pm: integer; | остаток, дающий лучшую сумму
sm: integer; | лучшая сумма
begin
for i := 0 to m-1 do begin
mn[i] := 0;
mx[i] := 0;
end;
pm := 0;
sm := 0;
readln(N);
for i := 0 to N-1 do begin
readln(x);
p:= x mod m;
if (x > m1[p]) then begin
m2[p] := m1[p];
m1[p] := x;
end
else if (x > m2[p]) then
m2[p] := x;
if (m1[p]+m2[p] > sm) and (m2[p] > 0) then begin
pm := p;
sm := m1[p] + m2[p];
end;
end;
if sm = 0 then writeln('0 0')
else writeln(m1[pm], ' ', m2[pm]);
end.
В приведённом решении лучшая пара находится «на лету»: после обработки каждого числа из последовательности проверяется, не увеличилась ли возможная сумма.
Эту проверку можно провести после завершения ввода, вычислив суммы для всех остатков и сравнив их. Такая программа тоже эффективна по времени и по памяти, а при больших N она работает даже быстрее предыдущей, т. к. выполняет меньше вычислений и сравнений.
Ниже приведена реализующая этот алгоритм программа на языке Python
Пример 2. Правильная, но неэффективная программа на языке Python.
m = 60
m1 = [0] * m
m2 = [0] * m
N = int(input())
for i in range(N):
x = int(input())
p = x % m
if x > m1[p]:
m2[p] = m1[p]
m1[p] = x
elif x > m2[p]:
m2[p] = x
p = 0; s = 0
for i in range(m):
if m2[i] > 0 and m1[i]+m2[i]> s:
p = i
s = m1[i]+m2[i]
if s == 0:
print(0,0)
else:
print(m1[p], m2[p])
Возможно также «лобовое» решение: запишем все исходные числа в массив, переберём все возможные пары и выберем подходящую. Такое решение не является эффективным ни по памяти (требуемая память зависит от размера исходных данных), ни по времени (количество возможных пар, а значит, количество действий и время счёта с ростом количества исходных элементов растёт квадратично). Подобная программа оценивается не выше 2 баллов.
Ниже приведена реализующая описанный выше алгоритм программа на языке Паскаль (использована версия PascalABC)
Пример 3. Правильная, но неэффективная программа на языке Паскаль.
const m=60;
var
N: integer; {количество чисел}
a: array [1..10000] of integer; {исходные данные}
x1, x2: integer; {ответ – пара чисел}
i,j: integer;
begin
readln(N);
for i:=1 to N do readln(a[i]);
x1:=0; x2:=0;
for i := 1 to N do begin
for j := i+1 to N do begin
if ((a[i] - a[j]) mod m = 0) and (a[i]+a[j]) > x1+x2) then begin
x1:=a[i]; x2:=a[j]
end
end
end;
writeln(x1, ' ', x2)
end.
Будем хранить в одном массиве из m элементов максимальные числа, имеющие соответствующий остаток от деления на m, а в другом — вторые по величине, и из всех таких пар выберем пару с наибольшей суммой
При этом нужно убедиться, что второй максимум существует, — иначе в последовательности нет двух чисел с таким остатком.
Ниже приведена программа на алгоритмическом языке, реализующая этот алгоритм
Пример 1. Программа на языке Паскаль. Программа эффективна по времени и памяти.
const m = 60;
var
m1: array[0..m-1] of integer;
m2: array[0..m-1] of integer;
i, N: integer;
x: integer; | очередное число из последовательности
p: integer; | остаток
pm: integer; | остаток, дающий лучшую сумму
sm: integer; | лучшая сумма
begin
for i := 0 to m-1 do begin
mn[i] := 0;
mx[i] := 0;
end;
pm := 0;
sm := 0;
readln(N);
for i := 0 to N-1 do begin
readln(x);
p:= x mod m;
if (x > m1[p]) then begin
m2[p] := m1[p];
m1[p] := x;
end
else if (x > m2[p]) then
m2[p] := x;
if (m1[p]+m2[p] > sm) and (m2[p] > 0) then begin
pm := p;
sm := m1[p] + m2[p];
end;
end;
if sm = 0 then writeln('0 0')
else writeln(m1[pm], ' ', m2[pm]);
end.
В приведённом решении лучшая пара находится «на лету»: после обработки каждого числа из последовательности проверяется, не увеличилась ли возможная сумма.
Эту проверку можно провести после завершения ввода, вычислив суммы для всех остатков и сравнив их. Такая программа тоже эффективна по времени и по памяти, а при больших N она работает даже быстрее предыдущей, т. к. выполняет меньше вычислений и сравнений.
Ниже приведена реализующая этот алгоритм программа на языке Python
Пример 2. Правильная, но неэффективная программа на языке Python.
m = 60
m1 = [0] * m
m2 = [0] * m
N = int(input())
for i in range(N):
x = int(input())
p = x % m
if x > m1[p]:
m2[p] = m1[p]
m1[p] = x
elif x > m2[p]:
m2[p] = x
p = 0; s = 0
for i in range(m):
if m2[i] > 0 and m1[i]+m2[i]> s:
p = i
s = m1[i]+m2[i]
if s == 0:
print(0,0)
else:
print(m1[p], m2[p])
Возможно также «лобовое» решение: запишем все исходные числа в массив, переберём все возможные пары и выберем подходящую. Такое решение не является эффективным ни по памяти (требуемая память зависит от размера исходных данных), ни по времени (количество возможных пар, а значит, количество действий и время счёта с ростом количества исходных элементов растёт квадратично). Подобная программа оценивается не выше 2 баллов.
Ниже приведена реализующая описанный выше алгоритм программа на языке Паскаль (использована версия PascalABC)
Пример 3. Правильная, но неэффективная программа на языке Паскаль.
const m=60;
var
N: integer; {количество чисел}
a: array [1..10000] of integer; {исходные данные}
x1, x2: integer; {ответ – пара чисел}
i,j: integer;
begin
readln(N);
for i:=1 to N do readln(a[i]);
x1:=0; x2:=0;
for i := 1 to N do begin
for j := i+1 to N do begin
if ((a[i] - a[j]) mod m = 0) and (a[i]+a[j]) > x1+x2) then begin
x1:=a[i]; x2:=a[j]
end
end
end;
writeln(x1, ' ', x2)
end.
📚 Похожие разобранные задания по предмету:
ID 29681 • Задание №3
Сколько записей удовлетворяют условию «Пол = 'м' и Физика > Обществознание»?
Фамилия | Пол | Математика | ...
ID 30588 • Задание №7
Дан фрагмент электронной таблицы.
| A | B | C
1 | | 2 | 8
2 | =(A1+1)*B1*3 | =(A1+1)*(A1+3) | =A1*C1/(A1−2)...
Официальные критерии проверки ФИПИ:
Критерии проверки:
Пояснения для проверяющих.
1. Задание Б является усложнением задания А. Если в качестве решения задания Б представлено решение задания А, то согласно приведённым ниже критериям, его оценка будет такой же, как если бы это решение было представлено в качестве решения задания А.
2. Два задания и, соответственно, возможность для экзаменуемого представить две программы дают ученику возможность (при его желании) сначала написать менее сложное и менее эффективное решение (задание А), которое даёт ему право получить два балла, а затем приступить к поиску более эффективного решения.
3. Каждая из программ, представленных экзаменуемым (но не более двух), оценивается по нижеследующим критериям. В качестве итоговой оценки берётся наибольшая из двух оценок.
Критерии оценивания выполнения задания | Баллы
Программа правильно работает для любых входных данных произвольного размера. Используемая память не зависит от количества прочитанных чисел, а время работы пропорционально этому количеству.
Допускается наличие в тексте программы до трех синтаксических ошибок одного из следующих видов:
1) пропущен или неверно указан знак пунктуации;
2) неверно написано или пропущено зарезервированное слово языка программирования;
3) не описана или неверно описана переменная;
4) применяется операция, недопустимая для соответствующего типа данных.
Если одна и та же ошибка встречается несколько раз, это считается за одну ошибку. | 4
Не выполнены условия, позволяющие поставить 4 балла. Программа в целом работает правильно для любых входных данных произвольного размера. Время работы пропорционально количеству введённых чисел, правильно указано, какие величины должны вычисляться по ходу чтения элементов последовательности чисел.
Количество синтаксических ошибок (описок) указанных выше видов — не более пяти.
Используемая память, возможно, зависит от количества прочитанных чисел (например, входные данные запоминаются в массиве или другой структуре данных (контейнер priority_queue, vector, set или map в С++)).
Допускается ошибка при вводе данных, неверный или неполный вывод результатов или неверная работа программы
в «экзотических» ситуациях. Кроме того, допускается наличие одной ошибки, принадлежащей к одному из следующих видов ошибок:
1) ошибка при инициализации минимумов;
2) неверно обрабатывается ситуация, когда один или несколько миниимумов не определены;
3) допущен выход за границу массива;
4) используется знак
Не выполнены условия, позволяющие поставить 3 или 4 балла. Программа работает в целом верно, эффективно или нет, но, в реализации алгоритма есть до двух содержательных ошибок, допустимые виды ошибок перечислены в критериях на 3 балла. Количество синтаксических описок не должно быть более девяти. Программа может быть неэффективна по времени. Например, все числа запоминаются в массиве и перебираются все возможные пары элементов последовательности:
min := 2001;
for i := 1 to N - 1 do begin
for j := i + 1 to N do begin
if ((a[i]+a[j]) mod 2 = 1) and
(a[i]+a[j]
Не выполнены условия, позволяющие поставить 2, 3 или 4 балла. Из описания алгоритма или общей структуры программы видно, что экзаменуемый в целом правильно представляет путь решения задачи независимо от эффективности. При этом программа может отсутствовать или быть представленной отдельными фрагментами, без ограничений на количество ошибок. | 1
Не выполнены критерии, позволяющие поставить 1, 2, 3 или 4 балла | 0
Максимальный балл | 4
Пояснения для проверяющих.
1. Задание Б является усложнением задания А. Если в качестве решения задания Б представлено решение задания А, то согласно приведённым ниже критериям, его оценка будет такой же, как если бы это решение было представлено в качестве решения задания А.
2. Два задания и, соответственно, возможность для экзаменуемого представить две программы дают ученику возможность (при его желании) сначала написать менее сложное и менее эффективное решение (задание А), которое даёт ему право получить два балла, а затем приступить к поиску более эффективного решения.
3. Каждая из программ, представленных экзаменуемым (но не более двух), оценивается по нижеследующим критериям. В качестве итоговой оценки берётся наибольшая из двух оценок.
Критерии оценивания выполнения задания | Баллы
Программа правильно работает для любых входных данных произвольного размера. Используемая память не зависит от количества прочитанных чисел, а время работы пропорционально этому количеству.
Допускается наличие в тексте программы до трех синтаксических ошибок одного из следующих видов:
1) пропущен или неверно указан знак пунктуации;
2) неверно написано или пропущено зарезервированное слово языка программирования;
3) не описана или неверно описана переменная;
4) применяется операция, недопустимая для соответствующего типа данных.
Если одна и та же ошибка встречается несколько раз, это считается за одну ошибку. | 4
Не выполнены условия, позволяющие поставить 4 балла. Программа в целом работает правильно для любых входных данных произвольного размера. Время работы пропорционально количеству введённых чисел, правильно указано, какие величины должны вычисляться по ходу чтения элементов последовательности чисел.
Количество синтаксических ошибок (описок) указанных выше видов — не более пяти.
Используемая память, возможно, зависит от количества прочитанных чисел (например, входные данные запоминаются в массиве или другой структуре данных (контейнер priority_queue, vector, set или map в С++)).
Допускается ошибка при вводе данных, неверный или неполный вывод результатов или неверная работа программы
в «экзотических» ситуациях. Кроме того, допускается наличие одной ошибки, принадлежащей к одному из следующих видов ошибок:
1) ошибка при инициализации минимумов;
2) неверно обрабатывается ситуация, когда один или несколько миниимумов не определены;
3) допущен выход за границу массива;
4) используется знак
Не выполнены условия, позволяющие поставить 3 или 4 балла. Программа работает в целом верно, эффективно или нет, но, в реализации алгоритма есть до двух содержательных ошибок, допустимые виды ошибок перечислены в критериях на 3 балла. Количество синтаксических описок не должно быть более девяти. Программа может быть неэффективна по времени. Например, все числа запоминаются в массиве и перебираются все возможные пары элементов последовательности:
min := 2001;
for i := 1 to N - 1 do begin
for j := i + 1 to N do begin
if ((a[i]+a[j]) mod 2 = 1) and
(a[i]+a[j]
Не выполнены условия, позволяющие поставить 2, 3 или 4 балла. Из описания алгоритма или общей структуры программы видно, что экзаменуемый в целом правильно представляет путь решения задачи независимо от эффективности. При этом программа может отсутствовать или быть представленной отдельными фрагментами, без ограничений на количество ошибок. | 1
Не выполнены критерии, позволяющие поставить 1, 2, 3 или 4 балла | 0
Максимальный балл | 4
🔗 Другие задания линии №27 по предмету Информатика:
ID 34669
Имеется набор данных, состоящий из пар положительных целых чисел. Необходимо выбрать из каждой ...
ID 34670
Последовательность натуральных чисел характеризуется числом Х — наибольшим числом, кратным 14 ...
ID 34671
На вход программы поступает последовательность из N целых положительных чисел. Рассматриваются ...
ID 34672
Дана последовательность N целых положительных чисел. Рассматриваются все пары элементов последо...
ID 34673
На вход программы поступает последовательность из N натуральных чисел. Рассматриваются все пары...