Информатика

Дано неориентированное дерево "— связный граф из \(n\) вершин без циклов, и число \(k\). Зафиксируем некоторую вершину \(s\) дерева и назовем ее столицей.

Ориентируем ребра дерева в направлении от столицы. Иными словами, ориентируем ребро \((u, v)\) в направлении \(u \to v\), если при подвешивании дерева за вершину \(s\) вершина \(u\) является родителем вершины \(v\). Заметим, что при таком ориентировании ребер каждая вершина достижима из столицы.

Определим расстояние до вершины \(v\) графа как минимальное количество ребер на пути из \(s\) в \(v\). Назовем доступностью вершины \(s\) максимальное из расстояний до всех вершин.

Разрешается добавить в дерево не более \(k\) дополнительных ориентированных ребер.

Для каждой вершины \(s\) дерева определите, какой минимальной доступности можно достичь, если выбрать вершину \(s\) в качестве столицы.

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

Формат входных данных
Первая строка содержит три целых числа \(n\), \(k\) и \(t\) (\(2 \le n \le 2 \cdot 10^5\), \(1 \le k \le n - 1\), \(n \cdot k \le 2 \cdot 10^5\), \(0 \le t \le 1\)) — количество вершин дерева, ограничение на максимальное количество добавленных ребер и число \(t\), равное \(0\), если нужно вывести ответ только для вершины с номером \(1\), и равное \(1\) иначе.

Каждая из следующих \(n - 1\) строк содержит два целых числа \(u_i, v_i\) (\(1 \le u_i, v_i \le n\)) — ребра дерева.

Гарантируется, что заданные ребра образуют дерево.

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

В случае, если \(t = 0\), выведите единственное целое число: минимальную доступность, которую можно достичь, выбрав вершину с номером \(1\) в качестве столицы, и добавив не более \(k\) дополнительных ориентированных ребер.

В случае, если \(t = 1\), выведите \(n\) чисел: \(i\)-е число равняется минимальной доступности, которую можно достичь, выбрав вершину \(i\) в качестве столицы, и добавив не более \(k\) дополнительных ориентированных ребер.

На рисунке приведены иллюстрации к первому примеру. Пунктирными линиями обозначены добавленные ребра. Для вершин \(1\) и \(2\) минимальная доступность равняется \(1\), а для вершин \(3\), \(4\) и \(5\) минимальная доступность равняется 2.

Последовательность \([b_1, b_2, \ldots, b_k]\) называется битонической, если выполнены неравенства \(b_1 < b_2 < \ldots < b_i > \ldots > b_k\) для некоторого \(1 \le i \le k\).

Например, последовательности \([1]\), \([1, 2, 3, 2]\), \([1, 4, 10]\), \([3, 2]\) являются битоническими, а последовательности \([1, 1]\), \([2, 1, 3]\) — нет.

Задана последовательность \([a_1, a_2, \ldots, a_n]\). Требуется количество пар \((l, r)\) таких, что \(1 \le l \le r \le n\) и последовательность \([a_l, a_{l+1}, \ldots, a_r]\) является битонической.

Формат входных данных
Первая строка ввода содержит число \(n\) (\(1 \leq n \leq 300\,000\)).

Вторая строка ввода содержит \(n\) целых чисел: \(a_1, a_2, \ldots, a_n\) (\(1 \leq a_i \leq n\)).

Формат выходных данных
Выведите одно число — количество пар \((l, r)\), таких, что \(1 \le l \le r \le n\) и последовательность \([a_l, a_{l+1}, \ldots, a_r]\) является битонической.

В первом примере подходят следующие пары:

• \((1, 1)\), последовательность \([1]\)

• \((2, 2)\), последовательность \([1]\)

• \((2, 3)\), последовательность \([1, 2]\)

• \((2, 4)\), последовательность \([1, 2, 3]\)

• \((2, 5)\), последовательность \([1, 2, 3, 1]\)

• \((3, 3)\), последовательность \([2]\)

• \((3, 4)\), последовательность \([2, 3]\)

• \((3, 5)\), последовательность \([2, 3, 1]\)

• \((4, 4)\), последовательность \([3]\)

• \((4, 5)\), последовательность \([3, 1]\)

• \((5, 5)\), последовательность \([1]\)

В самолетах авиакомпании Битавиа кресла расположены в \(n\) рядов, при этом в каждом ряду по шесть мест, между третьим и четвертым местом находится проход. Некоторые пассажиры регистрируются заранее онлайн, другие пассажиры регистрируются на стойке регистрации в аэропорту.

При онлайн-регистрации пассажир может выбрать любое место и не может его затем менять. Например, при \(n = 6\) рассадка в самолете после онлайн-регистрации может выглядеть так (крестиками отмечены занятые места):

