Чтобы купить курс,
пожалуйста, войдите
или зарегистрируйтесь
Вход/Регистрация Быстрый заказ
Быстрая регистрация
Информатика (Вариант 2)
Купить видеоуроки |
Приобретите наш курс
Для продолжения просмотра купите полный курс
наших видеоуроков
На вход программы поступает последовательность из N целых положительных чисел, все числа в последовательности различны. Рассматриваются все пары различных элементов последовательности, находящихся на расстоянии не меньше чем 4 (разница в индексах элементов пары должна быть 4 или более, порядок элементов в паре неважен). Необходимо определить количество таких пар, для которых произведение элементов делится на 29.
Описание входных и выходных данных
В первой строке входных данных задаётся количество чисел N (4 ≤ N ≤ 1000). В каждой из последующих N строк записано одно целое положительное число, не превышающее 10 000.
В качестве результата программа должна вывести одно число: количество пар элементов, находящихся в последовательности на расстоянии не меньше чем 4, в которых произведение элементов кратно 29.
Пример входных данных:
7
58
2
3
5
4
1
29
Пример выходных данных для приведённого выше примера входных данных:
5
Пояснение. Из 7 заданных элементов с учётом допустимых расстояний между ними можно составить 6 произведений: 58 · 4, 58 · 1, 58 · 29, 2 · 1, 2 · 29, 3 · 29. Из них на 29 делятся 5 произведений.
Требуется написать эффективную по времени и по памяти программу для решения описанной задачи.
Программа считается эффективной по времени, если при увеличении количества исходных чисел N в k раз время работы программы увеличивается не более чем в k раз.
Программа считается эффективной по памяти, если память, необходимая для хранения всех переменных программы, не превышает 1 Кбайт и не увеличивается с ростом N.
Максимальная оценка за правильную (не содержащую синтаксических ошибок и дающую правильный ответ при любых допустимых входных данных) программу, эффективную по времени и по памяти, – 4 балла.
Максимальная оценка за правильную программу, эффективную только по времени – 3 балла.
Максимальная оценка за правильную программу, не удовлетворяющую требованиям эффективности, – 2 балла.
Вы можете сдать одну программу или две программы решения задачи (например, одна из программ может быть менее эффективна). Если Вы сдадите две программы, то каждая из них будет оцениваться независимо от другой, итоговой станет бо́льшая из двух оценок.
Перед текстом программы обязательно кратко опишите алгоритм решения. Укажите использованный язык программирования и его версию.
Источник: 5splusom-school.ru
На вход программы поступает последовательность из N неотрицательных целых чисел, каждое из котор…
На вход программы поступает последовательность из N неотрицательных целых чисел, каждое из которых не больше 1000. Требуется определить, какая сумма цифр чаще всего встречается среди этих чисел. Если таких значений несколько, необходимо вывести наибольшее из них.
Входные данные:
На вход программе подаётся натуральное число N (N Пример входных данных:
3
13
22
32
Выходные данные:
Программа должна вывести наибольшую сумму цифр, которая чаще всего встречается среди введённых чисел.
Пример выходных данных для приведённого примера входных данных:
4
Два числа имеют сумму цифр 4.
Паскаль ABC
Виктория Карасенькова Вопрос задан 1 октября 2019 в 10 — 11 классы, true»> Поделиться
№27 КЕГЭ. Поиск макс пары, сумма которых кратна 120
27 задание ЕГЭ Информатика Определение количества троек
Источник: matfaq.ru
Систематизация решений задач по информатике (27 ЕГЭ)
В последние несколько лет выпускникам в условиях 27 задач предлагают обработать числовые последовательности. Для их успешного решения на 4 балла надо знать следующие правила:
1. Разность двух чисел кратна m, если остатки от деления этих чисел на m равны.
2. Произведение будет кратно m , если оба числа кратны m , или одно кратно m , а другое не кратно m .
3. Сумма двух чисел кратна k , если сумма остатков от деления этих чисел на k равна k .
Все задачи на обработку числовых последовательностей можно разбить на два вида:
I. рассмотреть все числа последовательности, удовлетворяющие определённым условиям
II. рассматривать числа, удовлетворяющие определённым условиям и при этом, отстоящие друг от друга на определённый интервал.
Задачи на 2 балла решаются обычным перебором и, как правило, не вызывают затруднений. На экзамене настоятельно рекомендуется записать решение на 2 балла, а потом – на 4. Баллы выставляются в пользу ученика. В таком случае, есть большая вероятность получения 2 баллов за 27 задачу, если оптимальное решение окажется неправильным. Рассмотрим конкретные задачи. Сначала на 2 балла (по одной на каждый случай)
Решение на 2 балла
I ) Без интервала На вход программы поступает последовательность из N (1≤ N ≤1000) целых, положительных чисел (все числа в последовательности различны). Рассматриваются все пары элементов последовательности. Необходимо определить количество пар, для которых произведение элементов кратно 62.
var N,i,j,count:integer; a:array[1..MAXN] of integer;
for i:=1 to N-1 do
for j:=i+1 to N do
if a[i]*a[j] mod 62 = 0 then count:=count+1;
II ) С интервалом Дана последовательность N целых положительных чисел. Рассматриваются все пары элементов последовательности, находящихся на расстоянии не меньше 6 (разница в индексах элементов должна быть 6 или более). Необходимо определить количество пар, сумма чисел в которых кратна 3.
Описание входных и выходных данных
В первой строке входных данных задаётся количество чисел N (6 ≤ N ≤ 1000). В каждой из последующих N строк записано одно натуральное число, не превышающее 10 000.
Пример входных данных:
Пример выходных данных для приведённого выше примера входных данных:
for i:=1 to N do readln(a[i]);
for i := 1 to N-d do begin
for j := i+d to N do begin
if (a[i] + a[j]) mod 3 = 0
Ещё несколько шаблонов на 2 балла
ЗАДАЧА НА НАИБОЛЬШУЮ СУММУ МЕЖДУ ЭЛЕМЕНТАМИ С РАССТОЯНИЕМ НЕ МЕНЕЕ 5
ЗАДАЧА НА ПОИСК КОЛИЧЕСТВА ПАР, ПРОИЗВЕДЕНИЕ МЕЖДУ ЭЛЕМЕНТАМИ КОТОРЫХ КРАТНО 6
ЗАДАЧА НА ПОИСК КОЛИЧЕСТВА ПАР МЕЖДУ ЭЛЕМЕНТАМИ ПРОИЗВЕДЕНИЕ КОТОРЫХ КРАТНО 14 И РАССТОЯНИЕ МЕЖДУ ЭЛЕМЕНТАМИ НЕ МЕНЕЕ 6
ЗАДАЧА НА ПОИСК ЭЛЕМЕНТОВ, СУММА КОТОРЫХ МАКСИМАЛЬНА, КРАТНА 60, ПРИ ЭТОМ i j , a [ i ]> a [ j ] И РАССТОЯНИЕ МЕЖДУ ЭЛЕМЕНТАМИ НЕ МЕНЕЕ 6
Решение на 4 балла
I ) Без интервала
1) (Произведение) На вход программы поступает последовательность из N (1≤ N ≤1000) целых, положительных чисел (все числа в последовательности различны). Рассматриваются все пары элементов последовательности. Необходимо определить количество пар, для которых произведение элементов кратно 62.
for i:=1 to N do begin
if x mod 62 =0 then k62:=k62+1
else if x mod 2 =0 then k2:=k2+1
else if x mod 31 =0 then k31:=k31+1
 |
