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

Миша заполнял таблицу истинности логической функции

F = (x → y) ∧ (y → z) ∧ (z → w)

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

Перем.1 Перем.2 Перем.3 Перем.4   F
   0      0      0      1     1
   1      0      0      1     1
   1      1      0      1     1

Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных x, y, z, w. В ответе напишите буквы x, y, z, w в том порядке, в котором идут соответствующие им столбцы (сначала буква, соответствующая первому столбцу, затем второму и т.д.). Буквы пишите подряд, без разделителей.

Миша заполнял таблицу истинности логической функции

F = (x ∧ ¬z ∧ ¬w) ∨ (x ∧ ¬z ∧ y)

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

Перем.1 Перем.2 Перем.3 Перем.4   F
   0      0      0      1     1
   0      0      1      1     1
   1      0      1      1     1

Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных x, y, z, w. В ответе напишите буквы x, y, z, w в том порядке, в котором идут соответствующие им столбцы (сначала буква, соответствующая первому столбцу, затем второму и т.д.). Буквы пишите подряд, без разделителей.

На рисунке схема дорог N-ского района изображена в виде графа, в таблице содержатся сведения о протяжённости каждой из этих дорог (в километрах).

Так как таблицу и схему рисовали независимо друг от друга, нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Рёбра графа (без указания длин):

A-D; A-E; B-D; B-F; C-D; C-F; C-G; D-G; E-F

Таблица протяжённостей дорог между пунктами П1…П7 (пустая клетка — дороги нет):

    П 1 П 2 П 3 П 4 П 5 П 6 П 7
П 1   .   .   .   2   .  26   .
П 2   .   .   .   .   .  24  16
П 3   .   .   .  25  29   .   .
П 4   2   .  25   .  26   .  23
П 5   .   .  29  26   .  12   .
П 6  26  24   .   .  12   .   .
П 7   .  16   .  23   .   .   .

Определите, какова суммарная протяжённость дорог из пункта A в пункт E и из пункта A в пункт D. В ответе запишите целое число.

На рисунке схема дорог N-ского района изображена в виде графа, в таблице содержатся сведения о протяжённости каждой из этих дорог (в километрах).

Так как таблицу и схему рисовали независимо друг от друга, нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Рёбра графа (без указания длин):

A-F; B-D; B-G; C-G; D-E; D-G; E-F; E-G; F-G

Таблица протяжённостей дорог между пунктами П1…П7 (пустая клетка — дороги нет):

    П 1 П 2 П 3 П 4 П 5 П 6 П 7
П 1   .   .   .   .   .   6   .
П 2   .   .   .   .   .  30   8
П 3   .   .   .   4   .   .   .
П 4   .   .   4   .  14  11   .
П 5   .   .   .  14   .  12   5
П 6   6  30   .  11  12   .  26
П 7   .   8   .   .   5  26   .

Определите, какова суммарная протяжённость дорог из пункта E в пункт G и из пункта F в пункт G. В ответе запишите целое число.

Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек (изображений звёзд), то есть разбить их множество на N непересекающихся непустых подмножеств так, что точки каждого подмножества лежат внутри прямоугольника размера H × W, причём эти прямоугольники между собой не пересекаются. Стороны прямоугольников не обязательно параллельны координатным осям. Гарантируется, что такое разбиение существует и единственно.

Для каждой звезды дана характеристика: тип цвета, светимость и размер согласно таблицам:

Цвет:                     Размер:
O — голубой               I    — карлик
B — бело-голубой          II   — субкарлик
A — белый                 III  — гигант
F — жёлто-белый           IV   — сверхгигант
G — жёлтый                V    — мегагигант
K — оранжевый             VI   — супергигант
M — красный

Значения записаны в характеристике слитно: обозначение цвета, затем светимость (одна арабская цифра), затем размер звезды (например, A3III).

Антицентром кластера называется точка кластера, сумма расстояний от которой до всех остальных точек кластера максимальна; для каждого кластера антицентр единственен. Расстояние между точками A(x₁, y₁) и B(x₂, y₂):

\(d(A, B) = \sqrt{ (x_1 − x_2)^2 + (y_1 − y_2)^2 }\)

