Author: | - | Time limit: | 1 sec | |
Input file: | input.txt | Memory limit: | 256 Mb | |
Output file: | output.txt |
Имеется трёхмерный массив чисел. Поступают запросы двух видов. Запрос первого вида заменяет значение в заданной ячейке на заданную величину. Запрос второго вида требует вычисления суммы значений в ячеках заданного параллелепиппеда.
Требуется написать программу, обрабатывающую запросы в порядке их перечисления, и выводящую на печать ответы на запросы второго вида.
В первой строке входного файла находится целое число n — общее количество запросов.
Далее следует n строк, содержащих запросы. В начале каждой строки находится число 1 или 2 — тип запроса.
Для запросов первого типа далее в строке содержатся целые числа x, y, z, value — координаты ячейки и новое значение в ней.
Для запросов второго типа далее в строке содержатся целые числа x1, y1, z1, x1, y1, z1 — координаты параллелепиппеда, для которого следет предоставить ответ на запрос.
Для каждого запроса второго типа следует вывести единственное число — ответ на запрос.
1 ≤ n ≤ 100000;
1 ≤ x, y, z, x1, y1, z1, x2, y2, z2 ≤ 100;
0 ≤ 232−1;
No. | Input file (input.txt ) |
Output file (output.txt ) |
---|---|---|
1 |
|
|
Автор: | - | Ограничение времени: | 1 сек | |
Входной файл: | input.txt | Ограничение памяти: | 256 Мб | |
Выходной файл: | output.txt |
Найдите наибольшую общую подпоследовательность двух строк.
В первой строке находится первая строка, во второй строке находится вторая строка. Строки состоят только из маленьких латинских букв.
Вывести наибольшую общую подпоследовательность. Если решений несколько, вывести любое.
Длина каждой строки не менее 1 и не превосходят 1000.
№ | Входной файл (input.txt ) |
Выходной файл (output.txt ) |
---|---|---|
1 |
|
|
Автор: | И. Бураго | Ограничение времени: | 2 сек | |
Входной файл: | input.txt | Ограничение памяти: | 64 Мб | |
Выходной файл: | output.txt |
Не так давно администрация столицы Флатландии приняла решение о строительстве канатной дороги. Этот транспорт подходит городу как нельзя лучше: столица построена на N холмах, каждый из которых при взгляде сбоку имеет вид параболы с направленными вниз ветвями. То есть i-й холм можно однозначно определить такими тремя числами Ai, Bi, Ci, что точка плоскости с координатами (x, y) находится внутри холма тогда и только тогда, когда Ai x2 + Bi x + Ci ≥ y. Холмы могут пересекаться, но вершина холма никогда не находится внутри другого холма.
Канатная дорога представляет собой набор из K одинаковых столбов высоты H, через вершины которых последовательно (в порядке увеличения абсциссы) протянут канат. В целях повышения надежности пассажирских перевозок столбы должны устанавливаться только на вершинах холмов. На первом и N-м холмах обязательно должны быть установлены столбы. Отрезки каната не должны пересекаться или даже касаться холмов.
Покупка уникальных столбов с античными барельефами принесла казне столицы существенные убытки, поэтому администрация хочет установить столбы так, чтобы сэкономить хотя бы на канате. Требуется написать программу, которая вычислит минимальную необходимую длину каната.
В первой строке входного файла находятся числа N K H, где N — количество холмов, K — число столбов и H — высота каждого из них (вещественное число). В каждой из следующих N строк содержится тройка вещественных чисел Ai Bi Ci, определяющая вид i-го холма. Холмы заданы в порядке увеличения абсциссы вершин.
В единственную строку выходного файла выведите минимальную длину каната, необходимого для строительства, с точностью до трёх знаков после десятичной точки или −1, если построить канатную дорогу невозможно.
2 ≤ N ≤ 300, 2 ≤ K ≤ N, 1 ≤ H ≤ 106.
−106 ≤ Ai < 0, −106 ≤ Bi, Ci ≤ 106.
Все вещественные числа во входном файле заданы не более чем с 5 знаками после десятичной точки.
№ | Входной файл (input.txt ) |
Выходной файл (output.txt ) |
---|---|---|
1 |
|
|
2 |
|
|