2) (Сумма кратная 80) Дана последовательность N (2≤ N ≤10000) целых положительных чисел. Рассматриваются все пары элементов последовательности (числа не превышают 10000), сумма которых делится на m =80. Среди всех таких пар нужно найти и вывести пару с максимальным произведением элементов. Если одинаковое максимальное произведение имеют несколько пар, можно вывести любую из них. Если таких пар нет, нужно вывести два нуля.
Пример
8
10
30
50
40
60
70
90
80 Программа должна вывести 70 90. Из данных 8 чисел можно составить 3 пары, удовлетворяющие условию: (10, 70), (30,50), (70,90). Наибольшее произведение будет в паре (70,90).
const m=80;
var a:array[0..m-1]of integer; N,x,x1,x2,p,pp,max,i:integer;
begin
for i:=0 to m-1 do a[i]:=0;
x1:=0; x2:=0; max:=0;
readln(N);
for i:=1 to N do begin
p:=x mod m; pp:=(m-p) mod m;
if x*a[pp]>max then
if x>a[p] then a[p]:=x;
3) (Разность кратная 80) Дана последовательность N целых неповторяющихся положительных чисел. Рассматриваются все пары элементов последовательности, разность которых делится на m = 80. Среди всех таких пар нужно найти и вывести пару с максимальной разностью элементов. Если одинаковую максимальную разность имеют несколько пар, можно вывести любую из них. Если подходящих пар в последовательности нет, нужно вывести два нуля.
Описание входных и выходных данных
В первой строке входных данных задаётся количество чисел N (2 ≤ N ≤ 10 000). В каждой из последующих N строк записано одно натуральное число, не превышающее 10 000. Гарантируется, что никакое число не встречается в последовательности более одного раза.
Пример входных данных:
Пример выходных данных для приведённого выше примера входных данных:
Пояснение. Из данных восьми чисел можно составить три пары, удовлетворяющие условию: (15, 95), (3, 163), (5, 85). Наибольшая разность получается в паре (3, 163).
Разность двух чисел кратна m, если остатки от деления этих чисел на m равны. При этом для получения максимальной разности нужно, чтобы одно из чисел было как можно больше, а второе как можно меньше.
Будем хранить в одном массиве из m элементов максимальные числа, имеющие соответствующий остаток от деления на m, а в другом – минимальные, и из всех пар максимумов и минимумов выберем пару с наибольшей разностью.
При этом нужно убедиться, что это именно пара. Поскольку в условии гарантируется, что числа в последовательности не повторяются, если минимум оказался равен максимуму, значит, пары на самом деле нет.
var mn,mx:array[0..m-1]of integer;
x : integer ; //очередное число из последовательности
p : integer ; //остаток
pm : integer ; //остаток, дающий лучшую разность
for i:=0 to m-1 do
if (x > mx[p]) then mx[p]:= x;
if mx[p]-mn[p] > mx[pm]-mn[pm] then pm := p;
if mx[pm] = mn[pm] then writeln(‘0 0’)
else writeln(mn[pm], ‘ ‘, mx[pm]);
 |
