Информатика

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

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

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

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

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

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

В терминологии сетей TCP/IP маской сети называют двоичное число, которое показывает, какая часть IP-адреса узла сети относится к адресу сети, а какая – к адресу узла в этой сети. Адрес сети получается в результате применения поразрядной конъюнкции к заданному адресу узла и его маске. Сеть задана IP-адресом одного из узлов 120.28.107.148 и сетевой маской 255.255.224.0. Чему равно наибольший IP-адрес, который можно назначить компьютеру в данной сети. В ответе укажите данный адрес без разделителей. Например, IP-адрес 88.28.87.148 необходимо в ответе записать как 882887148

При регистрации в компьютерной системе каждому пользователю выдаётся пароль, содержащий только символы из 1387-символьного набора специального алфавита. В базе данных для хранения каждого пароля отведено одинаковое и минимально возможное целое число байт, при этом используется посимвольное кодирование паролей, все символы кодируются одинаковым и минимально возможным количеством бит. Кроме пароля, для каждого пользователя в системе хранятся дополнительные данные, для которых выделено 729 байт. Известно, что для хранения данных о 329 пользователях потребовалось менее 263 Кбайт. Определите максимально возможную длину пароля (количество символов). В ответе запишите только целое число.

На предприятии каждой изготовленной детали присваивают серийный номер, содержащий символы из 200-символьного алфавита. В базе данных для хранения каждого серийного номера отведено одинаковое и минимально возможное целое число байт, при этом используется посимвольное кодирование номеров, все символы кодируются одинаковым и минимально возможным количеством бит. Известно, что для хранения 5000 серийных номеров выделено не более 1 Мбайт памяти. Определите максимально возможную длину серийного номера. В ответе запишите только целое число.

На предприятии каждой изготовленной детали присваивают серийный номер, содержащий только символы из специального алфавита. В базе данных для хранения каждого серийного номера отведено одинаковое и минимально возможное целое число байт, при этом используется посимвольное кодирование номеров, все символы кодируются одинаковым и минимально возможным количеством бит. Известно, что серийные номера имеют длину 512 символов, для хранения 2048  номеров выделено не менее 1000 Кбайт памяти. Определите, минимальную мощность специального алфавита, из которого формируются серийные номера. В ответе запишите только целое число.

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

?	?	?	?	F
		1		1
	1	0		1
1	0			1

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

(Досрочный ЕГЭ-2025) В файле электронной таблицы 9-255.xls в каждой строке записаны семь натуральных чисел.  Определите количество строк таблицы, содержащих числа, для которых выполнены оба условия:
– в строке есть два числа, которые повторяются трижды, одно число без повторений;
– наибольшее из повторяющихся чисел больше неповторяющегося числа.
В ответе запишите только число.
 

В файле электронной таблицы 9-253.xls в каждой строке записаны семь натуральных чисел.  Найдите строки таблицы, для которых выполнены следующие условия:
–    в строке есть ровно два числа, каждое из которых повторяется трижды, и одно число без повторений;
–    среднее арифметическое повторяющихся чисел строки меньше неповторяющегося числа. 
Из каждой такой строки выберите неповторяющееся число и найдите сумму этих чисел. В ответе запишите одно число.
 

В файле электронной таблицы 9-249.xls в каждой строке записаны шесть натуральных чисел. Определите количество строк таблицы, содержащих числа, для которых выполнены следующие условия:
– в строке есть число, повторяющееся не меньше трёх раз;
– в строке есть число, не повторяющееся в этой строке;
– среднее арифметическое всех повторяющихся чисел строки (с учётом количества повторений) меньше среднего арифметического неповторяющихся чисел этой строки. В ответе запишите только число.
 

В файле электронной таблицы 9-249.xls в каждой строке записаны шесть натуральных чисел. Определите количество строк таблицы, содержащих числа, для которых выполнены следующие условия:
– в строке есть число, повторяющееся не меньше трёх раз;
– в строке есть число, не повторяющееся в этой строке;
– среднее арифметическое всех повторяющихся чисел строки (с учётом количества повторений) больше среднего арифметического неповторяющихся чисел этой строки. В ответе запишите только число.