На стойку регистрации придут \(m\) пассажиров. По правилам Битавиа нужно рассадить их в самолете таким образом, чтобы итоговая рассадка в самолете была симметрична относительно прохода. То есть, если в некотором ряду на первом кресле сидит пассажир, то в том же ряду на шестом кресле тоже должен сидеть пассажир. То же самое справедливо для второго и пятого, третьего и четвертого кресел, соответственно. При этом пересаживать пассажиров, прошедших онлайн-регистрацию нельзя. В исходную рассадку, показанную на рисунке выше, можно добавить семь пассажиров, удовлетворив условие симметрии, например, следующим образом:

Вам дана рассадка пассажиров после онлайн-регистрации. Требуется рассадить \(m\) пассажиров так, чтобы итоговая рассадка в самолете была симметрична относительно прохода, или определить, что это невозможно.

Формат входных данных
В первой строке содержатся два целых числа \(n\) и \(m\) — количество рядов в самолете и количество пассажиров, которые придут на стойку регистрации (\(1 \le n \le 1000\), \(0 \le m \le 6000\)).

В следующих \(n\) строках задана изначальная рассадка в самолете после онлайн-регистрации. В каждой строке содержится по шесть символов, при этом \(i\)-й символ \(j\)-й строки равен <<X>> (заглавная английская X), если \(i\)-е место в \(j\)-м ряду уже занято и <<.>> (точка) иначе.

Формат выходных данных
Если искомой рассадки не существует, выведите <<Impossible>>.

Иначе выведите \(n\) строк по шесть символов — итоговую рассадку в самолете. При этом \(i\)-й символ \(j\)-й строки должен быть равен <<X>>, если место занято, и <<.>>, если свободно. Если существует несколько решений, разрешается вывести любое.

Ниже приведены пять примеров входных данных.

1. В первом примере \(m = 0\), а рассадка в самолете симметрична, поэтому итоговая рассадка совпадает с исходной.

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

3. В третьем примере существовало бы решение, при \(m = 1\), но при \(m = 2\) не существует способа рассадить всех пассажиров симметрично.

4. В четвертом примере требуется рассадить больше пассажиров чем свободных мест в самолете.

5. Пятый примере соответствует ситуации, рассмотренной на рисунках в тексте условия. В этом примере существует несколько решений, приведено одно из них.

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

Формат входных данных
Сначала вводится размер ноги покупателя (обувь меньшего размера он надеть не сможет), затем количество пар обуви в магазине и размер каждой пары. Размер — натуральное число, не превосходящее 100, количество пар обуви в магазине не превосходит 1000.

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

Наши люди до метро на такси не ездят!

После затянувшегося совещания директор фирмы решил заказать такси, чтобы развезти сотрудников по домам. Он заказал N машин — ровно столько, сколько у него сотрудников. Однако когда они подъехали, оказалось, что у каждого водителя такси свой тариф за 1 километр.

Директор знает, какому сотруднику сколько километров от работы до дома (к сожалению, все сотрудники живут в разных направлениях, поэтому нельзя отправить двух сотрудников на одной машине). Теперь директор хочет определить, какой из сотрудников на каком такси должен поехать домой, чтобы суммарные затраты на такси (а их несет фирма) были минимальны.

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

Сначала во входном файле записано натуральное число N (1 ≤ N ≤ 1000) — количество сотрудников компании (совпадающее с количеством вызванных машин такси). Далее записано N чисел, задающих расстояния в километрах от работы до домов сотрудников компании (первое число — для первого сотрудника, второе — для второго и т.д.). Все расстояния — положительные целые числа, не превышающие 1000. Далее записано еще N чисел — тарифы за проезд одного километра в такси (первое число — в первой машине такси, второе — во второй и т.д.). Тарифы выражаются положительными целыми числами, не превышающими 10000.

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

В выходной файл выведите N чисел. Первое число — номер такси, в которое должен сесть первый сотрудник, второе число — номер такси, в которое должен сесть второй и т.д., чтобы суммарные затраты на такси были минимальны. Если вариантов рассадки сотрудников, при которых затраты минимальны, несколько, выведите любой из них.

 

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

Упорядочите список участников олимпиады в порядке убывания набранных баллов.

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

Формат входных данных
Выведите список участников (только фамилии) в порядке убывания набранных баллов.

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

Формат входных данных
Вводится натуральное четырехзначное число.

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

У Ани есть клетчатый листок бумаги, на котором она нарисовала прямоугольник размером \(m \times n\).

После этого она раскрасила клетки прямоугольника, которые лежат на его границе.

Сколько клеток раскрасила Аня?

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

На первой строке ввода задано целое число \(m\) (\(1 \le m \le 10^8\)).

