Задана последовательность из n чисел a1, a2, ..., an. Подпоследовательностью длины k этой последовательности называется набор индексов i1, i2, ..., ik, удовлетворяющий неравенствам 1 ≤ i1 < i2 < ... < ik ≤ n. Подпоследовательность называется возрастающей, если выполняются неравенства ai1 < ai2 < ... < aik.
Необходимо найти число возрастающих подпоследовательностей наибольшей длины заданной последовательности a1, ... ,an. Так как это число может быть достаточно большим, необходимо найти остаток от его деления на 109 + 7.
Первая строка входного файла содержит целое число n (1 ≤ n ≤ 105). Вторая строка входного файла содержит n целых чисел: a1, a2, ... ,an. Все ai не превосходят 109 по абсолютной величине.
В выходной файл выведите ответ на задачу.
5 1 2 3 4 5
1
6 1 1 2 2 3 3
8
В области Тампере существуют станции обслуживания мобильных телефонов четвертого поколения, которые работают следующим образом. Вся область разделена на квадраты. Квадраты формируют матрицу S×S, строки и столбы которой нумеруются с 0 до S - 1. Каждый квадрат содержит одну станцию обслуживания. Количество активных мобильных телефонов внутри квадрата может меняться, потому что телефон может перемещаться из одного квадрата в другой или выключаться. Временами каждая станция обслуживания передает сведения об изменении в количестве активных телефонов на главную станцию обслуживания (вместе с номером строки и столбца матрицы).
Напишите программу, которая принимает эти сведения и отвечает на запросы о текущем количестве активных мобильных телефонов в любой прямоугольной области.
Каждый запрос к программе описывается на отдельной строке и состоит из одного целого числа, описывающего команду, а также из дополнительных параметров команды в соответствии со следующей таблицой:
| Команда | Параметры | Значение |
|---|---|---|
| 0 | S | Инициализирует матрицу размером S×S, состоящую только из нулей. Эта команда поступает один раз и является самой первой командой. |
| 1 | X Y A | Добавить число A к количеству активных мобильных телефонов в квадрате (X;Y). Число A может быть как положительным, так и отрицательным. |
| 2 | L B R T | Выдать текущую сумму количеств активных мобильных телефонов во всех квадратах (X;Y), где L ≤ X ≤ R, B ≤ Y ≤ T. |
| 3 | Прервать программу. Эта команда поступает один раз и является самой последней командой. |
Все значения всегда лежат в правильном диапазоне, поэтому нет необходимости их проверять. В частности, если число A отрицательное, то число активных телефонов в каком-либо квадрате все равно не станет меньше нуля. Индексы начинаются с 0, поэтому, например, для таблицы размера 4×4 имеем 0 ≤ X ≤ 3, 0 ≤ Y ≤ 3.
Ваша программа не должна отвечать ни на какую команду, кроме 2. Если команда 2, то ваша программа должна вывести единственную строку, содержащую одно целое число — ответ на этот запрос.
| Размер таблицы | S×S | 1×1 ≤ S×S ≤ 1024×1024 |
| Значение ячейки в любой момент времени | V | 0 ≤ V ≤ 215 - 1 (= 32767) |
| Величина обновления | A | -215 ≤ A ≤ 215 - 1 (= 32767) |
| Количество команд | U | 3 ≤ U ≤ 60002 |
| Максимальное количество активных телефонов во всей таблице | M | M = 230 |
0 4 1 1 2 3 2 0 0 2 2 1 1 1 2 1 1 2 -1 2 1 1 2 3 3
3 4
Многие пользователи мобильных телефонов при наборе sms-сообщений используют режим T9. При этом сообщения, например на английском языке, они набирают следующим образом. Для набора слова по буквам соответствующая букве кнопка нажимается один раз, вне зависимости от того, сколько букв соответствуют этой кнопке, и какой по счету идет нужная буква (см. картинку), а программа в телефоне подбирает из имеющегося словаря подходящее для данной комбинации кнопок слово. Если подходящих слов несколько, то в первую очередь предлагается наиболее часто встречающееся слово (изначально слова одинаковой встречаемости предлагаются по алфавиту). Если слово не подошло, то пользователь нажимает кнопку ‘*’ и программа предлагает второе по встречаемости слово, образуемое той же комбинацией кнопок (в первую очередь следующее слово с той же частотой встречаемости, если такое имеется). Если и оно не подошло, то кнопка ‘*’ нажимается еще раз и т.д. Для простоты будем считать, что современные модели телефонов содержат полный словарь используемых слов, и нужное слово обязательно найдется. Когда предлагаемое слово подошло, пользователь нажимает на кнопку “пробел”, нажимает на кнопку ‘1’ (последняя соответствует набору знака препинания), или заканчивает набирать сообщение. Когда знак препинания не подошёл, опять же нажимается кнопка ‘*’, до тех пор пока не появится требуемый знак. После набора пробела или знака препинания пользователь может ввести ещё один пробел или знак препинания, начать набирать следующее слово или закончить набирать сообщение. Будем считать, что пользователю достаточно трех знаков препинания, и они предлагаются в следующем порядке: точка (‘.’), запятая (‘,’), вопросительный знак (‘?’). После того как пользователь “утвердил” набранное слово (нажав на пробел или ‘1’), частота его встречаемости в словаре увеличивается на 1, и новое значение частоты учитывается, в том числе, и при наборе в режиме T9 остальных слов того же сообщения. При этом данное слово будет предлагаться первым среди слов с такой же частотой встречаемости, порядок предложения остальных слов остается неизменным. Когда появится еще одно слово с той же частотой, то уже оно будет предлагаться первым, не меняя порядка остальных, и т. д. Вам требуется написать программу, которая по имеющемуся словарю, содержащему первоначальные характеристики частоты встречаемости того или иного английского слова, и известной последовательности нажатий кнопок пользователем при наборе sms-сообщения в режиме T9 воспроизведет появившееся на экране сообщение.
В первой строке входного файла находится целое число N (3 ≤ N ≤ 50000) — количество слов в словаре. В каждой из следующих N строк записаны одно слово словаря и через пробел натуральное число F (1 ≤ F ≤ 1000) — первоначальное значение частоты встречаемости этого слова (чем больше значение, тем чаще встречается данное слово). Числовая характеристика частоты встречаемости отделена от слова ровно одним пробелом. Слова в словаре состоят только из строчных английских букв и расположены в алфавитном порядке. Длина слова не превышает 20 символов. Все слова не пустые и различные. Последняя строка файла состоит из цифр от 1 до 9 и символов “пробел” и ‘*’, обозначающих последовательность нажатий кнопок при наборе сообщения. Длина этой строки не превосходит 100000 символов.
Выведите в выходной файл текст sms-сообщения.
5 ad 2 be 1 not 10 or 5 to 50 86 23* 67 668 86 231**
to be or not to be?
3 act 1 bat 1 cat 1 228* 228** 228** 228**1
bat cat act bat.
Одна из новых возможностей текстового редактора «World XP» — это сортировка слов в предложении. Выход новой бета-версии редактора должен состоятся не позднее, чем через пять часов, а заявленная функция еще не реализована.
Требуется написать программу, осуществляющую сортировку слов в предложении. При этом все символы, отличные от букв, должны сохранится и не поменять своего положения относительно вхождений слов. Для упрощения при подаче входных данных на вход вашей программы все такие символы будут заменены на символ «.» (точка). Таким образом символ «.» имеет смысл разделителя между словами. Например, строка «..aba.a..ba» после сортировки пример вид «..a.aba..ba», а строка «c..bb.a» примет вид «a..bb.c». Слова следует сортировать лексикографически, как в словаре.
Входной файл содержит единственную строку, содержащую только прописные латинские буквы и символ «.». Слова могут разделяться любым количеством символов «.», строка может как начинаться, так и заканчиваться последовательностью точек. Длина заданной строки не менее 1 символа и не превосходит 106 символов.
В выходной файл выведите строку после сортировки слов в ней.
..aba.a..ba
..a.aba..ba
c..bb.a
a..bb.c
У Коли сегодня день рождения! По этому случаю он решил после олимпиады сходить с друзьями в парк аттракционов. И какая удача — можно купить групповой билет сразу на всех, всего за S рублей!
Конечно, скидываться придется всем поровну. То есть, если Коля позовет k своих друзей, то каждому придется заплатить S / (k + 1) рублей (да, сам Коля тоже должен внести свою долю). При этом S не обязательно должно делиться на k + 1: главное — купить билет, а между собой друзья уж как-нибудь договорятся.
Всего у Коли n друзей, при этом i-й из них готов пойти с Колей в парк, если доля, которую ему придется заплатить не больше bi (больше денег у него просто с собой нет) и не меньше ai (иначе он решит, что Колин день рождения — это скучно, и пойдет играть в волейбол с Сережей).
Так что может так получиться, что всех позвать не удастся. Ну и ладно. Для каждого своего друга Коля знает число fi — количество веселья, который тот произведет, если его позвать.
Помогите Коле выбрать подмножество друзей, которых Коля должен позвать с собой, чтобы максимизировать суммарное веселье.
В первой строке входного файлы содержится два целых числа: n и S (1 ≤ n ≤ 100000, 0 ≤ S ≤ 109) — количество друзей Коли и стоимость билета. В следующих n строках содержится по три целых числа: в i-й из этих строк находятся числа ai, bi и fi (0 ≤ ai ≤ bi ≤ S, 0 ≤ fi ≤ 109). Они означают, что i-го друга можно позвать на вечеринку, если доля, которую ему придется заплатить, лежит между ai и bi, и он произведет fi веселья.
В первой строке выходного файла выведите два числа: k (количество приглашенных на вечеринку друзей) и F (максимальное суммарное веселье, которое можно получить). Во второй строке выведите k чисел — номера друзей, которых нужно пригласить
4 10 4 5 40 2 4 30 2 6 10 3 5 20
2 50 2 4