4) (Максимальная сумма кратная 120) На вход программы поступает последовательность из N (1 ≤ N ≤ 12 000) положительных целых чисел. Рассматриваются все пары различных элементов последовательности (элементы пары не обязаны стоять в последовательности рядом). Найти пару элементов с максимальной суммой, кратной 120. Порядок элементов в паре соответствует порядку в последовательности и первый элемент в паре должен быть больше второго. Гарантируется, что такая пара есть.
var m:array[0..sk-1] of integer;
for i:=1 to sk-1 do m[i]:=-11111;
for i:=2 to n do begin
if (m[dk]>a) and (m[dk]+a>x+y) then
Пример входных данных
Выходные данные
II ) С интервалом
На вход программы поступает последовательность из N (4 ≤ N ≤ 10 000) целых положительных чисел (числа не превышают 10000), все числа в последовательности различны. Рассматриваются все пары различных элементов последовательности, находящиеся на расстоянии не меньше чем 4 (разница в индексах элементов пары должна быть 4 или более, порядок элементов в паре не важен). Необходимо определить количество пар, для которых произведение элементов делится на 13.
Пример входных данных:
7
26
2
3
5
4
1
13 Программа должна вывести 5
var i,j,n,k13,k,x,s:integer; a:array[1..4] of integer;
begin
readln(n);
for i:=1 to 4 do readln (a[i]);
k13:=0; k:=0; s:=0;
for i:=5 to n do begin
if a[1] mod 13=0 then k13:=k13+1
else k:=k+1;
readln(x);
if x mod 13=0 then s:=s+k+k13
else s:=s+k13;
for j:=1 to 3 do a[j]:=a[j+1];
a[4]:=x;
end;
writeln(s);
end.
В заключении ещё две задачи на числовые последовательности, но не на те правила, что перечислены выше
I Назовём длиной числа количество цифр в его десятичной записи. Например, длина числа 2017 равна 4, а длина числа 7 равна 1. Дан набор из N целых положительных чисел, каждое из которых меньше 10 8 . Необходимо определить, числа какой длины чаще всего встречаются в данном наборе и сколько в нём чисел этой длины. Если числа разной длины встречаются одинаково часто (и чаще чем числа любой другой длины), нужно выбрать большую длину.
Описание входных и выходных данных
В первой строке входных данных задаётся количество чисел N (1 ≤ N ≤ 1000). В каждой из последующих N строк записано одно натуральное число, меньшее, чем 10 8 . Пример входных данных:
Пример выходных данных для приведённого выше примера входных данных:
В данном наборе чаще всего (по 2 раза) встречаются числа длины 2 и 3. Выбираем большую длину, выводим саму длину (3) и количество чисел этой длины (2).
При заданных ограничениях числа в наборе могут иметь длину от 1 до 8. Необходимо создать массив из 8 элементов с индексами от 1 до 8 и использовать его для подсчёта количества чисел соответствующей длины. Использование массива не делает программу неэффективной по памяти, так как размер массива не зависит от N. Затем нужно найти значение максимального элемента этого массива и вывести максимальный из индексов элементов, равных этому максимуму и сам максимум. Пример правильной и эффективной программы на языке Паскаль
d: array[1..8] of integer;
for i:=1 to 8 do d[i]:=0;
Источник: znanio.ru