1 Ответ
1. В терминологии сетей TCP/IP маской сети называется двоичное число, определяющее, какая часть IP-адреса узла сети относится к адресу сети, а какая – к адресу самого узла в этой сети. При этом в маске сначала (в старших разрядах) стоят единицы, а затем с некоторого места – нули.
Адрес сети получается в результате применения поразрядной конъюнкции к заданному IP-адресу узла и маске. Например, если IP-адрес узла равен 231.32.255.131, а маска равна 255.255.240.0, то адрес сети равен 231.32.240.0. Узлы с IP-адресами 157.220.185.237 и 157.220.184.230 принадлежат одной
сети. Какое наименьшее количество IP-адресов, в двоичной записи которых ровно 15 единиц, может содержаться в этой сети?
Ответ: 9
2. Значение арифметического выражения
4·72^4 + 6·7^13 + 5·49^4 + 2·343^2 + 10 – x, где x – натуральное число, записали в системе счисления с основанием 7. Определите наименьшее значение x, при котором в этой записи шестёрок будет больше, чем нулей. В ответе запишите найденное значение x в десятичной системе счисления.
Ответ: 29 059 314
3. На числовой прямой даны три отрезка:
P = [153697; 780411], Q = [275071; 904082], R = [722050; 984086].
Укажите наименьшую возможную длину такого отрезка A, для которого логическое выражение
(¬(x ∈ A)) → (((x ∈ P) ≡ (x ∈ Q)) → ((x ∈ R) ≡ (x ∈ Q))) истинно (т.е. принимает значение 1) при любом значении переменной x.
Ответ: 709015
4. Функция F(n), где n – натуральное число, задана следующими соотношениями:
F(n) = F(n/2) + 3, если n чётно;
F(n) = F(n/3) + 2, если n нечётно и при этом кратно 3;
F(n) = 0, если n нечётно и не кратно 3.
Определите минимальное значение n, для которого F(n) = 70.
Ответ: 37 748 736
5. Файл содержит последовательность натуральных чисел, не превышающих 100 000. Назовём тройкой три идущих подряд элемента последовательности. Определите количество троек, для которых выполняются следующие условия:
– остаток от деления на 3 ровно одного числа из тройки равен остатку от деления на 3 минимального элемента всей последовательности;
– остаток от деления на 7 хотя бы двух чисел из тройки равен остатку от деления на 7 максимального элемента всей последовательности.
В ответе запишите два числа: сначала количество найденных троек, затем максимальную величину суммы элементов этих троек.
Ответ: 228,262713
6. Робот стоит в левом верхнем углу прямоугольного поля, в каждой клетке которого записано целое число, обозначающее выраженную в условных единицах высоту местности в данной клетке.
За один ход робот может переместиться на одну клетку вправо или на одну клетку вниз, но только при условии, что при этом переходе он поднимается или опускается не более чем на 50 условных единиц.
Задание 1. Определите количество различных маршрутов из исходной точки в правый нижний угол поля.
Задание 2. Определите количество клеток поля, недоступных для робота из-за ограничения на допустимый перепад высот. Исходные данные записаны в электронной таблице. В ответе запишите два
числа: сначала ответ на задание 1, затем ответ на задание 2.
Ответ: 255632,119
7. Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может выполнить любое из следующих действий:
1) убрать из кучи пять камней;
2) если количество камней в куче чётно, уменьшить его в два раза;
3) если количество камней в куче кратно трём, уменьшить его в три раза;
4) если количество камней в куче нечётно и не кратно трём, добавить один камень.
Например, если в куче 12 камней, то за один ход можно получить 7, 6 или 4 камня, а если в куче 11 камней, то за один ход можно получить 6 или 12 камней. Игра завершается, когда количество камней в куче становится не более 19. Победителем считается игрок, сделавший последний ход, то есть первым
получивший кучу, в которой будет 19 или меньше камней. В начале игры в куче было S камней, S > 19.
Укажите минимальное значение S, при котором Петя не может выиграть первым ходом, но при любом первом ходе Пети Ваня может выиграть своим первым ходом.
Ответ: 25
8. Для игры, описанной в задании 19, найдите два наименьших значения S, при которых Петя не может выиграть первым ходом, но у Пети есть выигрышная стратегия, позволяющая ему выиграть вторым ходом при любой игре Вани. В ответе запишите найденные значения в порядке возрастания.
Ответ: 40,43
9. Для игры, описанной в задании 19, найдите минимальное значение S, при котором у Вани есть стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети, но у Вани нет стратегии, которая позволила бы ему гарантированно выиграть первым ходом.
Ответ: 60
10. В таблице представлены идентификатор (ID) каждого процесса, его длительность в мс и ID поставщиков данных для зависимых процессов. Для независимых процессов в качестве ID поставщика данных указан 0.
Одновременно может выполняться не более 4 процессов. Если в какой-то момент в системе работает менее 4 процессов, то при наличии готовых к запуску процессов выбирается и запускается тот из них, который имеет минимальный ID.
За какое время будут выполнены все процессы?
В ответе напишите число – требуемое время в мс.
Ответ: 43
11. Исполнитель преобразует число на экране.
У исполнителя есть две команды, которые обозначены буквами:
A. Вычти 3
B. Если число чётное, Раздели на 2, Иначе Вычти 5 Программа для исполнителя – это последовательность команд. Сколько существует программ, которые преобразуют исходное число 36 в число 3 и при этом траектория вычислений не содержит числа 12?
Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы BAB при исходном числе 100 траектория будет состоять из чисел 50, 47, 42.
Ответ: 16
12. Текстовый файл состоит из цифр от 1 до 9, знаков операций «+», «–» и «*»
(сложение, вычитание и умножение) и заглавных латинских букв A, B, C, D.
Назовём правильной суммой строку, содержащую последовательность из одного или более десятичных чисел, в которой между соседними числами стоит ровно один знак «+» и нет других знаков.
Примеры правильных сумм: «23», «115+6», «1980+12+12351». Назовём результатом правильной суммы число, которое получится при выполнении записанных в соответствующей строке сложений. Например,
результат правильной суммы «2+3» – число 5. Найдите в данной строке правильную сумму, расположенную непосредственно после буквы A и имеющую наибольший результат.
В ответе запишите результат найденной суммы. Гарантируется, что ответ не превышает 2·109.
Ответ: 67 622 777
13. Маска числа – это последовательность цифр, в которой могут встречаться специальные символы «?» и «*». Символ «?» означает ровно одну произвольную цифру, символ «*» означает произвольную (в том числе
пустую) последовательность цифр.
Например, маске 123*4?5 соответствуют числа 123405 и 12376415.
Найдите все натуральные числа, принадлежащие интервалу [108; 2·108], которые соответствуют маске ?*42*81 и имеют ровно три натуральных делителя. В ответе запишите все найденные числа в порядке возрастания.
Ответ: 114 297 481; 141 824 281; 142 587 481; 149 842 081
14. Участники викторины письменно отвечают на 10 вопросов различной сложности. За правильный ответ начисляется от 1 до 5 баллов в зависимости от сложности вопроса. За неверный ответ вычитается от 1 до 5 баллов. Участник может не отвечать на какой-то вопрос, в таком случае баллы за этот вопрос не начисляются.
Входные данные
Первая строка входного файла содержит целое число N (N ≤ 10 000) – общее количество участников. Каждая из следующих N строк соответствует одному участнику и содержит 11 целых чисел, разделённых пробелами: сначала ID участника, затем – баллы, полученные им за каждый из 10 вопросов.
Гарантируется, что ID участников не повторяются. В ответе запишите два целых числа: сначала требуемый ID, затем требуемое количество.
Ответ: 35669,478
15. Вам даны два входных файла (A и B), каждый из которых имеет описанную выше структуру. По данным каждого из представленных файлов определите средний радиус по описанным выше правилам.
В ответе запишите два числа: сначала средний радиус для файла A, затем для файла B.
В качестве значения указывайте целую часть от умножения найденного числового значения на 10 000.
Ответ: 10001, 8504