В файле A хранятся данные о звёздах двух кластеров, где для каждого кластера H = 4, W = 3; количество точек не превышает 1000. В файле B хранятся данные о звёздах трёх кластеров, где для каждого кластера H = 4, W = 3; количество точек не превышает 20000. В каждой строке записана информация об одной звезде: координата x, координата y и характеристика звезды. Структура файла B аналогична файлу A.

Для файла A определите координаты антицентра каждого кластера, затем найдите два числа: A₁ — минимальное расстояние от голубого субкарлика до антицентра его кластера; A₂ — сумму расстояний антицентров кластеров до точки (−1, 2). Для файла B определите антицентры кластеров, затем найдите два числа: B₁ — абсциссу антицентра кластера с минимальным количеством субкарликов; B₂ — ординату антицентра того же кластера.

В ответе запишите четыре числа: целую часть значения A₁ × 10000, затем целую часть значения A₂ × 10000, затем число B₁ × 10000, затем число B₂ × 10000.



Формат ответа
Ответ вводится построчно, в первой строке для файла А, во второй - для файла В. Числа в одной строке разделяются одним пробелом.
А₁ А₂
В₁ В₂

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

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

Истинный центр кластера (центроид) — это одна из звёзд кластера, сумма расстояний от которой до всех остальных звёзд кластера минимальна. Под расстоянием понимается евклидово расстояние между точками A(x₁, y₁) и B(x₂, y₂):

d(A, B) = sqrt( (x1 − x2)^2 + (y1 − y2)^2 )

В файле A хранятся данные о звёздах двух кластеров, где H = 6.5, W = 4.5 для каждого кластера; количество звёзд не превышает 1000. В файле B хранятся данные о звёздах трёх кластеров, где H = 5, W = 4 для каждого кластера; количество звёзд не превышает 10000. В каждой строке файла записана информация об одной звезде: сначала координата x, затем координата y (значения в условных единицах). Структура файла B аналогична файлу A.

Известно, что в каждом файле имеются координаты ровно трёх «лишних» точек, представляющих аномалии (помехи при передаче данных). Эти точки не относятся ни к одному кластеру, их учитывать не нужно.

Для файла A определите координаты центра каждого кластера, затем найдите два числа: P_x — минимальную из абсцисс центров кластеров и P_y — минимальную из ординат центров кластеров. Для файла B определите координаты центра каждого кластера, затем найдите два числа: Q₁ — минимальное расстояние между центрами кластеров и Q₂ — максимальное расстояние между центрами кластеров.

В ответе запишите четыре числа: абсолютную величину целой части произведения P_x × 10000, затем абсолютную величину целой части произведения P_y × 10000, затем абсолютную величину целой части произведения Q₁ × 10000, затем абсолютную величину целой части произведения Q₂ × 10000.

Фермерское хозяйство закупает виноград у местных поставщиков для производства соков. Используется виноград двух типов: A и B. Приём ведут K сборщиков, пронумерованных натуральными числами начиная с 1. Сборщики с нечётными номерами принимают только виноград типа A, сборщики с чётными номерами — только виноград типа B.

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

Формат входных данных. В первой строке входного файла записаны два числа: N — количество поставщиков (N ≤ 10 000) и K — количество сборщиков (K ≤ 100). Каждая из следующих N строк содержит два целых неотрицательных числа и букву, разделённые пробелами: время прибытия, время окончания разгрузки и тип винограда (A или B). Гарантируется, что время прибытия меньше времени окончания разгрузки и что никакие два поставщика с виноградом одного типа не прибывают в одну и ту же секунду. Поставщики перечислены в произвольном порядке.

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

Производитель детского питания производит оптовую закупку винограда у фермерских хозяйств региона. Используется виноград двух типов — A и B (светлый и тёмный). На закупку выделена определённая сумма денег.

У фермерских хозяйств каждая партия винограда имеет свою стоимость в рублях. На выделенные деньги необходимо приобрести как можно больше винограда типа A (независимо от партии) и не менее одной партии винограда B. Если виноград A закончится, то на оставшиеся деньги нужно приобрести как можно больше винограда B. Если существует несколько способов закупить максимальное количество винограда, следует выбрать такой, при котором будет приобретено как можно больше винограда A и при этом потрачено наименьшее количество денег.

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

