Информатика

Текстовый файл состоит из символов T, U, V, W, X, Y и Z.
Определите в прилагаемом файле максимальное количество идущих подряд символов (длину непрерывной подпоследовательности), среди которых символ X встречается не более 140 раз.
Для выполнения этого задания следует написать программу.
 

Текстовый файл состоит из символов T, U, V, W, X, Y и Z.
Определите в прилагаемом файле минимальное количество идущих подряд символов (длину непрерывной подпоследовательности), среди которых символ W встречается не менее 240 раз.
Для выполнения этого задания следует написать программу.
 

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

Формат входных данных
Программа получает на вход строку с кодом.  Части кода разделены пробелом.
Каждый фрагмент кода это либо: 
nl означает NewLine (переход на новую строку)
либо 
Количество символа и какой символ
В качестве символов может быть любой печатаемый символ ASCII кода (до символа с кодом 127) либо специальные символы, закодированные следующим образом:
sp - пробел
bS - бэкслеш \
sQ - апостроф '
Количество символа - натуральное число, не превышающее 100.

Формат выходных данных 
Выведите получившуюся картинку.

У исполнителя Калькулятор имеются четыре команды, которые обозначены латинскими буквами:
A. Вычесть 1
B. Вычесть 5
C. Прибавить 7
D. Умножить на 2
Найдите количество существующих программ, для которых при исходном числе 9 результатом является число 84, и при этом траектория вычислений содержит хотя бы одно из чисел 30 или 60 и не содержит чисел, оканчивающихся на 3, а программа не содержит двух команд вычитания подряд.
 

Кай работает в лаборатории изучения массивов, он экспериментирует с двумя массивами натуральных чисел: \(A = [a_1, a_2, \ldots, a_n]\) длины \(n\) и \(B = [b_1, b_2, \ldots, b_m]\) длины \(m\).

Эксперимент, который проводит Кай, устроен следующим образом. У каждого из массивов отбрасывается произвольный, возможно пустой, префикс, а также произвольный, возможно пустой, суффикс, таким образом, чтобы оставшиеся части массивов имели равную длину. Обозначим получившиеся массивы как \(A'\) и \(B'\), а их длину как \(k\). Затем Кай суммирует поэлементно получившиеся массивы, итоговый массив Кай обозначает как \(C = [c_1, c_2, \ldots, c_k]\).

Пусть, например, \(n = 5\), \(A = [4, 3, 3, 2, 1]\), \(m = 6\), \(B = [4, 1, 5, 1, 3, 2]\), от массива \(A\) отбрасывается первый и последний элемент, от массива \(B\) три первых. После этого массивы имеют вид \(A' = [3, 3, 2]\), \(B' = [1, 3, 2]\), результат их поэлементного суммирования \(C = [4, 6, 4]\).

Задача Кая заключается в том, чтобы получать такие \(C\), которые являются массивами-палиндромами, то есть если числа на первой и последней позиции совпадают, числа на второй и предпоследней позиции совпадают, и так далее, для всех \(i\) числа на позициях \(i\) и \(k - i + 1\) совпадают.

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

Формат входных данных
В первой строке ввода даны два целых числа \(n\) и \(m\) — количество элементов в первом и во втором массиве, соответственно (\(1 \leqslant n, m \leqslant 100\,000\)).

Во второй строке ввода даны \(n\) целых чисел \(a_{i}\) — массив \(A\) (\(1 \leqslant a_i \leqslant 100\)).

В третьей строке ввода даны \(m\) целых чисел \(b_{j}\) — массив \(B\) (\(1 \leqslant b_j \leqslant 100\)).

Формат выходных данных
Выведите единственное целое число — максимальное \(k\), что Кай в результате эксперимента может получить массив-палиндром длины \(k\).

 

Текстовый файл состоит не более чем из 10⁷ символов и содержит только заглавные буквы A, B, C, D. Определите максимальную длину подстроки, состоящей из идущих групп символов ABCD в указанном порядке. При этом в начале и конце искомой последовательности группа символов ABCD может быть неполной. Искомая подстрока должна содержать не менее одной полной группы символов ABCD.

