Информатика

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

Для того, чтобы определить, какой участник может участвовать в каком дивизионе, планируется использовать рейтинг. Рейтинг каждого участника — целое число от \(0\) до \(5000\).

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

• Участники с рейтингом от \(0\) до \(1600\) имеют в качестве базового дивизиона третий.

• Участники с рейтингом от \(1601\) до \(1900\) имеют в качестве базового дивизиона второй.

• Участники с рейтингом более \(1900\) имеют в качестве базового дивизиона первый.

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

• Если соревнование проводится в базовом дивизионе участника, он участвует в своем дивизионе.

• Иначе участник может выбрать, в каком из доступных дивизионов он будет участвовать.

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

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

Формат входных данных
Первая строка ввода содержит целое число \(r\) "— рейтинг участника (\(0 \le r \le 5000\)).

Вторая строка ввода содержит от одного до трех различных символов. Каждый из этих символов равен 1, 2 или 3. Символы, которые встречаются во второй строке, показывают, в каких дивизионах проводится соревнование. Дивизионы перечислены в порядке возрастания номера, без пробелов.

Формат выходных данных
Выведите одну или более строк. Для каждого дивизиона, в котором участник сможет поучаствовать, выведите номер этого дивизиона. Если участник может принять участие в этом дивизионе только вне конкурса, выведите после номера дивизиона символ <<*>> (звездочка). Выводите дивизионы в порядке возрастания номера.

В этой задаче 35 тестов, каждый тест оценивается независимо, некоторые тесты оцениваются в 2, а некоторые в 3 балла.

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

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

Валентин выписывает натуральные числа, начиная с 1, в виде лестницы: на первой строке он пишет одно число, на второй — два, на третьей — три, и так далее.

1
2 3
4 5 6
7 8 9 10
...

После этого он стирает все числа на каждой строке, кроме первых \(k\). Если в строке меньше \(k\) чисел, он оставляет их все.

Заданы целые числа \(a\) и \(b\), а также число \(k\). Выведите строки с \(a\)-й по \(b\)-ю, которые получились у Валентина.

Формат входных данных

На ввод подаются три строки: первая содержит число \(a\), вторая содержит число \(b\), третья содержит число \(k\) (\(1 \le a \le b \le 10^9\), \(b - a \le 100\), \(1 \le k \le 100\)).

Формат выходных данных
Выведите строки с \(a\)-й по \(b\)-ю, которые получились у Валентина. Числа в строках разделяйте пробелами.

 

Целое число \(x\) называется свободным от квадратов, если нет такого целого числа \(y > 1\), что \(x\) делится на \(y^2\), то есть \(x = y^2z\) для некоторого целого \(z\).

Даны числа \(l\) и \(r\). Требуется найти число пар целых чисел \((a, b)\), таких что \(l \le a < b \le r\), и числа \(a\), \(b\), а также их произведение \(ab\) свободны от квадратов.

Формат входных данных
На вход подается две строки, первая содержит целое число \(l\), а вторая "— целое число \(r\) (\(1 \le l < r \le 10^9\), \(r - l \le 1000\)).

Формат выходных данных
Выведите одно целое число — искомое число пар.

Примечание
В примере подходят пары \(a = 3, b = 5\), \(a = 5, b = 6\). Число \(4\) не может входить в пару, так как \(4 = 2^2\cdot 1\), а пара \(a = 3, b = 6\) не подходит, так как \(ab = 3\cdot 6 = 18 = 3^2\cdot 2\).

Рассмотрим разбиения целого положительного числа \(n\) в сумму целых положительных чисел. Будем называть разбиение непростым, если слагаемые в нем упорядочены по неубыванию, причем среди слагаемых нет простых чисел.

Например, для \(n=5\) существует два непростых разбиения: \(1+1+1+1+1\) и \(1+4\).

Задано число \(n\). Выведите все его непростые разбиения на слагаемые.

Формат входных данных
На вход подается число \(n\) (\(1 \le n \le 70\)).

Формат выходных данных
Выведите все непростые разбиения \(n\) на слагаемые. Слагаемые разделяйте знаком <<+>>. Не выводите пробелы. Разбиения можно вывести в любом порядке.

Необходимо изобразить в текстовом формате перекресток двух дорог.

Изображение должно иметь размер \(n \times n\), ширина дорог должна быть \(l\). Центр перекрестка должен быть в центре изображения. Для клеток дороги следует использовать символ <<*>>, для клеток вне дороги символ <<.>>.

Формат входных данных
На первой строке дано целое число \(n\). На второй строке дано первое число \(l\). (\(3 \le n \le 100\), \(1 \le l < n\), \(l\) и \(n\) имеют одинаковую четность)

Формат выходных данных
Выведите \(n\) строк, изображение перекрестка.

Карта Карно - графический способ представления логической функции, составляемый для формирования минимизированной функции в аналитическом виде.
Для логической функции от четырёх переменных f(a, b, c, d) карта составляется следующим образом:

ab cd	00	01	11	10
00	f(0,0,0,0)	f(0,0,0,1)	f(0,0,1,1)	f(0,0,1,0)
01	f(0,1,0,0)	f(0,1,0,1)	f(0,1,1,1)	f(0,1,1,0)
11	f(1,1,0,0)	f(1,1,0,1)	f(1,1,1,1)	f(1,1,1,0)
10	f(1,0,0,0)	f(1,0,0,1)	f(1,0,1,1)	f(1,0,1,0)

После составления карты в ней выделяют "склейки" - прямоугольные области, удовлетворяющие
двум условиям:

• все значения истинны;
• размер области равен 2n, где n - любое натуральное число.

При этом считают, что первый и последний столбец, а также первая и последняя строки расположены "рядом", то есть в них также можно формировать склейки.
Цель формирования склеек - выделить как можно меньшее их число, для этого склейки должны иметь наибольший размер и могут накладываться друг на друга.
Для логической функции от четырёх переменных требуется составить карту Карно, в которой указать разными цифрами формируемые склейки: самые большие для этой функции (по 8 элементов) - цифрой 4, следующие по размеру (по 4 элемента) - цифрой 3, и т.д.

Входные данные
16 строк, составляющие полную таблицу истинности функции. В каждой строке через пробел записаны значения переменных a, b, c, d и значение функции f в виде нулей и единиц (0 - значение ложно, 1 - значение истинно).

Выходные данные
матрица из 4 строк по 4 цифры, записанных через пробел и соответствующих искомым значениям. Цифры могут принимать значения от 0 до 4.
 

Примеры

№	Входные данные	Выходные данные	Примечание
1	0 0 0 0 0 0 0 0 1 1 0 0 1 0 0 0 0 1 1 1 0 1 0 0 1 0 1 0 1 1 0 1 1 0 1 0 1 1 1 1 1 0 0 0 0 1 0 0 1 1 1 0 1 0 1 1 0 1 1 1 1 1 0 0 0 1 1 0 1 0 1 1 1 0 0 1 1 1 1 0	0 3 3 0 3 3 3 3 0 0 0 0 0 3 3 2	Для заданной функции выделяются склейки во 2-й строке и в квадрате в первой и последней строках по 4 элемента (обозначены цифрой 3), а также склейка из двух элементов в конце 4-й строки. Поскольку она накладывается на предыдущую склейку, то только второй элемент в ней обозначен цифрой 2.
2	0 0 0 0 1 0 0 0 1 1 0 0 1 0 0 0 0 1 1 0 0 1 0 0 1 0 1 0 1 1 0 1 1 0 1 0 1 1 1 1 1 0 0 0 0 1 0 0 1 0 1 0 1 0 0 1 0 1 1 0 1 1 0 0 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1	3 3 0 0 4 4 4 4 4 4 4 4 0 0 0 0	Для данной функции выделяется склейка во 2-й и 3-й строках, она состоит из 8 элементов и обозначается цифрой 4. Также выделяется квадрат из 4-х элементов (первые 2 в 1-й и 2-й строках), он накладывается на большую склейку, поэтому только его половина отмечена цифрой 3.

Для заданного в 10-й с/с дробного числа требуется определить разницу длин целой и дробной части этого числа в 5-й с/с при переводе с точностью до 8 разрядов.
Входные данные
положительное число в 10-й с/с, целая и дробная часть которого не превышают 8 разрядов каждая. Целая и дробная части разделяются точкой. Дробная часть может отсутствовать.
Выходные данные
неотрицательное целое число - разница между количеством разрядов целой и дробной части в пятеричной системе счисления.

Примеры

№	Входные данные	Выходные данные	Примечание
1	8.4	1	8.410=13.25, количество разрядов целой части на 1 больше, чем дробной
2	1.5	7	1.510=1.(2)5=1.222222225, в 5-й с/с дробь не имеет конечного представления, поэтому ограничиваем длину 8 дробными разрядами

Два узла, находящиеся в разных подсетях, имеют IP-адреса 192.168.144.183 и 192.168.249.39. В масках обеих подсетей одинаковое количество единиц. Укажите наименьшее возможное значение третьего слева байта этой маски. Ответ запишите в виде десятичного числа

Два узла, находящиеся в разных подсетях, имеют IP-адреса 243.171.13.52 и 243.171.22.4. В масках обеих подсетей одинаковое количество единиц. Укажите наименьшее возможное значение третьего слева байта этой маски. Ответ запишите в виде десятичного числа

Два узла, находящиеся в разных подсетях, имеют IP-адреса 169.46.190.43 и 169.46.95.229. В масках обеих подсетей одинаковое количество единиц. Укажите наименьшее возможное значение третьего слева байта этой маски. Ответ запишите в виде десятичного числа

Для узла c IP-адресом  253.189.9.182 адрес подсети равен 253.189.8.0. Сколько существует различных возможных значений третьего слева байта маски, если известно, что в этой сети не менее 100 узлов? Ответ запишите в виде десятичного числа.

Для узла c IP-адресом 166.208.9.201 адрес подсети равен 166.208.8.0. Сколько существует различных возможных значений третьего слева байта маски, если известно, что в этой сети не менее 1000 узлов? Ответ запишите в виде десятичного числа.

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

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

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