Вариант к1
Задание 1
На рисунке справа схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах). Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите длину кратчайшего пути между пунктами В и К. Передвигаться можно только по указанным дорогам.
Задание 2
Логическая функция F задаётся выражением
((x → z) ∧ (z → w)) ∨ (y ≡ (x ∨ z)).
На рисунке приведён частично заполненный фрагмент таблицы истинности функции F, содержащий неповторяющиеся строки. Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных x, y, z, w.
В ответе напишите буквы x, y, z, w в том порядке, в котором идут соответствующие им столбцы. Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.
Задание 3
В фрагменте базы данных представлены сведения о родственных отношениях. На основании приведённых данных определите сколько племянников и племянниц старше хотя бы одного из своих дядей или хотя бы одной из своих тетей (дядя или тетя - это родные брат или сестра матери или отца).
Задание 4
Для кодирования некоторой последовательности, состоящей из букв Л, М, Н, П, Р, решили использовать неравномерный двоичный код, удовлетворяющий условию, что никакое кодовое слово не является началом другого кодового слова. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Для букв Л, М, Н использовали соответственно кодовые слова 00, 01, 11. Для двух оставшихся букв – П и Р – кодовые слова неизвестны. Укажите кратчайшее возможное кодовое слово для буквы П, при котором код будет удовлетворять указанному условию. Если таких кодов несколько, укажите код с наименьшим числовым значением.
Задание 5
На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1) Строится двоичная запись числа N.
2) К этой записи дописывается (дублируется) последняя цифра.
3) Затем справа дописывается 0, если в двоичном коде числа N чётное число единиц, и 1, если нечётное.
4) К полученному результату дописывается ещё один бит чётности так, чтобы количество единиц в двоичной записи полученного числа стало чётным.
Полученная таким образом запись (в ней на три разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R. Укажите минимальное число R, большее 105, которое могло получиться в результате работы автомата. В ответе это число запишите в десятичной системе.
Задание 6
Определите, сколько существует целых положительных значений, подаваемых на вход программе, при которых программа выведет 80.
Задание 7 (№140).
Какой минимальный объём памяти (в Кбайт) нужно зарезервировать, чтобы можно было сохранить любое растровое изображение размером 1024 на 512 пикселей при условии, что в изображении могут использоваться 64 различных цвета? В ответе запишите только целое число, единицу измерения писать не нужно.
Задание 8
Алексей составляет таблицу кодовых слов для передачи сообщений, каждому сообщению соответствует своё кодовое слово. В качестве кодовых слов Алексей использует 5-буквенные слова, в которых есть только буквы A, B, C, X, причём буква X может появиться на последнем месте или не появиться вовсе. Сколько различных кодовых слов может использовать Алексей?
Задание 9
В файле электронной таблицы содержатся вещественные числа – результаты ежечасного измерения температуры воздуха на протяжении трёх месяцев. Найдите среднее значение измерений в апреле во второй половине дня (с 12:00), в которых температура не превышала 19 градусов.
В ответе запишите только целую часть получившегося числа.
Задание 10
С помощью текстового редактора определите, сколько раз, встречается слово «футляр» или «Футляр» в тексте рассказа А.П. Чехова «Человек в футляре». Другие формы слова «футляр», такие как «футляры», «футляре» и т.д., учитывать не следует. В ответе укажите только число.
Задание 11
Для регистрации на сайте необходимо продумать пароль, состоящий из 9 символов. Он должен содержать хотя бы 1 цифру, строчные или заглавные буквы латинского алфавита (алфавит содержит 26 букв) и хотя бы 1 символ из перечисленных: «.», «$», «#», «@», «%», «&». В базе данных для хранения сведения о каждом пользователе отведено одинаковое и минимальное возможное целое число байт. При этом используют посимвольное кодирование паролей, все символы кодируют одинаковым и минимально возможным количеством бит. Кроме собственного пароля, для каждого пользователя в системе хранятся дополнительные сведения, для чего выделено целое число байт одинаковое для каждого пользователя. Для хранения сведений о двадцати пользователях потребовалось 500 байт. Сколько байт выделено для хранения дополнительных сведений об одном пользователе. В ответе запишите только целое число – количество байт.
Задание 12
Дана программа для исполнителя Редактор:
НАЧАЛО
ПОКА нашлось (1111)
Заменить (1111, 7)
Заменить (77, 1)
КОНЕЦ ПОКА
КОНЕЦ
Какая строка получится в результате применения приведённой программы к строке вида 1…17…7 (95 единиц и 31 семёрка)?
Задание 13
На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует маршрутов длиной 8 из пункта А в пункт М? Длиной пути считать количество дорог, составляющих этот путь.
Задание 14
Значение выражения 7202 + 49102 - 720 записали в семеричной системе счисления. Сколько цифр 6 в такой записи?
Задание 15
Обозначим через ДЕЛ(n, m) утверждение «натуральное число n делится без остатка на натуральное число m».
Для какого наибольшего натурального числа А формула
ДЕЛ(x, А) → (ДЕЛ(x, 6) → ДЕЛ(x, 9))
тождественно истинна (то есть принимает значение 1 при любом натуральном значении переменной х)?
Задание 16
Алгоритм вычисления функции F(n) задан следующими соотношениями:
F(n) = 1, при n < -100000,
F(n) = F(n – 1) + 3*F(n – 3) + 2, при n > 10,
F(n) = -F(n – 1) для остальных случаев.
Чему равно значение функции F(20)?
Задание 17
Рассматривается множество целых чисел, принадлежащих числовому отрезку [8800; 55535], которые удовлетворяют следующим условиям:
− произведение разрядов больше 35;
− один из разрядов равен 7.
Найдите наибольшее из таких чисел и их количество.
Для выполнения этого задания можно написать программу или воспользоваться редактором электронных таблиц.
Задание 18
Квадрат разлинован на N×N клеток (3 < N < 17). В каждой клетке лежат конфеты, количество которых соответствует записанному числу. На поле работает исполнитель Дружище, который съедает все конфеты в клетке. Также, если исполнитель проходит между двумя четными или двумя нечетными значениями, то Добрый Волшебник дает ему еще 10 конфет, которые он, конечно же, сразу съедает. Так, например, если исполнитель приходит в клетку С3 из клетки В3, считается, что он прошел между клетками С2 и С4, если в С3 из С2 – между В3 и D3. Исполнитель может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Дружище перемещается в соседнюю правую клетку, по команде вниз – в соседнюю нижнюю. При попытке выхода за границу квадрата Дружище расстраивается, что ему не дают конфеты, и отказывается идти дальше.
Нам важно, чтобы Дружище съел как можно меньше конфет и при этом добрался из левой верхней клетки в правую нижнюю.
Исходные данные представляют собой электронную таблицу размером N×N, каждая ячейка которой соответствует клетке квадрата.
Пример входных данных:
Для указанных входных данных ответом должно быть число – минимально возможное съедаемое количество конфет – 53.
Задание 19
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может
а) добавить в кучу один камень;
б) увеличить количество камней в куче в два раза;
в) увеличить количество камней в куче в три раза.
Игра завершается в тот момент, когда количество камней в куче становится не менее 36. Если при этом в куче оказалось не более 60 камней, то победителем считается игрок, сделавший последний ход. В противном случае победителем становится его противник. В начальный момент в куче было S камней, 1 ≤ S ≤ 35.
Найдите минимальное значение S, при котором Ваня выигрывает своим первым ходом при любой игре Пети.
Задание 20.
Для игры, описанной в задании 19, определите сколько существует значений S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
− Петя не может выиграть за один ход;
− Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Задание 21.
Для игры, описанной в задании 19, найдите минимальное и максимальное значения S, при которых одновременно выполняются два условия:
– у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Найденные значения запишите в ответе в порядке возрастания.
Задание 22
Ниже записана программа. Получив на вход число x, эта программа печатает два числа, L и M. Укажите наибольшее из таких чисел x, при вводе которых алгоритм печатает сначала 4, а потом 8.
Задание 23
У исполнителя Калькулятор три команды, которым присвоены номера:
1. прибавь 1
2. умножь на 2
3. возведи в квадрат
Сколько есть программ, которые число 5 преобразуют в число 154?
Задание 24 (№505).
Текстовый файл состоит не более чем из 106 десятичных цифр. Найдите максимальную длину последовательности, каждые две соседние цифры в которой в сумме дают значение не меньшее 10.
Например, в последовательности 1567543853 есть две такие последовательности 5675 и 385.
В качестве ответа укажите максимальную длину найденной последовательности.
Для выполнения этого задания следует написать программу.
Задание 25
Уникальным назовём число, если у него первые две цифры нечётные. Для интервала [33333;55555] найдите числа, которые делятся на 7, 11, 13. В качестве ответа приведите пары чисел – порядковый номер по возрастанию найденного числа и само число.
Задание 26
Каждый день Петр ест некоторое количество конфет. Так как Петр любит фантики от конфет, то он каждый такой фантик откладывает. Таким образом каждый день у него набирается некоторое количество фантиков.
Нашему герою интересно, какое максимальное количество фантиков он сможет собрать за K дней (необязательно идущих подряд) и минимальное количество фантиков, собранных за день. Помогите нашему герою узнать эту информацию.
Входные и выходные данные.
В первой строке входного файла находятся два числа: N – Общее количество дней, на протяжении которых Петр собирал фантики (натуральное число, не превышающее 10 000) и K – количество дней, на протяжении которых Петр собрал максимально возможное количество фантиков (натуральное число, не превышающее 1000).
В следующих N строках находятся значения количества собранных фантиков (все числа натуральные, не превышающие 100), каждое в отдельной строке.
Гарантируется, что N > K.
Запишите в ответе два числа: максимальное число фантиков, собранных Петей за K дней и минимальное количество собранных главным героем за один день
Пример входного файла:
5 3
При таких исходных данных Петр может собрать суммарно максимум 150 фантиков за 3 дня (40+50+60 = 150)
Наименьшие количество собранных главным героем фантиков за один день оказалось – 10
Задание 27
Дан набор данных, состоящий из неотрицательных целых чисел. Из данного набора выбрали пары четных элементов, между которыми находится четное количество единиц (не меньше 2). Программа должна напечатать одно число – количество пар, которые удовлетворяет условию выбора.
Входные данные:
Даны два входных файла: файл A и файл B, каждый из которых содержит в первой строке количество чисел N (1 ≤ N ≤ 100000). Каждая из следующих N строк содержит одно целое положительное число.
Пример входного файла:
Для указанных входных данных количество пар с четными значениями 2 – (8, 6), (2, 6).
В ответе укажите два числа: сначала количество троек для файла А, затем для файла B.
Предупреждение: для обработки файла B не следует использовать переборный алгоритм, вычисляющий сумму для всех возможных вариантов, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.