Например, условию задачи удовлетворяют: BCDABCDABCDA, DABCDABCDAB

Для выполнения этого задания следует написать программу. 

Теплым весенним днем группа из N школьников-программистов гуляла в окрестностях города Кисловодска. К несчастью, они набрели на большую и довольно глубокую яму. Как это случилось — непонятно, но вся компания оказалась в этой яме.

Глубина ямы равна H. Каждый школьник знает свой рост по плечи h_i и длину своих рук l_i. Таким образом, если он, стоя на дне ямы, поднимет руки, то его ладони окажутся на высоте h_i + l_i от уровня дна ямы. Школьники могут, вставая друг другу на плечи, образовывать вертикальную колонну. При этом любой школьник может встать на плечи любого другого школьника. Если под школьником i стоят школьники j₁, j₂, …, j_k, то он может дотянуться до уровня h_j1 + h_j2 + … + h_jk + h_i + l_i.

Если школьник может дотянуться до края ямы (то есть h_j1 + h_j2 + … + h_jk + h_i + l_i ≥ H), то он может выбраться из нее. Выбравшиеся из ямы школьники не могут помочь оставшимся.

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

Формат входных данных
В первой строке входных данных задается натуральное число N (1 ≤ N ≤ 2000) — количество школьников, попавших в яму.

Далее в N строках содержится по два целых числа: рост i-го школьника по плечи h_i (1 ≤ h_i ≤ 10⁵) и длина его рук l_i (1 ≤ l_i ≤ 10⁵).

В последней строке указано целое число — глубина ямы H (1 ≤ H ≤ 10⁵).

Формат выходных данных
В первой строке выведите K — максимальное количество школьников, которые смогут выбраться из ямы. Если K > 0, то во второй строке в произвольном порядке выведите их номера, разделяя их пробелами. Школьники нумеруются с единицы в том порядке, в котором они заданы во входных данных. Если существует несколько решений, выведите любое.

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

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

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч {1} либо увеличить количество камней в куче в два раза. Для того, чтобы делать ходы, у каждого игрока есть неограниченное количество камней. 
Игра завершается в тот момент когда суммарное количество камней в кучах становится не менее {2}. 
Победителем считается игрок, сделавший последний ход, т.е. первым получивший суммарно в кучах {2} или больше камней.
В начальный момент в первой куче было {3} камней, во второй - S камней; 1 <= S <= {4}.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. 

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

Задание 20
Найдите два наименьших значения S, при которых у Пети есть выигрышная стратегия, причем одновременно выполняются два условия: 
- Петя не может выиграть за один ход;
- Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня. 
 Найденные значения запишите в порядке возрастания.

Задание 21
Найдите минимальное значение S, при котором одновременно выполняются два условия: 
- У Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом, при любой игре Пети;
- У Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом. 
 Если найдено несколько значений S, в ответе укажите наименьшее из них.


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

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

Далекая страна содержит \(n\) городов, соединенных \(n - 1\) дорогами, при этом из любого города можно добраться до любого другого по дорогам страны.

Известно, что каждый город относится ровно к одной провинции. Город \(v\) относится к провинции \(t_v\). Обратите внимание, что конкретная провинция может являться любым подмножеством городов, и возможно из одного города провинции нельзя добраться до другого этой же провинции, проходя только через города этой провинции. Столицей является город номер \(1\).

Банда разбойников собирается грабить караваны, которые будут идти через города страны. У каждого города есть коэффициент того, насколько удобно в нем грабить. В городе \(v\) он равен \(c_v\).

Вам приходят запросы двух типов:

1. Изменить провинцию, к которой относится город \(v\), на \(t_{new}\)

2. В \(k\) городах с номерами \(a_1, a_2, \ldots, a_k\) появляется по одному каравану, которые идут в столицу (город с номером 1) по кратчайшему пути. Разбойники выбирают один город, который находится в провинции \(t\), после чего грабят все караваны, которые пройдут через этот город. Если разбойники ограбят караваны в городе с номером \(v\), то они получат \(c_v \cdot num_v\), где \(c_v\) — коэффициент города \(v\), а \(num_v\) это количество караванов, проходящих через этот город.

