В ДВФУ начался субботник. Всех студентов выстроили в ряд, чтобы определить, кто будет работать. Всего, конечно, надо выбрать как можно больше студентов, но с одним условием - все выбранные студенты должны стоять рядом. Известно, что есть прилежные студенты, которые работают хорошо, а есть такие, что только пакостят. Для каждого студента i известна его мощность - a[i]. Если a[i]>0, то он работает, если меньше - пакостит. Для набора студентов мощность этого набора будет суммарной мощностью всех студентов. Вы должны найти такой способ выбрать студентов, что они смогут выполнить всю работу (суммарная мощность будет положительна) и студентов было как можно больше, поскольку необходима массовость. Гарантируется, что найдётся хотя бы один горящий энтузиазмом студент.
Формат входного файла
В первой строке записано целое число N. Во второй строке записаны N целых чисел a[i], разделенных пробелами. Гарантируется, что хотя бы одно число положительное.
Формат выходного файла
Вывести ровно два числа, разделенных пробелом - искомые L и R. Среди возможных решений вывести то, в котором L минимально.
Ученые нашли биочип, который при определенных условиях делится на несколько новых биочипов. При этом биочип-родитель прекращает свое существование. Биочипы-потомки обладают каджый своим объемом памяти. Далее биочип можно или использовать (запретив дальнейшее деление), или он будет делиться дальше по заранее известной схеме.
Ученые составили древовидные схемы деления для разных биочипов и точно знают структуру дерева из N элементов, включая объем памяти каждого из потенциальных потомков. Им нужна программа, которая выберет из этого дерева ровно M биочипов, суммарный объем памяти которых максимален. Обратите внимание, что если мы выбираем какой-то биочип, то ни один из его предков или потомков не может быть выбран.
Формат входного файла
В первой строке входного файла находятся два целых числа N и M - количество элементов дерева и количество выбираемых биочипов.
Следующие N строк содержат по два неотрицательных целых числа, разделенных пробелом: номер родителя в дереве и размер собственной памяти a[i]. Каждый биочип идентифицируется числом между 1 и N включительно, строка входного файла с номером i содержит информацию о биочипе с номером i−1. Ровно один биочип не имеет родителя, в качестве номера его родителя записан 0.
Входные данные таковы, что M биочипов выбрать можно.
Формат выходного файла
Выходной файл должен содержать одно целое число - максимально возможный суммарный объем памяти выбранных M биочипов.
Али-Амир выписал N чисел в ряд. Ряд чисел считается красивым, если любые два соседних числа имеют одинаковое количество единиц в двоичной или троичной системе счисления.
Али-Амир задумался, сколькими способами все имеющиеся числа можно выписать в красивый ряд.
Формат входного файла
В первой строке входного файла находится число N. В следующей строке записаны N чисел a[i].
Формат выходного файла
Выведите количество способов расположить все N чисел в красивый ряд.
Последовательность Морса-Туэ задаётся следующим образом:
1) Вначале записывается 1.
2) Каждым шагом дописывается число, дополняющее уже написанное до числа, состоящего только из единиц.
3) Получаем искомую бесконечную последовательность:
1001011001101001011010011001011001101001...
Формат входного файла
В первой строке входного файла находится число N.
Формат выходного файла
Выведите элемент последовательности Морса-Туэ с номером N.
В марсианской столице очень необычная система общественного транспорта: остановки делятся на те, на которых можно выходить из автобуса, и те, на которых можно в него садиться. При этом для каждой остановки есть отрезок дороги, до каждой точки которого можно добраться из этой остановки. До точек, не принадлежащих отрезку добраться из этой остановки невозможно.
В столице всего одна дорога, весь город построен вдоль нее, так что положение каждой остановки задается одной координатой.
В городе имеется M маршрутов, определяемых автобусной остановкой, из которой автобусы начинают движение и автобусной остановкой, на которой они заканчивают движение. Автобусы курсируют по своим маршрутам постоянно. После окончания движения каждый автобус телепортируется в начальную остановку и продолжает работу.
Администрация города решила разработать систему, воспользовавшись которой каждый житель сможет определить существует ли для него путь из дома до работы. Считается, что зарплаты жителей хватает только на один проезд на автобусе(жители не могут ехать с пересадками). Эту работу решено поручить вам.
N - количество жителей города. M - количество автобусных маршрутов.
Формат входного файла
В первой строке расположено число N. За ним N пар чисел(по одной паре в строке) - координата дома каждого жителя и координата его офиса. В следующей строке расположено число M, за ним в M строках расположено описание автобусных маршрутов - четыре числа через пробел: начало отрезка, достижимого из начальной остановки, конец этого отрезка, начало отрезка, достижимого из конечной остановки и его конец.
Формат выходного файла
Для каждого из N людей вывести количество подходящих маршрутов через пробел.
Ограничения
N, M ≤ 100000, все координаты от -1000000000 до 1000000000 включительно
На улице зима. N детей захотело поиграть в снеговиков.
Каждый ребенок имеет свой номер 1 ≤ i ≤ N. Каждый ребенок выбирает одного из уже существующих снеговиков, строит такого же, и либо добавляет с своему какой-то снежный ком сверху, либо убирает один ком сверху, либо оставляет как есть.
Каждый снеговик имеет свою высоту - это сумма радиусов всех комов, из которых он составлен.
Вам нужно для каждого снеговика узнать его высоту.
Формат входного файла
В первой строке записано целое число N. В следующих N строках задано по 2 числа - p, x. p - номер уже существующего снеговика, которого выбирает ребенок, и x - как ребенок его изменяет. Будем считать, что снеговик с номером 0 - пустой, с нулевой высотой. Если x == −1 - он убирает верхний ком. x == 0 - он не изменяет снеговика. x > 0 - он кладет сверху на снеговика снежный ком радиуса x. Все запросы корректны (снеговик с номером p всегда будет существовать. Если ребенок попробует убрать верхний ком, но его нет, высота снеговика останется нулевой).