В файле 17-418.txt содержится последовательность натуральных чисел, не превышающих 10000. Определите количество пар, для которых выполняются следующие условия:
– остаток от деления на 3 хотя бы одного числа из пары равен остатку от деления на 11 максимального элемента всей последовательности;
– остаток от деления на 11 хотя бы одного числа из пары равен остатку от деления на 3 минимального элемента всей последовательности.
В ответе запишите два числа: сначала количество найденных пар, затем максимальную величину суммы элементов таких пар. В данной задаче под парой подразумевается два идущих подряд элемента последовательности.

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может:
– добавить в кучу 3 камня;
– добавить в кучу 6 камней;
– увеличить количество камней в куче в 3 раза. Например, из кучи в 20 камней за один ход можно получить кучу из 23, 26 или 60 камней. Игра завершается, когда количество камней в куче становится не менее 132. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 132 или больше камней. В начальный момент в куче было S камней, 1 ≤ S ≤ 131. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
Задание 19.
Укажите минимальное значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом.
Задание 20.
Найдите два наименьших значения S, когда Петя имеет выигрышную стратегию, причём одновременно выполняются два условия:
– Петя не может выиграть за один ход;
– Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Найденные значения запишите в ответе в порядке возрастания.
Задание 21
Найдите минимальное значение S, при котором одновременно выполняются два условия:
– у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом. 


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

Злым числом в математике называется неотрицательное целое число с чётным числом единиц в его двоичной записи (например, число 5 — злое, в его двоичной записи две единицы). Они используются в теории чисел при исследовании последовательности Морса–Туэ и применяются в алгоритмах фрактального сжатия изображений. Натуральное число будем называть очень злым, если само оно чётное и количество единиц в его двоичной записи также чётное. Это такие числа, как 6, 10, 12, 18, 20 и так далее. По данному n определите количество очень злых чисел, не превосходящих n.

Формат входных данных
Единственная строка входного файла содержит натуральное число n (1 ≤ n ≤ 10⁹ ).

Формат выходных данных
Выведите одно неотрицательное целое число — количество очень злых натуральных чисел, не превосходящих n.

На столе у большого начальника лежит стопка из N заявлений, пронумерованных сверху вниз от 1 до N. Первое заявление он подписывает и убирает из стопки, второе — выбрасывает в мусорную корзину, третье — кладёт вниз стопки. Далее процесс продолжается аналогично, пока заявления в стопке не закончатся. Определите, будет ли заявление с номером K подписано или выброшено, а также номер шага, на котором это произойдёт. Одним шагом является каждая из трёх операций, описанных выше.

Формат входных данных
Первая строка входных данных содержит целое число N, вторая строка — целое число K (1 ≤ N ≤ 10⁹ , 1 ≤ K ≤ N).
Формат выходных данных
В первой строке выведите «Yes», если заявление с номером K будет подписано, и «No», если оно будет выброшено. Во второй строке выведите номер шага, на котором это произойдёт.

Замечание
В первом примере из условия в стопке находятся 4 заявления: (1, 2, 3, 4). Заявление 1 подписывается, заявление 2 выкидывается, заявление 3 перекладывается в конец. После выполнения трёх шагов в стопке будут заявления (4, 3). Поэтому на пятом шаге заявление 3 будет выброшено.
Во втором примере из условия стопка имеет вид (1, 2, 3, 4, 5). После выполнения трёх шагов стопка будет иметь вид (4, 5, 3). За следующие три шага заявление 4 будет подписано, заявление 5 будет выброшено, а заявление 3 — переложено в конец стопки (в которой ничего не будет, кроме заявления 3). Поэтому после шести шагов стопка будет иметь вид (3). На седьмом шаге заявление 3 будет подписано.

Тимофею на день рождения родители подарили металлоискатель. Естественно, наутро мальчик отправился на поиски клада. Он предположил, что когда-то давно кто-то мог обронить золотую монету на древней прямой дороге и для облегчения поиска придумал систему координат. Ось абсцисс OX направлена вдоль дороги, а ось ординат OY направлена вверх.
Устройство работает следующим образом: на его индикаторе выставляется натуральное число r и если ровно на этом расстоянии имеется золотой предмет, то загорается зелёная лампочка.
Сначала юный кладоискатель выставил число r1 в точке x = 0, затем отошёл в точку с абсциссой x = a и выставил число r2, как показано на рисунке. Новичкам везёт, оба раза загорелась зелёная лампочка. Определите координаты потерянной когда-то давно золотой монетки.

Формат входных данных
Программа получает на вход три целых числа a, r1 и r2, записанных в отдельных строках (1 ≤ a, r₁, r₂ ≤ 10⁹ ).
Формат выходных данных
Выведите в двух строках два числа – координаты сокровища (сначала — абсциссу, потом — ординату). Значение ординаты должно быть не положительным (монетка не может висеть в воздухе). Гарантируется, что входные данные таковы, что ответ существует и обе координаты монеты будут целыми числами.

Замечание
Рисунок соответствует примеру из условия.

