Портал обучения информатике. Подготовка к ЕГЭ, ОГЭ, олимпиадам

Путь в никуда#24761

Колобку снится странный сон.
В нём Колобок находится на клетчатом поле размера n × m в клетке с координатами (x, y).
Изначально Колобок смотрит вдоль положительного направления оси X. Затем он начинает идти по полю со следующей закономерностью:
• Пройти на одну клетку вперед. Повернуть на 90^oвправо.
• Пройти на одну клетку вперед. Повернуть на 90^o вправо.
• Пройти на две клетки вперед. Повернуть на 90^o вправо.
• Пройти на две клетки вперед. Повернуть на 90^o вправо.
• Пройти на три клетки вперед. Повернуть на 90^o вправо.
• Пройти на три клетки вперед. Повернуть на 90^o вправо.
• Пройти на четыре клетки вперед. Повернуть на 90^o вправо.
• И так далее...

Движение продолжается до тех пор, пока Колобок не выйдет за границы поля. После этого Колобок просыпается.

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

Формат входного файла
В первой строке входного файла находятся два натуральных числа n, m (1 ≤ n, m ≤ 10⁹ ) — размеры доски вдоль оси X и оси Y соответственно. Во второй строке находятся два натуральных числа x, y (1 ≤ x ≤ n; 1 ≤ y ≤ m) — координаты стартовой позиции колобка.

Формат выходного файла
В выходной файл выведите одно число — количество клеток, посещенных Колобком во сне.

Вывод	Ввод
7 6 3 4	36
2 2 1 1	2
2 2 1 2	4

Комментарий
На рисунке наглядно показан первый пример.

✓ 17✗ 49800средняяВойти и решать

Легкая, вариант-1#24758

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

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

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

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

Входные данные

В первой строке находится натуральное число n (2 ≤ n ≤ 100) — количество сотрудников в фирме.

Следующая строка содержит n-1 натуральное число — номера непосредственных начальников сотрудников с номерами от 2 до n в соответствующем порядке. Числа отделены друг от друга одним пробелом. Гарантируется, что номер непосредственного начальника очередного сотрудника меньше номера самого сотрудника.

Следующая строка содержит одно натуральное число x (1 ≤ x ≤ n) — номер отправляемого в командировку сотрудника.

Выходные данные

выведите одно число — количество сотрудников, отправляющихся в командировку после выполнения описанной операции.

Пример входных и выходных данных

Ввод	Вывод
9 1 2 1 4 4 2 7 8 2	5

Деревья Поиск компонент связности

✓ 41✗ 67600лёгкаяВойти и решать

What's this#18539

What’s this

После посадки на Марс учёные нашли странную систему пещер, соединённых туннелями. И учёные начали исследовать эту систему, используя управляемых роботов. Было обнаружено, что существует ровно один путь между каждой парой пещер. Но потом учёные обнаружили специфическую проблему. Иногда в пещерах происходят небольшие взрывы. Они вызывают выброс радиоактивных изотопов и увеличивают уровень радиации в пещере. К сожалению, роботы плохо выдерживают радиацию. Но для исследования они должны переместиться из одной пещеры в другую. Учёные поместили в каждую пещеру сенсор для мониторинга уровня радиации. Теперь они каждый раз при движении робота хотят знать максимальный уровень радиации, с которым придётся столкнуться роботу во время его перемещения. Как вы уже догадались, программу, которая это делает, будете писать вы.

Формат входных данных
Первая строка содержит одно целое число N (1≤ N ≤ 100000) — количество пещер. Следующие N −1 строк описывают туннели. Каждая из этих строк содержит два целых числа — a_iи b_i(1 ≤ a_i,b_i≤ N), описывыющие туннель из пещеры с номером a_iв пещеру с номером b_i. Следующая строка содержит целое число Q (1 ≤ Q ≤ 100000), означающее количество запросов. Далее идут Q запросов, по одному на строку. Каждый запрос имеет вид «C U V », где C — символ «I» либо «G», означающие тип запроса (кавычки только для ясности). В случае запроса «I» уровень радиации в U-й пещере (1 ≤ U ≤ N) увеличивается на V (0 ≤ V ≤ 10000). В случае запроса «G» ваша программа должна вывести максимальный уровень радиации на пути между пещерами с номерами U и V (1≤ U,V ≤ N) после всех
увеличений радиации (запросов «I»), указанных ранее. Предполагается, что изначальный уровень радиации равен 0 во всех пещерах, и он никогда не уменьшается со временем (потому что период полураспада изотопов много больше времени наблюдения).
Формат выходных данных
Для каждого запроса «G» выведите одну строкусодержащую максимальный уровень радиации

графы Дерево отрезков, RSQ, RMQ Деревья

✓ 5✗ 251 200средняяВойти и решать