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

Рассматриваются частицы на плоскости. Для каждой частицы известны декартовы координаты x и y, проекции вектора скорости Vx и Vy, масса m, а также признак внутреннего строения, обозначенный одним из значений I–VII.

Частицы требуется разбить на 4 непересекающихся непустых кластеров по значениям кинетической энергии. Для любых двух частиц, попавших в один кластер, модуль разности значений E не превышает R = 2,2. Гарантируется, что такое разбиение существует и единственно.

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

В каждой строке файла записаны шесть значений: x y Vx Vy m признак. Числовые значения записаны в одинаковых для всех частиц условных единицах и разделены одним или несколькими пробелами и/или символами табуляции. Количество строк в файле не превышает 10000. Абсолютное значение каждого числового параметра не превышает 100.

Для каждого кластера определите его центр, а затем найдите два числа: Q₁ — количество частиц с признаком III в кластере, содержащем наибольшее число частиц; Q₂ — расстояние между центрами кластеров с наибольшим и наименьшим количеством частиц.

В ответе запишите два числа: сначала Q₁ без изменения, затем целую часть произведения Q₂ × 10 000.

Для справки

E = 1/2 · m · (Vx² + Vy²).

Евклидово расстояние между точками A(x₁, y₁) и B(x₂, y₂): d(A,B) = √((x₂ − x₁)² + (y₂ − y₁)²).

Типовой пример организации данных во входном файле

1.20  -3.40   2.00  -3.00  0.50  III
-2.10  4.30  -1.50   2.20  1.40  VI
5.60   1.10   4.00   0.50  0.80  II

Для первой строки примера значение кинетической энергии равно приблизительно 3.2500.

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

Рассматриваются частицы на плоскости. Для каждой частицы известны декартовы координаты x и y, проекции вектора скорости Vx и Vy, масса m, а также признак внутреннего строения, обозначенный одним из значений I–VII.

Частицы требуется разбить на 4 непересекающихся непустых кластеров по значениям кинетической энергии. Для любых двух частиц, попавших в один кластер, модуль разности значений E не превышает R = 1,8. Гарантируется, что такое разбиение существует и единственно.

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

В каждой строке файла записаны шесть значений: x y Vx Vy m признак. Числовые значения записаны в одинаковых для всех частиц условных единицах и разделены одним или несколькими пробелами и/или символами табуляции. Количество строк в файле не превышает 10000. Абсолютное значение каждого числового параметра не превышает 100.

Для каждого кластера определите его центр, а затем найдите два числа: Q₁ — наибольшее расстояние от частицы с признаком V до центра того кластера, которому эта частица принадлежит; Q₂ — наибольшая масса среди центров кластеров.

В ответе запишите целые части произведений Q₁ × 10 000 и Q₂ × 10 000.

Для справки

E = 1/2 · m · (Vx² + Vy²).

Евклидово расстояние между точками A(x₁, y₁) и B(x₂, y₂): d(A,B) = √((x₂ − x₁)² + (y₂ − y₁)²).

Типовой пример организации данных во входном файле

1.20  -3.40   2.00  -3.00  0.50  III
-2.10  4.30  -1.50   2.20  1.40  VI
5.60   1.10   4.00   0.50  0.80  II

Для первой строки примера значение кинетической энергии равно приблизительно 3.2500.

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

Рассматриваются частицы на плоскости. Для каждой частицы известны декартовы координаты x и y, проекции вектора скорости Vx и Vy, масса m, а также признак внутреннего строения, обозначенный одним из значений I–VII.

Частицы требуется разбить на 4 непересекающихся непустых кластеров по значениям кинетической энергии. Для любых двух частиц, попавших в один кластер, модуль разности значений E не превышает R = 2,0. Гарантируется, что такое разбиение существует и единственно.

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

В каждой строке файла записаны шесть значений: x y Vx Vy m признак. Числовые значения записаны в одинаковых для всех частиц условных единицах и разделены одним или несколькими пробелами и/или символами табуляции. Количество строк в файле не превышает 10000. Абсолютное значение каждого числового параметра не превышает 100.

Для каждого кластера определите его центр, а затем найдите два числа: Q₁ — наименьшее евклидово расстояние между двумя различными частицами одного кластера, каждая из которых имеет признак IV; Q₂ — минимальное значение кинетической энергии среди центров кластеров.

В ответе запишите два числа: целые части произведений Q₁ × 10 000 и Q₂ × 10 000 в указанном порядке.

Для справки

E = 1/2 · m · (Vx² + Vy²).

Евклидово расстояние между точками A(x₁, y₁) и B(x₂, y₂): d(A,B) = √((x₂ − x₁)² + (y₂ − y₁)²).

Типовой пример организации данных во входном файле

1.20  -3.40   2.00  -3.00  0.50  III
-2.10  4.30  -1.50   2.20  1.40  VI
5.60   1.10   4.00   0.50  0.80  II

Для первой строки примера значение кинетической энергии равно приблизительно 3.2500.

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

