Экзамены и диагностики

10 224 задачивместе с подтемами
Число у задачи — рейтинг сложности, слово рядом — насколько она трудна по сравнению с другими задачами такого же типа. Шкалы задач с ответом и задач с кодом между собой не сравниваются. Рядом — счётчики попыток: ✓ успешные, ✗ неуспешные.
(Д. Муфаззалов) Назовём маской числа последовательность цифр, в которой также могут встречаться следующие символы: — символ «?» означает ровно одну произвольную цифру; — символ «*» означает любую последовательность цифр произвольной длины; в том числе «*» может задавать и пустую последовательность. Например, маске 123*4?5 соответствуют числа 123405 и 12300425. Пусть А(n) – это квадрат суммы двух чисел: числа, запись которого есть левая половина записи числа n, и числа, запись которого есть правая половина записи числа n. Для чисел с нечетным количеством цифр величина A(n) равна нулю. Например, A(1234) = (12 + 34)2 = 2116. Среди натуральных чисел, не превышающих 35·106, найдите все числа, соответствующие маске *2*0*2*5*, и кратные числу 25, для которых А(n) = n. В ответе запишите в первом столбце таблицы все найденные числа в порядке возрастания, а во втором столбце – соответствующие им результаты деления этих чисел на 25.
Задание выполняется с использованием прилагаемых файлов.

Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд: разбить их на четыре непересекающихся непустых подмножества — кластера.

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

В файле также имеются координаты ровно семи лишних точек — аномалий, возникших в результате помех при передаче данных. Эти точки не принадлежат ни одному из кластеров, и учитывать их не нужно. Гарантируется, что разбиение на четыре кластера и семь аномалий существует и единственно.

Будем называть центром кластера точку этого кластера, сумма расстояний от которой до всех остальных точек того же кластера минимальна. Для каждого кластера гарантируется единственность его центра. Количества точек во всех четырёх кластерах различны.

Расстояние между точками A(x1, y1) и B(x2, y2) вычисляется по формуле:

d(A, B) = √((x2 − x1)2 + (y2 − y1)2).

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

В каждой строке файла находятся два вещественных числа — координаты x и y одной точки в условных единицах, разделённые пробелами. Десятичный разделитель — точка. Строки заголовка и строки с количеством точек в файле нет.

Количество точек не превышает 10 000. Абсолютные значения координат не превышают 200. Все точки различны. Порядок строк не определяет принадлежность точки кластеру.

Выполните задание

Определите координаты центров всех четырёх кластеров и количество точек в каждом кластере. Затем вычислите два числа:

  • P — расстояние между центром кластера с наименьшим количеством точек и центром кластера с наибольшим количеством точек;
  • Q — наибольшее расстояние от центра кластера с наибольшим количеством точек до точки этого же кластера.

В ответе запишите в одной строке два целых числа: сначала целую часть произведения P · 10000, затем целую часть произведения Q · 10000. Округление до ближайшего целого не выполняется. Для выполнения этого задания следует написать программу.

Запись ответа на платформе. Введите два числа в указанном в условии порядке, разделив их одним пробелом.

Задание выполняется с использованием прилагаемых файлов.

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

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

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

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

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

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

В первой строке входного файла находятся два натуральных числа: N — количество участков, не превышающее 1 000 000, и K — количество видов газонокосилок в магазине, не превышающее 100 000.

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

В последних K строках записано по два натуральных числа: мощность газонокосилки, не превышающая 1000, и стоимость одной газонокосилки данного вида. Числа в строке разделены пробелами.

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

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

Типовой пример организации данных во входном файле
3 3
1
3
2
10 7
3 7
2 1

В этом примере для участков с требованиями 1 и 2 выбирают вид мощности 2 стоимостью 1. Для участка с требованием 3 выбирают мощность 10 стоимостью 7: при одинаковой цене она предпочтительнее мощности 3.

На газонокосилки наибольшей купленной мощности потрачено 7; куплено два различных вида. Ответ к примеру: 7 2. Пример имеет иллюстративный характер; для выполнения задания используйте данные прилагаемого файла.

Запись ответа на платформе. Введите два числа в указанном в условии порядке, разделив их одним пробелом.

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

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

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

Примечание. Простым называется натуральное число, имеющее ровно два различных натуральных делителя: 1 и само себя. В данном задании учитываются различные простые делители: например, делитель 2 считается один раз независимо от того, в какой степени он входит в разложение числа.

Запись ответа на платформе. Введите все десять чисел в одну строку через пробел: сначала два числа первой строки таблицы, затем два числа второй строки и так далее. Не добавляйте скобки и запятые.

Задание выполняется с использованием прилагаемых файлов.

Текстовый файл состоит из десятичных цифр и заглавных букв латинского алфавита.

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

