Контроль пройден (или Контроль не пройден)

Задача А (2 балла).Напишите на любом языке программирования программу для решения поставленной задачи, в которой входные данные будут запоминаться

в массиве, после чего будут проверены все возможные пары элементов.

Задача Б (4 балла).Напишите программу для решения поставленной задачи, которая будет эффективна как по времени, так и по памяти (или хотя бы по одной из этих

характеристик).

На вход программе в первой строке подаётся количество чисел N (2 < N £ 10000). В каждой из последующих N строк записано одно натуральное число, не превышающее 1000. В последней строке записано контрольное значение.

Пример входных данных:

6

100

8

33

145

19

84

153

Пример выходных данных для приведённого выше примера входных данных:

Вычисленное контрольное значение: 153

Контроль пройден

62) По каналу связи передастся последовательность слов в алфавите {А, Е, Р}. Длина каждого слова не превосходит 10 букв, слова могут не быть осмысленными словами русского языка. Каждое слово передается в виде целого числа, полученного следующим образом.

1) Сначала слово колируется с помощью неравномерного двоичного кода с кодовыми словами: Е – 0; Р – 10; А – 11.

2) К полученной двоичной последовательностисправа приписывается цифра 1.

3) Полученная двоичная цепочка переворачивается, то есть, из цепочки 01010111 получается 11101010.

4) Искомое число N вычисляется в результате перевода двоичной цепочки, полученной на предыдущем шаге, в десятичную систему.

Например, символьная последовательность ААЕЕР будет преобразована в 11110010, затем (добавляем единицу в конец) – в 111100101, а затем – в число: 1 + 2 + 4 + 8 + 64 + 256 = 335. Отметим, что 335 = 101001111₂.

Напишите программу, которая, получив на вход натуральное число, декодирует переданное сообщение и определяет, сколько раз в исходном слове встречаются гласные буквы. Считается, что входное число может быть представлено в виде значения целого типа в используемом языке программирования.

Пример входных данных:

5483

Пример выходных данных:

АЕРАЕРР

4

Примечание. В этом примере: исходное слово: АЕРАЕРР. Кодовая двоичная последовательность: 110101101010, после добавления 1 справа получим: 1101011010101.

63) На спутнике «Восход» установлен прибор, предназначенный для измерения солнечной активности. Каждую минуту прибор передаёт по каналу связи неотрицательное целое число – количество энергии солнечного излучения, полученной за последнюю минуту, измеренное в условных единицах. Временем, в течение которого происходит передача, можно пренебречь. Необходимо найти в заданной серии показаний прибора максимальное чётное произведение двух показаний, между моментами передачи которых прошло не менее 9 минут. Если получить такое произведение не удаётся, ответ считается равным –1. Количество энергии, получаемое прибором за минуту, не превышает 1000 условных единиц. Общее количество показаний прибора в серии не превышает 10 000.

Задача А (2 балла).Напишите на любом языке программирования программу для решения поставленной задачи, в которой входные данные будут запоминаться

в массиве, после чего будут проверены все возможные пары элементов.

Задача Б (4 балла).Напишите программу для решения поставленной задачи, которая будет эффективна как по времени, так и по памяти (или хотя бы по одной из этих

характеристик).

Входные данные представлены следующим образом. В первой строке задаётся число N – общее количество показаний прибора. Гарантируется, что N > 9. В каждой из следующих N строк задаётся одно неотрицательное целое число – очередное показание прибора.

Пример входных данных:

11

12

45

5

3

17

23

21

20

19

12

26

Программа должна вывести одно число – описанное в условии произведение.

Пример выходных данных для приведённого выше примера входных данных:

1170

64)На спутнике «Восход» установлен прибор, предназначенный для измерения солнечной активности. В течение времени эксперимента (это время известно заранее) прибор каждую минуту передаёт в обсерваторию по каналу связи положительное целое число, не превышающее 1000, - количество энергии солнечного излучения, полученной за последнюю минуту, измеренное в условных единицах.

После окончания эксперимента передаётся контрольное значение наибольшее число R, удовлетворяющее следующим условиям:

1. R – произведение двух различных переданных элементов последовательности («различные» означает, что не рассматриваются квадраты переданных чисел, произведения различных, но равных по величине элементов допускаются);

2. R не делится на 26.

В результате помех при передаче как сами числа, так и контрольное значение могут быть искажены.
Напишите эффективную по времени и используемой памяти программу, которая будет проверять правильность контрольного значения. Программа должна напечатать отчёт по следующей форме.