Рассматриваются частицы на плоскости. Для каждой частицы известны декартовы координаты x и y, проекции вектора скорости Vx и Vy, масса m, а также признак внутреннего строения, обозначенный одним из значений I–VII.

Частицы требуется разбить на 4 непересекающихся непустых кластеров по значениям кинетической энергии. Для любых двух частиц, попавших в один кластер, модуль разности значений E не превышает R = 2,0. Гарантируется, что такое разбиение существует и единственно.

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

В каждой строке файла записаны шесть значений: x y Vx Vy m признак. Числовые значения записаны в одинаковых для всех частиц условных единицах и разделены одним или несколькими пробелами и/или символами табуляции. Количество строк в файле не превышает 10000. Абсолютное значение каждого числового параметра не превышает 100.

Для каждого кластера определите его центр, а затем найдите два числа: Q₁ — наибольшее евклидово расстояние между двумя частицами одного кластера, каждая из которых имеет признак II; Q₂ — максимальное значение кинетической энергии среди центров кластеров.

В ответе запишите два числа: сначала целую часть произведения Q₁ × 10 000, затем целую часть произведения Q₂ × 10 000.

Для справки

E = 1/2 · m · (Vx² + Vy²).

Евклидово расстояние между точками A(x₁, y₁) и B(x₂, y₂): d(A,B) = √((x₂ − x₁)² + (y₂ − y₁)²).

Типовой пример организации данных во входном файле

1.20  -3.40   2.00  -3.00  0.50  III
-2.10  4.30  -1.50   2.20  1.40  VI
5.60   1.10   4.00   0.50  0.80  II

Для первой строки примера значение кинетической энергии равно приблизительно 3.2500.

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

Для каждой частицы на плоскости известны её координаты x и y, проекции вектора скорости Vx и Vy, масса m и тип внутреннего строения. Тип обозначается одним из римских чисел от I до VII.

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

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

В каждой строке файла записаны шесть значений в следующем порядке: x, y, Vx, Vy, m, тип. Значения разделены пробелами и/или символами табуляции. Дробная часть чисел отделена точкой. Все величины заданы в согласованных единицах измерения. Масса каждой частицы положительна, абсолютное значение каждого числового поля не превосходит 100. В файле не более 10 000 строк; заголовка нет.

Для каждого кластера найдите его центр. Затем определите:

• Q1 — наибольшее евклидово расстояние между двумя частицами одного кластера, одна из которых имеет тип III, а другая — тип VI;
• Q2 — среднее арифметическое значений кинетической энергии центров всех пяти кластеров.

В каждом кластере есть частицы обоих указанных типов.

В ответе запишите два числа: сначала целую часть произведения Q1 · 10 000, затем целую часть произведения Q2 · 10 000.

Кинетическая энергия частицы вычисляется по формуле

\(E = m · (Vx^2 + Vy^2) / 2.\)

Евклидово расстояние между точками (x₁; y₁) и (x₂; y₂) равно

\(d = \sqrt{((x_2-x_1)^2 + (y_2-y_1)^2)}\)

Пример трёх строк файла:

1.20  -3.40   2.000  -1.000  0.60000000  III
5.10   0.80  -1.500   2.000  0.80000000  VI
-2.70  4.30   1.000  -3.000  0.40000000  I

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

Числа в ответе разделяйте одним пробелом.

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

Поступающих, допущенных к зачислению, упорядочивают по следующим правилам:

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

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

В первой строке файла записаны два натуральных числа N и K — количество поступающих и количество мест, 1 ≤ K < N ≤ 100 000. Каждая из следующих N строк содержит пять целых чисел: уникальный ID поступающего, баллы за три испытания и отметку о прохождении практикума. ID находится в диапазоне от 1 до 1 000 000, каждый балл — от 0 до 100. Отметка 1 означает, что практикум пройден, 0 — что не пройден.

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

Пример содержимого файла:

6 2
101 60 70 80 1
205 80 60 70 1
309 90 90 39 1
412 70 70 70 1
518 95 90 80 0
624 55 60 65 1

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

Числа в ответе разделяйте одним пробелом.

Пусть S — сумма всех чётных натуральных делителей числа, кроме самого числа.

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

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


Формат ввода ответа при решении в эмуляторе станции КЕГЭ
Каждая пара чисел записывается в отдельной строке. В первом столбце записывается найденное число, во втором - значение S.

 

Текстовый файл содержит одну строку длиной не более 3 000 000 символов. Строка состоит из латинских букв A, B, C, D, E и цифр от 1 до 9.

Определите максимальную длину непрерывной последовательности символов, которая содержит ровно 1500 вхождений подстроки BCA и не более 20 букв E.

В ответе запишите количество символов в найденной последовательности.

В текстовом файле задан ориентированный взвешенный граф, не содержащий циклов. Каждая строка описывает одно ребро и содержит три числа: L, M и W. Натуральные числа L и M — номера начальной и конечной вершин ребра, положительное вещественное число W — его вес. Между одной и той же парой вершин не бывает нескольких рёбер одного направления.

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

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

