ФОРМАТ ВЫВОДА (файл bcount.out):
Для каждого из Q запросов (a,b), выведите строку, содержащую три целых числа количество коров в интервале a…b, имеющих номера пород 1,2,3.
ПРИМЕР ВВОДА: 6 32113211 63 32 4 | ПРИМЕР ВЫВОДА: 3 2 11 0 0 2 0 1 |
Задача 13. Следующее дерево
На ферме Джона растет большое количество деревьев. После обучения в компьютерном классе, Бетси заметила, все эти деревья являются двоичными деревьями, у которых каждая вершина, не являющаяся листом, имеет ровно две вершины-наследницы. Бетси назначила каждой вершине число - количество листьев в поддереве, которое имеет эту вершину в качестве корневой.
Затем Бетси расположила числа, ассоциированные с вершинами в соответствующем порядке, однако она указала только числа, ассоциированные с корневой вершиной и всеми левыми наследницами всех вершин. Для уточнения рассмотрим следующее дерево:
*7 / \ / \ / \ *4 3 / \ / \*1 3 *1 2 / \ / \ *2 1 *1 1 / \*1 1 | Звездочками помечены вершины, указанные Бетси. Набор чисел, представляющих такое дерево - 7 4 1 2 1 1 1 После представления каждого дерева таким образом, Бетси заметила, что: * все деревья имеют одинаковое количество листьев * все деревья имеют различное числовое представление * все возможные двоичные деревья имеются на ферме Поэтому, будучи творческой коровой, она решила отсортировать коды этих деревьев. Решите эту же задачу и Вы. Вам задано числовое представление (код) дерева, найдите код, который следует за ним непосредственно, в списке Бетси. |
Формат ввода
|
|
* Строка 1: L - длина кода (1 <= L <= 1000)
* Строка 2: L разделенных пробелами целых чисел, представляющих код дерева в списке Бетси
Формат вывода
Одна строка с разделенными пробелом целыми числами кода, который следует за данным кодом в лексико-графическом порядке. Если входной код - последний в списке Бетси, выведите 0. Помните: деревья, указанные на вводе, и представленные в выводе должны иметь одно и то же количество листьев.
Пример ввода: 5 5 3 2 1 1 | Пример вывода 5 4 1 1 1 |
Задача 14. Сумма
Дан массив из n элементов. Найти сумму чисел на отрезке.
Формат ввода
Первая строка содержит два целых числа n и k (1 ≤ n ≤ 100000, 0 ≤ k ≤ 100000) – количество чисел в массиве и количество запросов.
Следующие k строк содержат запросы двух видов:
• A L R x – присвоить элементам массива с позициями от L до R значение x (1 ≤ L ≤ R ≤ n, 0 ≤ x ≤ 10^9)
• Q L R – найти сумму чисел в массиве на позициях от L до R (1 ≤ L ≤ R ≤ n)
Изначально в массиве находятся нули.
Формат вывода
На каждый запрос вида "Q L R" следует вывести единственное число – сумму на отрезке.
Пример входа 5 9 A 2 3 2 A 3 5 1 A 4 5 2 Q 1 3 Q 2 2 Q 3 4 Q 4 5 Q 5 5 Q 1 5 | Пример выхода 3 2 3 4 2 7 |
|
|
Задача 15. Свободные числа
Строка является палиндромом, если она остается такой же при обратном чтении. Число называется свободным от палиндромов, если оно не содержит палиндром с длиной больше 1 в качестве подстроки. Например, число 16276 является свободным от палиндромов, а число 17276 не является таковым, поскольку содержит палиндром 727. Ваша задача – вычислить общее количество свободных от палиндромов чисел в заданном диапазоне.
Ввод
Ввод содержит два целых числа, a и b.
Вывод
Вывод должен содержать одно целое число: общее количество свободных от палиндромов чисел в диапазоне a,…,b (включая числа a и b).
Ограничения: 0<=a<=b<=10^18.
Пример:
Ввод Вывод
123 321 153
123456789 987654321 167386971
Дата добавления: 2019-02-22; просмотров: 156; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!