Вычисленное контрольное значение: ...

Контроль пройден (или Контроль не пройден)

Если удовлетворяющее условию контрольное значение определить невозможно, то выводится только фраза «Контроль не пройден».

Перед текстом программы кратко опишите используемый Вами алгоритм решения.
На вход программе в первой строке подаётся количество чисел N. В каждой из последующих N строк записано одно положительное целое число, не превышающее 1000. В последней строке записано контрольное значение.

Пример входных данных:

5
52
12
39
55
23
2145

Пример выходных данных для приведённого выше примера входных данных:

Вычисленное контрольное значение: 2145

Контроль пройден

Начало формы

Конец формы

65) Задание А. Имеется набор данных, состоящий из 6 пар положительных целых чисел. Необходимо выбрать из каждой пары ровно одно число так, чтобы сумма всех выбранных чисел не делилась на 4 и при этом была максимально возможной. Если получить требуемую сумму невозможно, в качестве ответа нужно выдать 0. В этом варианте задания оценивается только правильность программы, время работы и размер использованной памяти не имеют значения.

Задание Б. Имеется набор данных, состоящий из пар положительных целых чисел. Необходимо выбрать из каждой пары ровно одно число так, чтобы сумма всех выбранных чисел не делилась на 4 и при этом была максимально возможной. Если получить требуемую сумму невозможно, в качестве ответа нужно выдать 0.

Программа считается эффективной по времени, если время работы программы пропорционально количеству пар чисел N, т.е. при увеличении N в k раз время работы программы должно увеличиваться не более чем в k раз. Программа считается эффективной по памяти, если размер памяти, использованной в программе для хранения данных, не зависит от числа N и не превышает 1 килобайта.

Входные данные:

Для варианта А на вход программе подаётся 6 строк, каждая из которых содержит два натуральных числа, не превышающих 10000.

Пример входных данных для варианта А:

1 3

5 12

6 8

5 4

3 3

1 1

Для варианта Б на вход программе в первой строке подаётся количество пар N (1 £ N £ 100000). Каждая из следующих N строк содержит два натуральных числа, не превышающих 10 000.

Пример входных данных для варианта Б:

6

1 3

5 12

6 8

5 4

3 3

1 1

Пример выходных данных для приведённых выше примеров входных данных:

31

66) На вход программы поступает последовательность из N натуральных чисел. Нужно выбрать из них произвольное количество чисел так, чтобы их сумма была максимальной и не делилась на 4. В результате программа должна вывести количество выбранных чисел и их сумму. Если получить требуемую сумму невозможно, в качестве ответа нужно выдать 0.

Входные данные:

На вход программе подаётся натуральное число N (N £ 1000), а затем N натуральных чисел, каждое из которых не превышает 10000.

Пример входных данных:

3

1

2

1

Выходные данные:

Программа должна вывести два числа: сначала количество выбранных чисел, а затем их сумму.

Пример выходных данных для приведённого примера входных данных:

2 3

67) На вход программы поступает последовательность из N натуральных чисел. Требуется определить, какая цифра чаще всего встречается в десятичной записи этих чисел. Если таких цифр несколько, необходимо вывести их все в порядке убывания – от большей к меньшей.

Входные данные:

На вход программе подаётся натуральное число N (N £ 1000), а затем N натуральных чисел, каждое из которых не превышает 10000.

Пример входных данных:

3

13

214

32

Выходные данные:

Программа должна вывести цифры, которые встречаются в последовательности наибольшее число раз, в порядке убывания.

Пример выходных данных для приведённого примера входных данных:

3 2 1

(цифры 3, 2 и 1 встречаются по 2 раза).

68) На вход программы поступает последовательность из N натуральных чисел. Требуется определить, с какой цифры реже всего (но, по крайней мере, один раз) начинается десятичная запись этих чисел. Если таких цифр несколько, необходимо вывести наименьшую из них.

Входные данные:

На вход программе подаётся натуральное число N (N £ 1000), а затем N натуральных чисел, каждое из которых не превышает 10000.

Пример входных данных:

3

13

214

32

Выходные данные:

Программа должна вывести одну (минимальную) цифру, с которой реже всего начинаются введённые числа.

Пример выходных данных для приведённого примера входных данных:

1

69) На вход программы поступает последовательность из N неотрицательных целых чисел, каждое из которых не больше 1000. Требуется определить, какая сумма цифр чаще всего встречается среди этих чисел. Если таких значений несколько, необходимо вывести наибольшее из них.