Родители Лизы подключили пакет, содержащий N телевизионных каналов, пронумерованных числами от 1 до N. Переключать каналы можно с помощью двух кнопок на пульте: «+» и «−». Короткое нажатие на кнопку «+» приведёт к переключению на следующий канал, если номер текущего канала меньше N; если же номер текущего канала равен N, то телевизор продолжит показывать этот канал. Если кнопку «+» нажать и удерживать некоторое время, произойдёт переход на K каналов вперёд, при условии, что номер текущего канала не превосходит N − K. В противном случае произойдёт переход на канал N.
Аналогично, короткое нажатие на кнопку «−» приведёт к переключению на предыдущий канал, если номер текущего канала больше 1; если же номер текущего канала равен 1, телевизор продолжит показывать этот канал. Если кнопку «−» нажать и удерживать некоторое время, то произойдёт переход на K каналов назад при условии, что номер текущего канала превышает K. В противном случае произойдёт переход на канал 1.
Лиза включила телевизор и обнаружил, что он показывает канал P. Лиза знает, что очень скоро по каналу с номером U начнётся интересная передача. Определите, какое минимальное количество нажатий на кнопки пульта потребуется сделать Лизе, чтобы переключиться на канал U.
Формат входных данных
В первой строке содержится целое число N (3 ≤ N ≤ 10⁹ ) — количество телевизионных каналов.
Во второй строке содержится целое число K (2 ≤ K < N) — количество каналов, на которое осуществится переход назад или вперёд при удерживании соответствующей кнопки переключения.
В третьей строке содержится целое число P (1 ≤ P ≤ N) — номер канала, который показывает телевизор.
В четвёртой строке содержится целое число U (1 ≤ U ≤ N) — номер канала, на который желает переключиться Лиза. Гарантируется, что P = U.
Формат выходных данных
Выведите одно целое неотрицательное число — минимальное количество нажатий на кнопки пульта, которое необходимо для переключения с канала P на канал U.

Замечание
В первом примере Лизе следует сначала выполнить одно короткое нажатие на кнопку «+» и переключиться с канала 3 на канал 4, а затем трижды осуществить переход вперёд на 5 каналов: сначала переключиться с 4 на 9, затем с 9 на 14 и, наконец, с 14 на 19 канал.
Во втором примере Лиза может сначала переключиться коротким нажатием на кнопку «−» на канал 2, после чего выполнить три перехода вперёд на 5 каналов: с канала 2 на канал 7, затем на канал 12 и, наконец, на канал 17.
В третьем примере Лиза дважды выполнит короткое нажатие кнопки «−».
В четвёртом примере Лизе нужно сначала перейти назад, на канал 1, после чего трижды выполнить переход вперёд, последовательно на каналы 6, 11, 16.

Шоколад помогает развивать ум и укреплять дух! Старец Летовец после своих занятий угощает своих учеников шоколадом. На следующем занятии у него будет M учеников и каждому из них Старец хочет дать по одной плитке шоколада.

Чтобы купить нужное количество шоколада, старец отправил своего праправнука Летовёнка разузнать, какое минимальное количество денег ему понадобится.
Оказывается, каждый магазин продаёт шоколад по разной цене. В i-м магазине можно купить не более Bi​ плиток шоколада по цене Аi​ рублей за плитку. Летовец хочет потратить как можно меньше денег, но при этом купить ровно M плиток шоколада. 

Помогите Летовёнку посчитать какую минимульную сумму на шоколад потратит старец Летовец. 

Формат входных данных
В первой строке заданы два числа: N и M (1 <= N, M <= 10⁵). Следующие N строк содержат по 2 числа: Ai (1 <= A_i <= 10⁹) и Bi (1 <= В_i <= 10⁵). \(B_1 + B_2 +... + B_N >= M\).


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

Примеры

№	Входные данные	Выходные данные
1	2 5 4 9 2 4	12
2	4 30 6 18 2 5 3 10 7 9	130
3	1 100000 1000000000 100000	100000000000000

Летовецкие числа — это положительные целые числа, которые делятся на a, b или c.

Напишите программу, которая находит n-е по счёту летовецкое число.

Формат входных чисел
Программа получает на вход четыре целых положительных числа n, a, b, и c. Каждое число записано в отдельной строке. 
Ограничения на входные данные

• 1 <= n, a, b, c <= 109
• 1 <= a * b * c <= 1018
• Гарантируется, что результат находится в диапазоне [1, 2 * 109].

Формат выходных чисел
Ваша программа должны вывести одное число -  n-е по счёту летовецкое число.