Вариант к2
Задание 1
На рисунке справа схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах). Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите длину дороги между пунктами Г и Д. Передвигаться можно только по указанным дорогам.
Задание 2
Логическая функция F задаётся выражением (x ∧ y) ∨ (y ≡ z) ∨ w. Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных x, y, z, w.
В ответе напишите буквы x, y, z, w в том порядке, в котором идут соответствующие им столбцы.
Задание 3
В фрагменте базы данных представлены сведения о родственных отношениях. На основании приведенных данных определите, сколько прямых потомков (то есть детей и внуков) Кривич Л.П. упомянуто в таблице.
Задание 4
Для кодирования некоторой последовательности, состоящей из букв Л, М, Н, П, Р, решили использовать неравномерный двоичный код, удовлетворяющий условию, что никакое кодовое слово не является началом другого кодового слова. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Для букв Л, М, Н использовали соответственно кодовые слова 00, 01, 11. Для двух оставшихся букв – П и Р – кодовые слова неизвестны. Укажите кратчайшее возможное кодовое слово для буквы П, при котором код будет удовлетворять указанному условию. Если таких кодов несколько, укажите код с наименьшим числовым значением.
Задание 5 (№612).
Автомат обрабатывает натуральное число N по следующему алгоритму.
1 Строится двоичная запись числа N.
2 Удаляется первая слева единица и все следующие непосредственно за ней нули. Если после этого в числе не остаётся цифр, результат этого действия считается равным нулю.
3 Полученное число переводится в десятичную запись.
4 Новое число вычитается из исходного, полученная разность выводится на экран.
Пример. Дано число N = 11 Алгоритм работает следующим образом.
1 Двоичная запись числа N: 1011
2 Удаляется первая единица и следующий за ней ноль: 11
3 Десятичное значение полученного числа 3
4 На экран выводится число 11 – 3 = 8
Сколько разных значений будет показано на экране автомата при последовательном вводе всех натуральных чисел от 10 до 1000?
Задание 6 (№820).
Определите, при каком наибольшем введённом значении переменной S программа выведет число 32?
Задание 7 (№166).
Стереоаудиофайл передается со скоростью 32000 бит/с. Файл был записан с такими параметрами: глубина кодирования – 16 бит на отсчет, частота дискретизации – 48000 отсчетов в секунду, время записи – 90 с. Сколько минут будет передаваться файл?
Задание 8
Сколько слов длины 5, начинающихся с согласной буквы и заканчивающихся гласной буквой, можно составить из букв К, У, М, А? Каждая буква может входить в слово несколько раз. Слова не обязательно должны быть осмысленными словами русского языка.
Задание 9
Откройте файл электронной таблицы, содержащей вещественные числа – ведомость продуктового магазина. Наценкой товара считается разность между закупочной ценой и ценой реализации. Прибыль – количество проданных товаров, умноженное на значение наценки. Найдите товар с наценкой выше среднего значения, который принесет максимальную прибыль после его полной продажи. В качестве ответа укажите одно число – полученную после продажи найденного товара прибыль.
Задание 10 (№478).
С помощью текстового редактора определите, сколько раз, не считая сносок, встречается слово «портрет» или «Портрет» в тексте романа в стихах А.С. Пушкина «Евгений Онегин». Другие формы слова «портрет», такие как «портреты», «портретами» и т.д., учитывать не следует. В ответе укажите только число.
Задание 11 (№371).
При регистрации в компьютерной системе каждому пользователю выдаётся пароль, состоящий из 15 символов, содержащий только строчные и заглавные буквы латинского алфавита и десятичные цифры. В базе данных для хранения сведений о каждом пользователе отведено одинаковое и минимально возможное целое число байт. При этом используют посимвольное кодирование паролей, все символы кодируют одинаковым и минимально возможным количеством бит. Кроме собственно пароля, для каждого пользователя в системе хранятся дополнительные сведения.
Для хранения сведений о 17 пользователях потребовалось 255 байт.
Какой объем памяти выделен для хранения дополнительных сведений? В ответе запишите только целое число – количество бит.
Примечание: в латинском алфавите 26 букв.
Задание 12
Сколько клеток лабиринта соответствуют требованию, что, начав движение в ней и выполнив предложенную программу, РОБОТ уцелеет и остановится в закрашенной клетке (клетка F1)?
Задание 13
На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?
Задание 14
Определите число N, для которого выполняется равенство 103N = 97N+2.
Задание 15
Элементами множества А являются натуральные числа. Известно, что выражение
( x ∈ {1, 2, 4, 8, 16}) ∧ ( x ∈ {3, 4, 9, 16}) ∨ ( x ∈ A)
истинно (т. е. принимает значение 1) при любом значении переменной х. Определите наименьшее возможное количество элементов множества A.
Задание 16 (№598).
Алгоритм вычисления функции F(n) задан следующими соотношениями:
F(n) = 1 при n ≤ 1;
F(n) = n · F(n – 1) при чётных n > 1;
F(n) = n + F(n – 2) при нечётных n > 1;
Определите значение F(84).
Задание 17 (№806).
Рассматривается множество целых чисел, принадлежащих числовому отрезку [3089; 9715], которые не делятся нацело на 7, 8, 9, 13 и являются четными.Найдите количество таких чисел и максимальное из них.
Для выполнения этого задания можно написать программу или воспользоваться редактором электронных таблиц.
Задание 18
Дана последовательность вещественных чисел. Из неё необходимо выбрать несколько подряд идущих чисел так, чтобы каждое следующее число было больше предыдущего. Какую максимальную сумму могут иметь выбранные числа?
Пример входных данных:
Для указанных входных данных ответом должно быть число 20 – максимальная сумма элементов возрастающей последовательности. В ответе укажите только целую часть числа.
Задание 19 (№502).
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит две кучи камней. Первый ход делает Петя, игроки ходят по очереди один за другим. Игрок может либо увеличить количество камней в любой из куч на 3, либо увеличить количество вдвое. Игра завершается, когда хотя бы в одной из куч количество камней становится не менее 21.
Обозначим, как (х, у) игровую позицию, когда в первой куче х камней, во второй – у. Количество камней в обоих кучах в начале игры положительное.
Так, если игрок делает ход из позиции (3, 6), то он может получить одну из трех позиций (6, 6), (3, 9), (3, 12).
Известно, что игра началась из позиции (5, S). Найдите все значения S, при которых у Пети есть выигрышная стратегия в два хода.
В качестве ответа укажите наименьшее и наибольшее значения S.
Задание 20.
Для условия игры из задания 19, ответьте на вопрос.
Известно, что в начале игры в первой куче было 4 камня. Укажите минимальное количество камней во второй куче, если известно, что в таком случае Ваня имеет выигрышную стратегию в два или три хода.
Задание 21.
Для условия игры из задания 19, ответьте на вопрос.
Известно, что Петя имеет выигрышную стратегию при игре из позиции (3, S). Найдите все возможные значения S, если известно. Что Петя не может выиграть своим первым ходом? Запишите найденные значения в порядке возрастания без разделителей.
Пример: значения S 5, 8, 9 запишутся как 589.
Задание 22
Получив на вход число x, этот алгоритм печатает число M. Известно, что x > 100. Укажите наименьшее такое (т. е. большее 100) число x, при вводе которого алгоритм печатает 9.
Задание 23
Исполнитель преобразует число на экране. У исполнителя есть две команды, которым присвоены номера:
Прибавить 1
Прибавить следующее нечетное
Умножить на 2
Сколько существует программ, для которых при исходном числе 3 результатом является число 75 и при этом траектория вычислений содержит число 25?
Задание 24
Текстовый файл состоит из не более, чем 1000 строк, каждая из которых состоит не более чем из 106 символов A, B, C. Найдите количество строк, где количество букв B не менее, чем на 5% больше количества букв A. В качестве ответа приведите количество найденных строк.
Для выполнения этого задания следует написать программу.
Примечание: символы в латинице или в английской раскладке
Задание 25 (№953).
Пусть S - сумма различных натуральных делителей целого числа, являющихся простыми числами, не считая самого числа.
Напишите программу, которая перебирает целые числа, меньшие 500 000, в порядке убывания и ищет среди них такие, для которых значение S не равно нулю и делится на 10. Программа должна найти и вывести первые 7 таких чисел и соответствующие им значения S.
формат вывода: для каждого из 7 таких найденных чисел в отдельной строке сначала выводится само число, затем значение S. Строки выводятся в порядке убывания найденных чисел.
Например, для числа 20 S = 2 + 5 =7
Задание 26
Каждый день Петр ест некоторое количество конфет. Так как Петр любит фантики от конфет, то он каждый такой фантик откладывает. Таким образом каждый день у него набирается некоторое количество фантиков.
Нашему герою интересно, какое максимальное количество фантиков он сможет собрать за K дней (необязательно идущих подряд) и минимальное количество фантиков, собранных за день. Помогите нашему герою узнать эту информацию.