#113283

Sparse table для суммы

Темы: [Динамическое программирование на таблицах] [Дерево отрезков, RSQ, RMQ]

Дан трёхмерный массив. Найдите сумму на параллелепипеде со сторонами, паралельными осям координат.

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

В первой строке даны три числа: 1 ≤ N , M , K ≤ 100 . В следующих N × M строках даны по K чисел - | a _ijk | < 10⁹ . Далее в отдельной строке даётся одно число Q ≤ 10⁵ - количество запросов. В следующих Q строках даются запросы: каждый запрос имеет вид x₁y₁z₁ x₂y₂z₂- две противоположные границы параллелепипеда, сумму которого необходимо подсчитать. 1 ≤ x ₁ ≤ x ₂ ≤ N 1 ≤ y ₁ ≤ y ₂ ≤ M 1 ≤ z ₁ ≤ z ₂ ≤ K

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

Для каждого запроса выведите одно число в отдельной строке - ответ на этот самый запрос

Примеры

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

3 3 3
2 3 5
1 2 3
4 5 7
1 6 6
9 6 6
8 6 6
4 3 3
2 3 3
5 3 3
1
2 1 2 3 3 3

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

#113299

Все слова

Темы: [Комбинаторика] [Целые числа]

Вася придумал свой собственный алфавит, в котором \(N\) символов. Теперь он хочет составить c с помощью этого алфавита все слова, состоящие ровно из \(K\) букв, причём ни одно слово не может начинаться с первой буквы алфавита и не может заканчиваться на последнюю букву алфавита. Помогите Васе определить, сколько он сможет составить таких слов.

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

Входная строка содержит два числа, разделённых пробелом: число символов в алфавите \(N\) и длину слов \(K\) (\(0\) < \(N, K\) <= \(10\)).

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

Программа должна вывести единственное число - количество слов длиной \(K\) в алфавите мощностью \(N\), таких что ни одно слово не начинается с первой буквы алфавита и не заканчивается на последнюю букву алфавита.

Примеры

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

4 1

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

#113300

Газон фермера

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

Английский фермер тщательно следит за своим газоном, в котором в каждой точке с целыми координатами растет один пучок травы. Как-то фермер воспользовался газонокосилкой и постриг траву на некотором прямоугольном участке газона. Стороны этого участка параллельны осям координат, а две противоположные вершины расположены в точках \((x_1, y_1)\) и \((x_2, y_2)\). Следует отметить, что пучки травы, находящиеся на границе этого прямоугольника, также были пострижены.

Для полива газона фермер установил в точке с координатами \((x_3, y_3)\) дождевальную установку, радиус действия которой равен \(r\). Таким образом, установка начала поливать все пучки, расстояние от которых до точки \((x_3, y_3)\) не превышало \(r\).

Фермера заинтересовал следующий вопрос: сколько пучков травы оказалось и пострижено, и полито в этот день? Требуется написать программу, которая позволит дать ответ на вопрос фермера.

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

Первая входная строка содержит четыре целых числа: \(x_1, y_1, x_2, y_2 (−100 000 \le x_1 < x_2 \le 100 000; −100 000 \le y_1 < y_2 \le 100 000)\). Во второй входной строке записаны три целых числа: \(x_3, y_3, r (−100 000 \le x_3, y_3 \le 100 000; 1 \le r \le 100 000)\).

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

Необходимо вывести одно целое число – число пучков травы, которые были и пострижены, и политы.

Подзадача 1

Все координаты не превосходят 1000. Решение оценивается в 30 баллов.

Подзадача 2

Радиус и стороны прямоугольника не превосходят 10000. Решение оценивается в 30 баллов.

Подзадача 3

Дополнительные ограничения отсутствуют. Решение оценивается в 40 баллов.

Примеры

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

0 0 5 4
4 0 3

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

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

-100 -100 100 100
0 0 50

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

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

0 0 10 10
100 100 5

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

#113301

Ходом коня

Темы: [Целые числа] [Условный оператор (if)] [Цикл for] [Строки]

Как известно, в шахматах горизонтальные строки обозначаются цифрами от 1 до 8, считая от расположения белых фигур, стоящих внизу доски, а вертикальные столбцы – буквами латинского алфавита: A, B, C, D, E, F, G, H.

На шахматной доске в клетке с заданными координатами находиться конь. Для клетки А1 после первого хода возможно перемещение коня на клетку С2 или В3.

Требуется написать программу, которая определяет координаты всех клеток, куда можно пойти конём первым ходом.

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

В единственной входной строке записано обозначение исходной позиции коня на шахматной доске.

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

В единственной строке должны быть записаны через пробел обозначения всех клеток, в которые может переместиться конь после первого хода. Клетки выводятся в следующем порядке: вначале клетки первого ряда слева – направо, далее клетки второго ряда и т.д.

Примеры

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

A1

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

C2 B3

#113302

Ходы коня-2

Темы: [Целые числа] [Строки] [Условный оператор (if)] [Цикл for]

Как известно, в шахматах горизонтальные строки обозначаются цифрами от 1 до 8, считая от расположения белых фигур, стоящих внизу доски, а вертикальные столбцы – буквами латинского алфавита: A, B, C, D, E, F, G, H.

На шахматной доске в клетке с заданными координатами находиться конь. Сначала делается первый ход конём, а затем – второй ход. Например, для клетки А1 после первого хода возможно перемещение коня на клетку С2 или В3, а после второго хода – на клетки А1, Е1, А3, Е3, В4, D4.

Требуется написать программу, которая определяет координаты всех клеток, куда можно прийти конём за два хода.

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

В единственной входной строке записано обозначение исходной позиции коня на шахматной доске.

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

В единственной строке должны быть записаны через пробел обозначения всех клеток, в которые может переместиться конь после второго хода. Клетки выводятся в следующем порядке: вначале клетки первого ряда слева – направо, далее клетки второго ряда и т.д.

Примеры

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

A1

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

A1 C1 E1 D2 A3 E3 B4 D4 A5 C5