Если подходящих последовательностей с максимальным количеством букв несколько, выберите последовательность с наименьшим порядковым номером первого символа в файле.

В ответе запишите число — порядковый номер первого символа найденной последовательности. Для выполнения этого задания следует написать программу.

Примечание. Нумерация символов файла начинается с нуля. Искомая позиция — позиция первой цифры, а не первой буквы. Гарантируется, что подходящая последовательность существует.

Задание выполняется с использованием прилагаемых файлов.

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

Каждая строка содержит два натуральных числа A и B, разделённых пробелами. Такая строка означает, что в графе существует ориентированное ребро из вершины A в вершину B. Каждое ребро описано ровно один раз; строка с количеством вершин или рёбер отсутствует.

Путём из вершины X в вершину Y называется последовательность вершин, начинающаяся в X и заканчивающаяся в Y, в которой каждые две соседние вершины соединены ориентированным ребром в направлении следования. Два пути считаются различными, если различаются последовательности их вершин.

Граф не содержит ориентированных циклов. Всего в нём не более 10 000 вершин и не более 100 000 рёбер; номера вершин не превышают 10 000.

Определите количество различных путей из вершины 17 в вершину 1943. Гарантируется, что хотя бы один такой путь существует. В ответе запишите целое число.

Типовой пример организации данных в файле
1 2
1 3
2 4
3 4
2 3
4 5

В этом примере из вершины 1 в вершину 5 ведут три пути: 1–2–4–5, 1–3–4–5 и 1–2–3–4–5.

Пример имеет иллюстративный характер. Для выполнения задания используйте данные прилагаемого файла. Следует написать программу.

Задание выполняется с использованием прилагаемых файлов.

В файле содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно. Данные находятся на листе Sheet1.

Будем говорить, что процесс B зависит от процесса A, если для выполнения процесса B необходимы результаты выполнения процесса A. В этом случае процесс B может начаться только после полного завершения процесса A.

Информация о процессах представлена в виде таблицы. В первом столбце указан идентификатор процесса — ID, во втором столбце — время его выполнения в миллисекундах, в третьем перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс независимый, в третьем столбце записано значение 0.

Каждый процесс начинается в самое раннее допустимое время и выполняется непрерывно в течение указанного времени. Число одновременно выполняющихся процессов не ограничено. Нумерация миллисекунд начинается с 1; независимые процессы начинают работу на первой миллисекунде.

Если процесс длительностью d миллисекунд начинается на миллисекунде t, то он выполняется на миллисекундах t, t + 1, …, t + d − 1. Зависимый процесс может начаться со следующей миллисекунды после завершения всех процессов, от которых он зависит.

Определите максимальное количество процессов, которые не могут начать своё выполнение раньше 14-й миллисекунды.

Типовой пример организации данных в файле
ID процесса BВремя выполнения B, мсID процессов A
130
241
322; 4
450
581; 4
631

Для приведённой таблицы процесс 1 выполняется на миллисекундах 1–3, процесс 2 — на миллисекундах 4–7, процесс 4 — на миллисекундах 1–5. Поэтому процесс 3 начинается на 8-й миллисекунде и заканчивается на 9-й.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные прилагаемого файла.

Для игры из задания 19. Ниже повторены её правила.

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя.

За один ход игрок может добавить в одну из куч по своему выбору три камня или увеличить количество камней в одной из куч в два раза. У каждого игрока есть неограниченное количество камней, чтобы делать ходы.

Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 324. Победителем считается игрок, сделавший последний ход, то есть первым получивший суммарно в кучах 324 камня или больше.

В начальный момент в первой куче было 9 камней, во второй куче — S камней, где 1 ≤ S ≤ 314.

Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.

Найдите минимальное значение S, при котором одновременно выполняются два условия:

  • у Вани есть выигрышная стратегия, позволяющая ему выиграть своим первым или вторым ходом при любой игре Пети;
  • у Вани нет стратегии, позволяющей ему гарантированно выиграть своим первым ходом.

Для игры из задания 19. Ниже повторены её правила, чтобы задание можно было выполнять независимо от расположения вопросов на платформе.

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя.

За один ход игрок может добавить в одну из куч по своему выбору три камня или увеличить количество камней в одной из куч в два раза. У каждого игрока есть неограниченное количество камней, чтобы делать ходы.

Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 324. Победителем считается игрок, сделавший последний ход, то есть первым получивший суммарно в кучах 324 камня или больше.

В начальный момент в первой куче было 9 камней, во второй куче — S камней, где 1 ≤ S ≤ 314.

Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.

Найдите два наименьших значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:

  • Петя не может выиграть за один ход;
  • Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.

Найденные значения запишите в порядке возрастания.

Запись ответа на платформе. Введите два числа в указанном в условии порядке, разделив их одним пробелом.

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя.