В ответе запишите целую часть длины кратчайшего пути.

Пример графа:

Пример содержимого файла для этого графа: 63 941 8.0 7 28 4.6 941 512 1.1 63 28 1.5 7 941 11.6 28 941 3.2 7 63 2.4

Ответ для примера: 7.

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

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

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

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

В ответе запишите целое число миллисекунд.

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

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

• Петя не может выиграть первым ходом;
• Петя может гарантированно выиграть своим вторым ходом независимо от действий Вани.

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

Числа в ответе разделяйте одним пробелом.

Петя и Ваня играют с одной кучей камней. Они ходят по очереди, первым ходит Петя. За один ход игрок может:

• убрать из кучи 3 камня;
• убрать из кучи 7 камней;
• уменьшить количество камней в 3 раза, если оно делится на 3 без остатка.

Игра заканчивается, как только в куче остаётся не более 20 камней. Побеждает игрок, сделавший последний ход. В начальный момент в куче S камней, S ≥ 21.

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

Найдите наименьшее S, при котором Петя не может выиграть первым ходом, а Ваня после любого первого хода Пети может выиграть своим первым ходом.

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

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

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

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

Числа в ответе разделяйте одним пробелом.

В файле записана последовательность целых чисел, каждое из которых по модулю не превосходит 100 000. Каждое число записано в отдельной строке. Определите количество пар соседних элементов, в которых ровно одно число кратно 7, а сумма чисел больше наименьшего положительного элемента всей последовательности, оканчивающегося на 17. Затем найдите наименьшую сумму элементов среди таких пар. Гарантируется, что указанный положительный элемент и хотя бы одна подходящая пара существуют.

В ответе запишите два числа: сначала количество пар, затем наименьшую из их сумм.

Числа в ответе разделяйте одним пробелом (либо вносите в таблицу, если выполняете задание через эмулятор станции КЕГЭ).

 

Функция F(n), где n — натуральное число, определена следующими соотношениями:

• F(n) = 1 при n ≤ 2;
• F(n) = n · F(n − 2) при n > 2.

Вычислите значение выражения \((F(2027) − F(2025)) / F(2023)\).

Обозначим через ДЕЛ(n, m) утверждение «натуральное число n делится без остатка на натуральное число m».

Сколько существует натуральных значений A, при которых выражение

\((ДЕЛ(x, 36) \to ДЕЛ(x, A)) \land (ДЕЛ(x, A) \to ДЕЛ(x, 6))\)

истинно при любом натуральном значении x?

Числа в выражении записаны в системе счисления с основанием 19:

\(4x31_{19} + 2x7_{19} + x5_{19}.\)

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

Для найденного x вычислите частное от деления значения выражения на 17. В ответе запишите это частное в десятичной системе счисления.

Исполнитель преобразует число на экране с помощью трёх команд:

• A. Прибавить 2.
• B. Прибавить 3.
• C. Умножить на 2.

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

Сколько существует программ, которые преобразуют число 3 в число 29 и траектория которых содержит ровно одно из чисел 9 или 17?

Исполнитель МТ работает с бесконечной лентой, разделённой на ячейки. В каждой ячейке находится символ 0, символ 1 или пустой символ λ. Головка исполнителя находится в одном из состояний q0, q1 и обозревает одну ячейку.

Программа задаётся таблицей. Строка таблицы соответствует текущему состоянию головки, столбец — символу в обозреваемой ячейке. Команда состоит из трёх элементов: записываемого символа, действия головки и нового состояния. Действие L означает сдвиг на одну ячейку влево, R — на одну ячейку вправо, S — остановку. Сначала выполняется запись символа, затем действие головки. Прочерком отмечены неиспользуемые сочетания состояния и символа.

На ленте в соседних ячейках записано двоичное представление числа 1535 без ведущих нулей. Все остальные ячейки пусты. В начальный момент головка находится в состоянии q0 в пустой ячейке непосредственно справа от записи числа.

Исполнитель МТ работает с бесконечной лентой, разделённой на ячейки. В каждой ячейке находится символ 0, символ 1 или пустой символ λ. Головка исполнителя находится в одном из трёх состояний q0, q1, q2 и обозревает одну ячейку.

Программа задаётся таблицей. Строка таблицы соответствует текущему состоянию головки, столбец — символу в обозреваемой ячейке. Команда состоит из трёх элементов: записываемого символа, действия головки и нового состояния. Действие L означает сдвиг на одну ячейку влево, R — на одну ячейку вправо, S — остановку. Сначала выполняется запись символа, затем действие головки.

Выполните задание
На ленте в соседних ячейках записано двоичное представление числа 1535 без ведущих нулей. Все остальные ячейки пусты. В начальный момент головка находится в состоянии q₀ и обозревает крайнюю левую цифру записи числа.

Определите число, двоичная запись которого останется на ленте после завершения программы. Ответ запишите в десятичной системе счисления.