Определите максимальный ущерб, равный количеству награбленного разбойниками, для каждого запроса второго типа. Если в провинции, указанной в запросе, нет ни одного города, то ответ на этот запрос равен \(0\).

Формат входных данных
В первой строке даны два целых числа \(n\) и \(q\) (\(2 \le n \le 200\,000, 1 \le q \le 200\,000\)) — количество городов и количество запросов.

Во второй строке дано \(n - 1\) целое число \(p_2, p_3, \ldots, p_n\) (\(1 \le p_i < i\)), где число \(p_i\) означает, что существует дорога между городами \(i\) и \(p_i\).

В третьей строке дано \(n\) целых чисел \(t_1, t_2, \ldots, t_n\) (\(1 \le t_i \le n\)) — номера провинций у городов.

В четвертой строке дано \(n\) целых чисел \(c_1, c_2, \ldots, c_n\) (\(1 \le c_i \le 10^9\)) — коэффициенты успешности грабежа.

Далее идет \(q\) строк описаний запросов. В начале каждой строки дано одно целое число \(x_i\) (\(1 \le x_i \le 2\)) — тип запроса.

1. Если \(x_i = 1\), то далее идет два целых числа \(v\) и \(t_{new}\) (\(1 \le v, t_{new} \le n\)) — номер города, у которого меняется провинция, и номер его новой провинции.

2. Если \(x_i = 2\), то далее идут целые числа \(t\) и \(k\), и \(k\) целых чисел \(a_1, a_2, \ldots, a_k\) (\(1 \le t, k, a_i \le n\)) — номер провинции, в городе которой можно грабить; количество городов, из которых выходят караваны; и номера городов, из которых входят караваны. Гарантируется, что в одном запросе все \(a_i\) различны. Также гарантируется, что сумма \(k\) по всем запросам второго типа не превышает \(200\,000\).

Формат выходных данных
На каждый запрос второго типа выведите одно число — максимальное число, которое разбойники смогут получить. Если в провинции, указанной в запросе, нет ни одного города, то ответ на этот запрос равен \(0\).

Примечание
В первом запросе караваны идут из городов с номерами \(3\) и \(4\) и нужно ограбить их в городе из третьей провинции. Это те же самые города с номерами \(3\) и \(4\), через каждый из которых пройдет по одному каравану. Поэтому разбойники ограбят караваны в третьем городе и получат \(c_3 \cdot 1 = 10 \cdot 1 = 10\).

Во втором запросе караваны также идут из городов с номерами \(3\) и \(4\), но теперь нужно ограбить их в городе из первой провинции. В первой провинции находятся города \(1\) и \(2\), через каждый из которых пройдет два каравана. Среди них разбойники выбирают город \(2\), потому что \(c_2 > c_1\) и ответ на этот запрос равен \(c_2 \cdot 2 = 3 \cdot 2 = 6\).

В третьем провинция для города \(3\) изменяется на \(1\).

В четвертом запросе караваны снова идут из городов с номерами \(3\) и \(4\), и нужно ограбить караваны в городе из первой провинции. То есть разбойники могут ограбить караваны в одном из городов с номерами \(1, 2\) или \(3\). Через города с номерами \(1\) и \(2\) пройдет два каравана, а через город \(3\) только один. Разбойникам выгодно ограбить караваны в городе \(3\) и получить \(c_3 \cdot 1 = 10 \cdot 1 = 10\).

Карта Карно - графический способ представления логической функции, составляемый для формирования минимизированной функции в аналитическом виде.
Для логической функции от четырёх переменных 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.

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

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

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

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

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

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

Текстовый файл состоит не более чем из 10⁶ символов и содержит только заглавные буквы латинского алфавита. Определите максимальную длину подстроки, в которой символ Y встречается не более 150 раз.