Входные данные. Первая строка входного файла содержит два целых числа: N — общее количество партий винограда и M — сумму денег, выделенную на закупку (в рублях). Каждая из следующих N строк описывает одну партию и содержит целое число (стоимость партии в рублях) и один символ (латинская буква A или B), определяющий тип винограда. Все данные в строках отделены одним пробелом.

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

Пример входного файла:

6 110
40 B
50 A
50 B
30 B
20 A
10 B

В данном случае можно купить не более четырёх партий винограда, из них не более двух партий типа A. Минимальная цена такой покупки — 110 рублей (партии 10 B, 20 A, 30 B, 50 A). Останется 0 рублей. Ответ: 2 0.

Пусть R – сумма 4 наибольших делителей числа. Напишите программу, которая перебирает целые числа, большие 1151 996, в порядке возрастания и ищет среди них такие, для которых R является простым числом и палиндромом, т.е. одинаково читается слева направо и справа налево. В ответе запишите в первом столбце таблицы первые пять найденных чисел в порядке возрастания, а во втором столбце – соответствующие им значения R. Количество строк в таблице для ответа избыточно.

Пусть S – сумма всех натуральных делителей целого числа. Если таких делителей у числа нет, то значение S считается равным нулю. Напишите программу, которая перебирает целые числа, большие 8 494 154, в порядке возрастания и ищет среди них такие, у которых есть ровно 4 различных натуральных делителя, а значение S является палиндромом (то есть читается слева-направо и справа- налево одинаково).

В ответе запишите в первом столбце таблицы первые 5 найденных чисел в порядке воз- растания, a во втором столбце – соответствующие им значения S. Например, для числа 20 S = 1 + 2 + 4 + 5 + 10 + 20 = 42.

Пусть M – сумма минимального и максимального простых натуральных делителей целого числа, не считая самого числа. Если таких делителей у числа нет, то значение M считается равным нулю.

Напишите программу, которая перебирает целые числа, большие 7 800 000, в порядке воз- растания и ищет среди них такие, для которых M больше 100 000 и является палиндромом, т.е. одинаково читается слева направо и справа налево. В ответе запишите в первом столб- це таблицы первые пять найденных чисел в порядке возрастания, а во втором столбце – соответствующие им значения M.

Например, для числа 298 M = 2 + 149 = 151.

Пусть M – сумма минимального и максимального простых натуральных делителей целого числа, не считая самого числа. Если таких делителей у числа нет, то значение M считается равным нулю.

Напишите программу, которая перебирает целые числа, большие 5 800 000, в порядке воз- растания и ищет среди них такие, для которых М больше 80 000 и является палиндромом, т.е. одинаково читается слева направо и справа налево.

В ответе запишите в первом столбце таблицы первые пять найденных чисел в порядке возрастания, а во втором столбце – соответствующие им значения М. Например, для числа 298 M = 2 + 149 = 151.

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

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

I = 1     V = 5     X = 10    L = 50
C = 100   D = 500   M = 1000

• символы V, L, D никогда не повторяются;
• символы I, X, C, M могут повторяться не более 3 раз подряд;
• если меньшая цифра стоит слева от большей, её значение вычитается (только для пар IV, IX, XL, XC, CD, CM; вычитаемое не может быть меньше одной десятой уменьшаемого);
• если цифра стоит справа от большей или равной, их значения складываются;
• цифры в записи числа располагаются слева направо в порядке убывания их значений (за исключением случаев вычитания).

Например, римская запись MMXXVI корректна и обозначает число 2026.

Текстовый файл состоит из римских цифр I, V, X, L, C, D, M и знаков арифметических операций «+» и «−» (сложение и вычитание). Определите максимальное количество символов в непрерывной последовательности, которая является корректным арифметическим выражением с корректными римскими числами. В ответе укажите количество символов.

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

I = 1     V = 5     X = 10    L = 50
C = 100   D = 500   M = 1000