Входные данные:

На вход программе подаётся натуральное число N (N £ 1000), а затем N натуральных чисел, каждое из которых не превышает 1000.

Пример входных данных:

3

13

22

32

Выходные данные:

Программа должна вывести наибольшую сумму цифр, которая чаще всего встречается среди введённых чисел.

Пример выходных данных для приведённого примера входных данных:

4

Два числа имеют сумму цифр 4.

70) На вход программы поступает последовательность из N натуральных чисел, каждое из которых не больше 1000. Требуется вывести цифры, встречающиеся в эти числах, в порядке неубывания частоты их появления. Если какие-то цифры встречаются одинаковое число раз, они выводятся в порядке убывания.

Входные данные:

На вход программе подаётся натуральное число N (N £ 1000), а затем N натуральных чисел, каждое из которых не превышает 10000.

Пример входных данных:

3

456

20

3452

Пример выходных данных для приведённого примера входных данных:

6 3 0 5 4 2

71) На вход программы поступает последовательность из N натуральных целых чисел, каждое из которых не больше 1000. Требуется определить, можно ли записать все значащие цифры шестнадцатеричной записи этих чисел так, чтобы полученная строка было симметричной (читалась одинаково как слева направо, так и справа налево). Если требуемую строку составить невозможно, то программа должна вывести на экран число 0, а если возможно, то вывести число 1.

Входные данные:

На вход программе подаётся натуральное число N (N £ 1000), а затем N натуральных чисел, каждое из которых не превышает 10000.

Пример входных данных:

3

13

22

32

Пример выходных данных для приведённого примера входных данных:

0

Из цифр D, 1, 6, 2, 0 нельзя составить симметричную строку.

Пример входных данных:

4

186

68

171

14

Пример выходных данных для приведённого примера входных данных:

1

Из цифр A, B, 4, 4, A, B, D можно составить симметричную строку.

72) Имеется набор данных, состоящий из пар положительных целых чисел. Для каждой пары чисел находится значение А – наибольший общий делитель. Напишите эффективную по времени работы и по используемой памяти программу, которая будет определять, какое значение А встречалось чаще всего. Если несколько значений А встречалось одинаковое наибольшее количество раз, вывести их в порядке убывания.

Программа считается эффективной по времени, если время работы программы пропорционально количеству пар чисел N, т. е. при увеличении N в k раз время работы программы должно увеличиваться не более чем в k раз. Программа считается эффективной по памяти, если размер памяти, использованной в программе для хранения данных, не зависит от числа N и не превышает 100 килобайт.

Входные данные:

На вход программе в первой строке подаётся количество пар N (1 £ N £ 100000). Каждая из следующих N строк содержит два натуральных числа, не превышающих 1000.

Пример входных данных:

6

1 3

5 15 

6 9 

5 4 

3 3 

36 40 

Пример выходных данных для приведённого примера входных данных:

3 1

73) Имеется набор данных, состоящий из троек натуральных чисел. Необходимо выбрать из каждой тройки ровно одно число так, чтобы сумма всех выбранных чисел не была кратна 4 и при этом была максимально возможной. Если получить требуемую сумму невозможно, в качестве ответа нужно выдать 0. Напишите эффективную программу, решающую поставленную задачу.

Входные данные:

На вход программе в первой строке подаётся количество троек N (1 £ N £ 100000). Каждая из следующих N строк содержит три натуральных числа, не превышающих 10 000.

Пример входных данных:

6

1 3 2

5 12 12

6 8 12

5 4 12

3 3 12

1 1 13

Пример выходных данных для приведённого примера входных данных:

63

74) Имеется набор данных, состоящий из троек натуральных чисел. Необходимо выбрать из каждой тройки два числа так, чтобы сумма всех выбранных чисел была кратна 4 и при этом была максимально возможной. Если получить требуемую сумму невозможно, в качестве ответа нужно выдать 0.

Входные данные:

На вход программе в первой строке подаётся количество троек N (1 £ N £ 100000). Каждая из следующих N строк содержит три натуральных числа, не превышающих 10 000.

6

8 3 4

4 8 12

9 5 6

2 8 3

12 3 5

1 4 12

Пример выходных данных для приведённого примера входных данных:

88

75) Дан набор из N натуральных чисел. Необходимо определить количество пар элементов (a_i, a_j) этого набора, в которых 1 £ i < j £ N и произведение элементов кратно 6. Напишите эффективную по времени и по памяти программу для решения этой задачи.