На второй строке ввода задано целое число \(n\) (\(1 \le n \le 10^8\)).

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

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

Участникам, использующим язык Python3, рекомендуется отправлять решения на проверку с использованием интерпретатора PyPy3.

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

Возле тропинки растут \(n\) деревьев, текущие уровни влажности которых заданы массивом \(a_1, a_2, \dots, a_n\). Леон научился трем способностям, которые помогут ему осушать и поливать почву.

• Он может выбрать позицию \(i\) и уменьшить уровень влажности деревьев \(1, 2, \dots, i\) на \(1\).

• Он может выбрать позицию \(i\) и уменьшить уровень влажности деревьев \(i, i + 1, \dots, n\) на \(1\).

• Увеличить уровень влажности всех деревьев на \(1\).

Леон хочет узнать минимальное число действий, которое необходимо совершить, чтобы каждое дерево имело уровень влажности равный \(0\).

Формат входных данных
В первой строке вводится одно целое число \(n\) (\(1 \leq n \leq 200\,000\)).

Во второй строке вводятся \(n\) целых чисел \(a_1, a_2 \ldots a_n\) (\(-10^9 \leq a_i \leq 10^9\)) — изначальные уровни влажности деревьев.

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

В первом примере из условия достаточно \(2\) раза применить операцию прибавления \(1\) ко всему массиву.

Во втором примере из условия можно \(4\) раза применить операцию вычитания на префиксе длины \(3\) и получить массив \(6, 0, 3\).

После этого \(6\) раз применить операцию вычитания на префиксе длины \(1\) и \(3\) раза операцию вычитания на суффиксе длины \(1\). Итого, количество действий составит \(4 + 6 + 3 = 13\). Можно показать, что меньшим количеством действий обойтись нельзя, поэтому \(13\) — это ответ.

 

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в два раза. Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче становится не менее W. Победителем считается игрок, сделавший последний ход, т.е. первым получивший кучу, в которой будет W или больше камней.
В начальный момент в куче было S камней, 1 ≤ S ≤ W-1.

Напишите программу, которая определяет:
задание 1) такое значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом.
задание 2)  все значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
задание 3)  все значение S, при котором одновременно выполняются два условия:

Аня и Боря играют в игру. Первый ход делает Аня. Изначально на доске записано натуральное число n. На каждом ходе игрока, этот игрок делает следующий ход:

• выбирает любое x,  не равное n, но кратное числу n (более формально 0 < x < n и n % x == 0)
• заменяет число n на доске на n-x.

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

Определите, кто победит в этой игре, если оба будут следовать оптимальной стратегии.


Формат входных данных
Программа получает на вход натуральное число n (n <= 1000).

Формат выходных данных
Выведите 1, если Аня выигрывает игру, иначе  выведите 0.

Дан массив целых чисел (nums) с индексацией, начинающейся с 0. Сформируйте новый массив целых чисел (ans), в котором i-й элемент вычисляется по формуле:

 ans[i] = |leftSum[i] - rightSum[i]|.

Где:

leftSum[i] - сумма элементов, стоящих слева от элемента nums[i]. Если таких элементов нет, то leftSum[i] = 0.
rightSum[i] - сумма элементов, стоящих справа от элемента nums[i]. Если таких элементов нет, то rightSum[i] = 0.

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

Формат входных данных
Первая строка содержит число n (n <= 10⁵). Во второй строке записаны n целых чисел numsi - элементы массива nums (|numsi| < 10⁶).

Формат выходных данных
Выведите на экран n чисел - элементы нового массива на экран в одну строку, разделяя элементы одним пробелом.

Электронная почта Деда Мороза в течении долгого времени принимает заказы на новогодние подарки. Все желания детей кодируются некоторым положительным целым числом и затем передаются по каналу связи. Количество заказаов заранее неизвестно, но их всегда не менее двух. Признаком конца данных считается число 0. 
Для того, чтобы понять, что все данные приняты без ошибок, после данных передаётся контрольное значение. Контрольное значение равно максимально возможному произведению двух чисел из переданных, которое делится на 7, но не делится на 49. Если такое произведение получить нельзя, контрольное значение считается равным 1.
Дед Мороз очень занят в последний месяц перед Новым годом и просит вас обработать все входные данные и напечатать краткий отчёт, включающий количество принятых чисел, принятое контрольное значение, вычисленное контрольное значение и вывод о совпадении значений.


Формат входных данных
В каждой строке исходных данных содержится одно целое число. Сначала идут строки с основными данными – положительными числами, затем число 0 (признак окончания данных), в последней строке – контрольное значение.

Формат выходных данных
Программа должна вывести отчёт по форме, приведённой ниже в примере.
 

Примечание
В последней строке в зависимости от результата (если переданное контрольное значение и вычисленное контрольное значения равны) может быть values true