Символы I, X, C, M могут повторяться не более 3 раз подряд; комбинации для 4, 9, 40, 90, 400, 900 записываются «вычитанием» (IV, IX, XL, XC, CD, CM). Числа записываются слева направо от большего значения к меньшему. Если символ с меньшим значением стоит после символа с большим или равным значением, их значения складываются. Если символ с меньшим значением стоит перед большим, его значение вычитается, но только для комбинаций: I перед V или X (IV = 4, IX = 9); X перед L или C (XL = 40, XC = 90); C перед D или M (CD = 400, CM = 900).

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

1. Прибавь 2
2. Замени 1 на 3

Первая из этих команд увеличивает число на экране на 2. Вторая команда может применяться только к числу, в десятичной записи которого содержится хотя бы одна цифра «1», и действует, заменяя все цифры «1» в записи числа на цифры «3» (например, число 11 превратится в 33, а 21 - в 23).

Программа для исполнителя – это последовательность команд.

Сколько существует программ, для которых при исходном числе 10 результатом является число 44?

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

• добавить в одну из куч (по своему выбору) 3 камня;
• увеличить количество камней в одной из куч (по своему выбору) в 2 раза.

Например, пусть в одной куче 20 камней, а в другой — 30 камней; такую позицию обозначим (20, 30). Тогда за один ход можно получить любую из четырёх позиций: (23, 30), (20, 33), (40, 30), (20, 60). Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней.

Игра завершается в тот момент, когда суммарное количество камней в двух кучах становится не менее 173. Победителем считается игрок, сделавший последний ход, то есть первым получивший такую позицию, при которой в двух кучах суммарно 173 камней или больше. В начальный момент в первой куче 27 камней, во второй куче — S камней; 1 ≤ S ≤ 150.

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

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

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

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

Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может:

• добавить в одну из куч (по своему выбору) 4 камня;
• увеличить количество камней в одной из куч (по своему выбору) в 2 раза.

Например, пусть в одной куче 20 камней, а в другой 30 камней; такую позицию в игре обозначим (20, 30). Тогда за один ход можно получить любую из четырёх позиций: (24, 30), (20, 34), (40, 30), (20, 60).

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

В начальный момент в первой куче 28 камней, во второй куче – S камней; 1≤ S ≤ 153.

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

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

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

В ответе запишите два числа: сначала наименьшее значение S, затем наибольшее.

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

• добавить в одну из куч (по своему выбору) 3 камня;
• увеличить количество камней в одной из куч (по своему выбору) в 2 раза.

Например, пусть в одной куче 20 камней, а в другой — 30 камней; такую позицию обозначим (20, 30). Тогда за один ход можно получить любую из четырёх позиций: (23, 30), (20, 33), (40, 30), (20, 60). Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней.

Игра завершается в тот момент, когда суммарное количество камней в двух кучах становится не менее 173. Победителем считается игрок, сделавший последний ход, то есть первым получивший такую позицию, при которой в двух кучах суммарно 173 камней или больше. В начальный момент в первой куче 27 камней, во второй куче — S камней; 1 ≤ S ≤ 150.

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

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

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

В ответе запишите два числа: сначала наименьшее значение S, затем наибольшее.

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

Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может:

• добавить в одну из куч (по своему выбору) 4 камня;
• увеличить количество камней в одной из куч (по своему выбору) в 2 раза.

Например, пусть в одной куче 20 камней, а в другой 30 камней; такую позицию в игре обозначим (20, 30). Тогда за один ход можно получить любую из четырёх позиций: (24, 30), (20, 34), (40, 30), (20, 60).

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

В начальный момент в первой куче 28 камней, во второй куче – S камней; 1≤ S ≤ 153.

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

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

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

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

Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может:

• добавить в одну из куч (по своему выбору) 3 камня;
• увеличить количество камней в одной из куч (по своему выбору) в 2 раза.

Например, пусть в одной куче 20 камней, а в другой 30 камней; такую позицию в игре обозначим (20, 30). Тогда за один ход можно получить любую из четырёх позиций: (23, 30), (20, 33), (40, 30), (20, 60).

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

В начальный момент в первой куче 27 камней, во второй куче – S камней; 1≤ S ≤ 150.

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

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