| Условие задачи | | Прогресс |
|
Темы:
Массивы
Префиксные суммы(минимумы, ...)
Динамическое программирование: один параметр
У нас есть сетка с H строками и W столбцами. Квадрат в i-й строке и j-м столбце будет называться Square(i, j). Целые числа от 1 до H·W записаны по всей сетке, а целое число, записанное в Square(i, j), равно Ai,j.
Вы - волшебник (волшебница), и можете телепортировать фигуру, помещенную на Square(i, j) в Square(x, y), потратив \(|x-i|+|y-j|\) маджиков (магических монет).
Теперь вам нужно пройти Q практических тестов на свои способности как волшебника (волшебницы). I-е испытание будет проводиться следующим образом:
- первоначально фигура располагается в квадрате, где записано целое число Li;
- пусть x будет целым числом, записанным в квадрате, занятом фигурой. Неоднократно переместите фигуру в квадрат, где написано целое число x+D, пока x не станет равен Ri. Тест заканчивается, когда x = Ri .
Гарантируется, что Ri- Li делится на D.
Для каждого теста найдите сумму маджиков, израсходованных во время этого теста.
Входные данные
В первой строке заданы три целых числа: H, W и D (\(1\leq H,W \leq 300\), \(1 \leq D \leq H \cdot W\)).
В следующих H строках записано по W чисел Ai,j (\(1 \leq A_{i,j} \leq H \cdot W\), \(A_{i,j} \neq A_{x,y} ((i,j) \neq (x,y))\).
В следующей строке записано целое число Q (\(1 \leq Q \leq 10^5\)).
В последних Q строках записано по 2 целых числа: Li и Ri (\(1 \leq L_i \leq R_i \leq H \cdot W\)), \((R_i-L_i)\) кратно D.
Выходные данные
Для каждого теста выведите сумму маджиков, израсходованных во время этого теста. Вывод должен быть в порядке проведения тестов.
Примеры
| № |
Входные данные |
Выходные данные |
Пояснения |
| 1 |
3 3 2
1 4 3
2 5 7
8 9 6
1
4 8 |
5 |
- 4 записано Square (1,2).
- 6 записано в Square (3,3).
- 8 записано in Square (3,1).
Таким образом, сумма магических очков, израсходованных во время одного теста, составляет:
\((|3-1|+|3-2|)+(|3-3|+|1-3|)=5\).
|
| 2 |
4 2 3
3 7
1 4
5 2
6 8
2
2 2
2 2 |
0
0 |
Обратите внимание, что может быть тест, в котором фигура вообще не перемещается, и может быть несколько идентичных тестов. |
| 3 |
5 5 4
13 25 7 15 17
16 22 20 2 9
14 11 12 1 19
10 6 23 8 18
3 21 5 24 4
3
13 13
2 10
13 13 |
0
5
0 |
|
| |
![]()
|
|
Темы:
Массивы
Алгоритмы обработки
Громозека имеет последовательность целых чисел A длины N. Он сделает три среза в последовательности A и разделит ее на четыре (непустые) смежные подпоследовательности B, C, D и E. Положения срезов он выбирает произвольно. Пусть P, Q, R, S - суммы элементов в B, C, D, E соответственно. Громозека будет счастлив, когда абсолютная разница между максимумом и минимумом между P, Q, R, S будет минимальной. Найдите минимально возможную абсолютную разницу между максимумом и минимумом между P, Q, R, S.
Входные данные
В первой строке записано целое число N (\(1<=N<=2 \cdot 10^5\)). Во второй строке записано N целых чисел Ai (\(1<=A_i<=10^9\)).
Выходные данные
Выведите на экран минимально возможную абсолютную разницу между максимумом и минимумом между P, Q, R, S.
Примеры
| № |
Входные данные |
Выходные данные |
Пояснения |
| 1 |
5
3 2 4 1 2 |
2 |
Если разделить A на B, C, D, E = (3), (2), (4), (1,2), то P = 3, Q = 2, R = 4, S = 1 + 2 = 3.
Здесь максимум и минимум среди P, Q, R, S равны 4 и 2, с абсолютной разницей 2.
Мы не можем сделать абсолютную разницу между максимумом и минимумом меньше 2, поэтому ответ - 2. |
| 2 |
10
10 71 84 33 6 47 23 25 52 64 |
36 |
|
| 3 |
7
1 2 3 1000000000 4 5 6 |
999999994 |
|
| |
![]()
|