Максимус любит симметричные строки. В качестве новогоднего подарка, он попросил ему подарить несколько натуральных чисел.  При этом, Максимус будет доволен, если он сможет записать все значащие цифры шестнадцатеричной записи этих чисел так, чтобы полученная строка было симметричной (читалась одинаково как слева направо, так и справа налево). 
Дед Мороз выбрал для Максимуса N натуральных целых чисел, каждое из которых не больше 1000. Он просит вас помочь ему определить, будет ли доволен Максимус таким подарком.
Если Максимус будет доволен, то ваша программа должна вывести на экран число 1, а иначе - число 0.

Формат входных данных
На вход программе подаётся натуральное число N (N <= 10⁵), а затем N натуральных чисел, каждое из которых не превышает 10000.

Формат выходных данных
Если Максимус будет доволен, то ваша программа должна вывести на экран число 0, а если возможно, то вывести число 1.

Примечание
1. В первом тестовом примере, если перевести все числа в шестнадцатеричную систему счисления, то получим цифры D, 1, 6, 2, 0. Из данных цифр невозможно составить симметричную строку. Ответ: 0.
2. Во втором тестовом примере, если перевести все числа в шестнадцатеричную систему счисления, то получим цифры A, B, 4, 4, A, B, D. Из данных цифр можем составить симметричную строку, например такую AB4D4BA. Ответ: 1.

 

Дед Мороз принёс Алисе новогодний подарок - Бинарную картину, которая представляет собой матрицу размером n x n, где каждое значение равно 0 или 1. Однако, перед тем как положить его под елку, Дед Мороз заметил, что полученная картина немного отличается от той, которую она заказывала.

Чтобы получить картинку, которую хотела Алиса, нужно выполнить следующие два шага:

1. Отразить картинку горизонтально: перевернуть каждую строку матрицы.
2. Инвертировать каждый пиксель: заменить каждое значение 0 на 1 и каждое значение 1 на 0.

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

Помогите Деду Морозу написать программу для посоха, иначе дети могут остаться без новогодних подарков!

Формат входных данных
Программа получает на вход в первой строке число n - размер картины (1 <= n <= 20). В каждой из следующих n строк написано по n чисел 0 или 1. 

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

У Громозеки есть его любимая строка S и другая строка T.  Он внимательно посмотрел на свои строки и понял, что первая строка (S) может содержать в себе несколько раз вторую строку (T). Громозека подсчитал все вхождения строки T в строку S и написал себе в порядке возрастания список индексов, начиная с которых строка T входит в строку S. Однако, путешествуя по Галактике, Громозека потерял этот список и пришел в уныние. Помогите Громозеке восстановить потерянный список. 

Формат входных данных
Первые две строки входных данных содержат строки S  и T, соответственно. Длины строк больше 0 и меньше 50000, строки содержат только строчные латинские буквы.

Формат выходных данных
Выведите в порядке возрастания индексы символов, начиная с которых строка T входит в строку S (в одной строке должно быть записано одно число).

Дана матрица numsi,j размером nxm. Вывести те столбцы матрицы, в которых имеется хотя бы один элемент, равный минимальному элементу матрицы.

Формат входных данных
Программа получает на вход в первой строке два числа n, m - количество строк и столбцов в матрице. В каждой из следующих n+1 строке записаны по m чисел - элементы матрицы numsi,j. (1<= n, m <= 15, -10⁵ <= numsi,j<=10⁵)

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

Дана матрица numsi,j размером nxm. Вывести те строки матрицы, в которых имеется хотя бы один элемент, равный минимальному элементу матрицы.

Формат входных данных
Программа получает на вход в первой строке два числа n, m - количество строк и столбцов в матрице. В каждой из следующих n+1 строке записаны по m чисел - элементы матрицы numsi,j. (1<= n, m <= 15, -10⁵ <= numsi,j<=10⁵)

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

Дана матрица numsi,j размером nxm. Заменить каждый элемент матрицы, оканчивающийся на 43, на максимальный элемент матрицы. 

Формат входных данных
Программа получает на вход в первой строке два числа n, m - количество строк и столбцов в матрице. В каждой из следующих n+1 строке записаны по m чисел - элементы матрицы numsi,j. (1<= n, m <= 15, -10⁵ <= numsi,j<=10⁵)

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

Дана матрица numsi,j размером nxm. Заменить каждый элемент матрицы, оканчивающийся на 12, на минимальный элемент матрицы. 

Формат входных данных
Программа получает на вход в первой строке два числа n, m - количество строк и столбцов в матрице. В каждой из следующих n+1 строке записаны по m чисел - элементы матрицы numsi,j. (1<= n, m <= 15, -10⁵ <= numsi,j<=10⁵)

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