#1364

Сугробы на ЛЭП

Темы: [Дерево отрезков, RSQ, RMQ]

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

Служба электроснабжения проводит мониторинг уровня снега, лежащего на ЛЭП Нью-Васюки - Москва. Вся ЛЭП разбивается на участки опорами. Снег имеет свойства падать на какой-либо интервал ЛЭП, если там уже лежал какой-либо снег, то высота снежного покрова на этом участке суммируется. Также снег имеет тенденцию таять на участке трассы в результате оттепели, при этом известно, что не бывает сугробов отрицательной высоты. Энергетикам крайне важно уметь узнавать суммарную высоту снежного покрова на некоторых последовательных участках, чтобы знать вероятность обрыва проводов.

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

В первой строке входного файла содержатся два числа: N – (1 ≤ N ≤ 10 000) и M – количество команд (1 ≤ M ≤ 50 000). Каждая команда имеет вид “1 L R S”, что означает, что на участок с L-ой опоры по R-ую опору выпало S сантиметров снега (S может быть и отрицательным, тогда это означает, что такое количества снега растаяло), или “2 L R” – запрос суммарной высоты снега на участке с L-ой опоры по R-ую. Опоры нумеруются от 0 до N. Гарантируется, что для запросов вида “1 L R S” при S < 0 на каждом участке между опорами L и R уровень снега составляет не менее S.

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

На каждую команду 2 (запрос) вы должны выводить число K – суммарную высоту снежного покрова, лежащего на проводах с L-ой опоры по R-ую. Каждое число должно выводиться на новой строке. Известно, что в процессе работы суммарное количество снега на любом интервале не превышает 2³¹.

Примеры

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

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

37
67

#1367

Из шестнадцатиричной в двоичную

Темы: [Системы счисления]

Необходимо перевести число из шестнадцатиричной системы счисления в двоичную.

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

Задается одно целое число N ( N ≤ 65536) в шестнадцатиричной системе счисления.

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

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

Примеры

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

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

#1368

Из двоичной в шестнадцатиричную

Темы: [Системы счисления]

Необходимо перевести число из двоичной системы счисления в шестнадцатиричную.

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

Задается одно целое число N (1 ≤ N ≤ 65536) в двоичной системе счисления. В числе могут присутствовать ведущие нули, общее количество знаков кратно 4.

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

Необходимо вывести число N в шестнадцатиричной системе счисления.

Примеры

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

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

#1370

Фибоначчиева последовательность

Темы: [Цикл for]

Источники: [ Личные олимпиады, Московская олимпиада школьников, 7-9 классы, 2009, Задача A ]

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

Последовательность чисел a₁, a₂, …, a_i,… называется Фибоначчиевой, если для всех i≥3 верно, что a_i=a_i_–1+a_i_–2, то есть каждый член последовательности (начиная с третьего) равен сумме двух предыдущих.

Ясно, что задавая различные числа a₁ и a₂ мы можем получать различные такие последовательности, и любая Фибоначчиева последовательность однозначно задается двумя своими первыми членами.

Будем решать обратную задачу. Вам будет дано число N и два члена последовательности: a_N и a_N₊₁. Вам нужно написать программу, которая по их значениям найдет a₁ и a₂.

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

Вводятся число N и значения двух членов последователности: a_N и a_N₊₁ (1≤N≤30, члены последовательности — целые числа, по модулю не превышающие 100)
Если вы пишите на языке программирования python, то считывание a_N и a_N₊₁ элементов должно быть организовано так:
x, y = map(int, input().split())

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

Выведите два числа — значения первого и второго членов этой последовательности.

Примеры

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

4
3 5

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

1 1

#1371

Ка-штаны

Темы: [Одномерные массивы]

Источники: [ Личные олимпиады, Московская олимпиада школьников, 7-9 классы, 2009, Задача B ]

Заданы длины отрезков, которые необходимо наложить на окружность. Требуется наложить их так, чтобы максимальное количество отрезков, покрывающих точку было минимальным.

Как известно, обычно штаны состоят из двух штанин. Однако собачке нужны, например, уже штаны из 5 штанин (для 4-х лап и хвоста), а сороконожке – штаны с 40 штанинами.

У Пети живет Зверь, у которого M лап. Иногда – когда на улице особенно холодно, чтобы Зверь не простудился, на него бывает нужно надеть несколько штанов, чтобы на каждой лапе было надето по несколько штанин.

Петина мама оставила Пете N штанов, имеющих соответственно K₁, K₂, …, K_N штанин, наказав ему надеть на Зверя их все. Петя хочет надеть на Зверя штаны так, чтобы на самой «утепленной» лапе оказалось как можно меньше штанин, но при этом все оставленные мамой штаны были надеты на зверя. Любые штаны можно надевать на любой набор лап (каждая лапа встречается в наборе не более одного раза).

Помогите ему – напишите программу, которая для каждых штанов укажет, на какие лапы должны быть надеты их штанины. Имейте в виду, что две штанины одних и тех же штанов не могут быть надеты на одну и ту же лапу (в то время как штанины разных штанов могут быть надеты на одну и ту же лапу).

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

Вводится сначала число M, а затем число N (1 ≤ M ≤ 100, 1 ≤ N ≤ 100). Далее вводятся N чисел K_i, обозначающих число штанин у оставленных мамой штанов (1 ≤ K_i ≤ M).

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

Выведите N строк, в i-ой строке должно быть выведено K_i различных чисел, обозначающих номера лап Зверя, на которые должны быть надеты штанины i-ых штанов. Лапы Зверя нумеруются натуральными числами от 1 до M. Если искомых ответов несколько, то выведите любой из них.

Комментарии к примерам тестов.

1. Первые штаны надеты на лапу 1;
вторые штаны надеты на лапы 1 и 2;
третьи штаны надеты на лапы 2, 3 и 4.
Таким образом, на самых «утепленных» лапах (а это лапы 1 и 2) надето по 2 штанины.

2. Первые штаны надеты на лапы 1, 2 и 3;
вторые штаны надеты на лапы 1 и 4.
Таким образом, количество штанов на самой «утепленной» лапе (это лапа номер 1) – 2.

Примеры

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

4 3
1 2 3

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

1
2 3
4 1 2

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

4 2
3 2

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

1 2 3
4 1