За один ход игрок может добавить в одну из куч по своему выбору три камня или увеличить количество камней в одной из куч в два раза. У каждого игрока есть неограниченное количество камней, чтобы делать ходы.

Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 324. Победителем считается игрок, сделавший последний ход, то есть первым получивший суммарно в кучах 324 камня или больше.

В начальный момент в первой куче было 9 камней, во второй куче — S камней, где 1 ≤ S ≤ 314.

Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.

Известно, что Ваня выиграл своим первым ходом после неудачного хода Пети. Укажите минимальное значение S, при котором такая ситуация возможна.

Задание выполняется с использованием прилагаемых файлов.

Квадрат разлинован на N × N клеток, где 1 < N < 30. Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз.

По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз — в соседнюю нижнюю. Квадрат ограничен внешними стенами. Между соседними клетками также могут находиться внутренние стены. Сквозь стену Робот пройти не может.

Перед каждым запуском в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монету с собой; это относится также к начальной и конечной клеткам маршрута.

Робот начинает движение в левой верхней клетке. В «угловых» клетках поля — тех, которые справа и снизу ограничены стенами, — он не может продолжать движение, поэтому накопленная сумма считается итоговой.

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

Определите максимальную и минимальную суммы среди всех возможных итоговых сумм, которые может собрать Робот, пройдя из левой верхней клетки в конечную клетку маршрута. В ответе укажите сначала максимальную, затем минимальную сумму.

Исходные данные представлены электронной таблицей размером N × N, каждая ячейка которой соответствует клетке квадрата. Внутренние и внешние стены обозначены утолщёнными линиями границ ячеек. Обычные тонкие линии стенами не являются.

Иллюстративный пример

Для поля 2 × 2 без внутренних стен с числами, приведёнными ниже, возможны маршруты 1 → 2 → 4 и 1 → 3 → 4.

12
34

Максимальная сумма в этом примере равна 8, минимальная — 7. Пример поясняет правила подсчёта; для выполнения задания используйте данные прилагаемого файла.

Запись ответа на платформе. Введите два числа в указанном в условии порядке, разделив их одним пробелом.

Задание выполняется с использованием прилагаемых файлов.

В файле содержится последовательность целых чисел. Её элементы могут принимать целые значения от −100 000 до 100 000 включительно. Каждое число записано в отдельной строке; служебного заголовка нет.

Определите количество троек элементов последовательности, в которых все элементы положительны, при этом ровно один элемент имеет запись, оканчивающуюся цифрой 3 в системе счисления с основанием 7, а сумма элементов тройки не больше максимального элемента всей последовательности, кратного 5.

В ответе запишите количество найденных троек, затем абсолютное значение минимального из произведений элементов таких троек.

В данной задаче под тройкой подразумеваются три идущих подряд элемента последовательности. Гарантируется, что в последовательности есть элемент, кратный 5, и хотя бы одна подходящая тройка.

Запись ответа на платформе. Введите два числа в указанном в условии порядке, разделив их одним пробелом.

Алгоритмы вычисления значений функций F(n) и G(n), где n — целое число, заданы следующими соотношениями:

F(n) = n, если n ≤ 7;
F(n) = F(n − 2) + 4, если n > 7;

G(n) = n, если n > 42025;
G(n) = n − 1 + G(n + 2), если n ≤ 42025.

Чему равно значение выражения G(42015) − F(2025)?

Для какого наибольшего целого неотрицательного числа A выражение

(y + 11x > A) ∨ (x < 234110) ∨ (y < 468220)

тождественно истинно, то есть принимает значение 1 при любых целых неотрицательных значениях x и y?

Значение арифметического выражения

4 · 31251012 + 3 · 6251011 − 2 · 1251010 + 3 · 251009 − 4 · 51008 − 15625

записали в системе счисления с основанием 25. Определите в 25-ричной записи полученного числа количество цифр с числовым значением, не превышающим 9. Ведущие нули в записи отсутствуют.

Исполнитель преобразует число на экране. У исполнителя есть три команды, которые обозначены латинскими буквами:

  1. A. Найти целую часть от деления на 5.
  2. B. Вычесть 3.
  3. C. Вычесть 4.

Первая команда заменяет число на экране целой частью результата его деления на 5. Вторая и третья команды уменьшают число соответственно на 3 и на 4. Программа для исполнителя — последовательность команд.

Сколько существует программ, для которых при исходном числе 46 результатом является число 16 и при этом траектория вычислений содержит число 23?

Траектория вычислений программы — последовательность результатов выполнения всех команд программы. Например, для программы BBC при исходном числе 46 траектория состоит из чисел 43, 40, 36.

Исполнитель МТ представляет собой читающую и записывающую головку, которая может передвигаться вдоль бесконечной горизонтальной ленты, разделённой на равные ячейки. В каждой ячейке находится ровно один символ из алфавита исполнителя, включая специальный пустой символ λ.

Время работы исполнителя делится на дискретные такты — шаги. На каждом такте головка находится в одном из допустимых состояний q0, q1, … . В начальный момент головка находится в состоянии q0.

Головка обозревает одну ячейку ленты — текущую ячейку. За один такт исполнитель записывает в неё указанный символ, после чего может сдвинуться в соседнюю ячейку и перейти в указанное состояние либо завершить работу. Записываемый символ может совпадать с уже находящимся в ячейке.

Программа задаётся таблицей. В первой строке перечислены символы алфавита, в первом столбце — состояния головки. В клетке на пересечении строки состояния и столбца символа находится выполняемая команда. Если сочетание символа и состояния при работе программы невозможно, клетка остаётся пустой.

Каждая команда состоит из трёх элементов, разделённых запятыми:

  1. символ, записываемый в текущую ячейку;
  2. направление: L — сдвиг на одну ячейку влево, R — сдвиг на одну ячейку вправо, S — завершение работы после записи символа без сдвига;
  3. состояние, в которое переходит головка.

Например, команда X, L, q2 означает: записать X в текущую ячейку, сдвинуться в соседнюю слева ячейку и перейти в состояние q2. Запись символа производится до сдвига.

Пример выполнения программы

Пусть на ленте подряд записаны три символа Z, остальные ячейки пусты, головка находится на первой пустой ячейке справа от слова ZZZ в состоянии q0. Для этой иллюстрации используется следующая программа:

СостояниеλZX
q0λ, L, q0X, L, q1
q1λ, S, q1X, L, q1

Начальное расположение ленты и головки:

…λλZZZλλ…
▲ q0

Лента и головка после остановки:

…λλXXXλλ…
▲ q1

Головка перемещается влево, заменяет все Z на X и останавливается на первой пустой ячейке слева от слова XXX. Пример поясняет правила чтения таблицы и не является программой основного задания.

Выполните задание

Алфавит исполнителя: {λ, 1, X, Z}. На ленте в соседних ячейках записано неизвестное ненулевое количество символов 1. Сразу справа от них записан один символ Z. Все остальные ячейки ленты заполнены символом λ.

В начальный момент головка расположена над самым левым символом 1 в состоянии q0. Программа работы исполнителя:

Состояниеλ1XZ
q0X, R, q1X, R, q0Z, L, q4
q11, R, q1X, R, q1Z, R, q2
q21, L, q31, R, q2
q3λ, R, q01, L, q3X, L, q3Z, L, q3
q4λ, S, q41, L, q4

После завершения программы на ленте находится 4054 символа 1. Определите количество символов 1, находившихся на ленте до начала работы программы. В ответе запишите целое число.

При регистрации в компьютерной системе каждому объекту присваивается пароль, состоящий из 609 символов. В качестве символов используются десятичные цифры, символы из 3862-символьного специального алфавита и ещё 20 специальных знаков. Все перечисленные группы символов не пересекаются.

В базе данных для хранения каждого пароля отведено одинаковое и минимально возможное целое число байт. При этом используется посимвольное кодирование паролей: все символы кодируются одинаковым и минимально возможным количеством бит.

Кроме собственно пароля для каждого объекта в системе хранятся дополнительные сведения, для которых отведено 179 байт на один объект.

Определите объём памяти в байтах, необходимый для хранения сведений — паролей и дополнительных данных — о 17 объектах. В ответе запишите только целое число.

В терминологии сетей TCP/IP маской сети называют двоичное число, которое показывает, какая часть IP-адреса узла сети относится к адресу сети, а какая — к адресу узла в этой сети.

Маска содержит сначала подряд идущие единицы, затем — нули. Адрес сети получается в результате применения поразрядной конъюнкции к заданному адресу узла и его маске.

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

Для узла с IP-адресом 221.26.40.132 адрес сети равен 221.26.40.128. Чему равна наибольшая возможная сумма числовых значений октетов широковещательного адреса этой сети?

В ответе запишите только число. Например, для широковещательного адреса 100.20.3.255 следовало бы записать 378.

Задание выполняется с использованием прилагаемых файлов.

Откройте файл электронной таблицы, содержащей в каждой строке семь целых чисел. Числа могут быть отрицательными, положительными или равными нулю. Нумерация строк начинается с 1; строки заголовков в таблице нет.

Определите сумму чисел строки таблицы с наименьшим номером, для которой одновременно выполнены оба условия:

  • в строке два различных числа повторяются по два раза каждое, остальные три числа встречаются по одному разу и попарно различны;
  • сумма квадратов неповторяющихся чисел строки больше квадрата номера этой строки.

В ответе запишите абсолютное значение полученной суммы.

Поделиться
Класснуть