Массивы


Плюсануть
Поделиться
Класснуть
Запинить


Условие задачи Прогресс
ID 38589. Практический тест
Темы: Массивы    Префиксные суммы(минимумы, ...)    Динамическое программирование: один параметр   

У нас есть сетка с 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		  

 
ID 38716. Радость Громозеки
Темы: Массивы    Алгоритмы обработки   

Громозека имеет последовательность целых чисел 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  

ID 38647. Путешествие Громозеки
Темы: Циклы    Массивы   

У Громозеки есть следующие два личных принципа: он никогда не преодолевает расстояние больше L за один день. Он никогда не спит под открытым небом. То есть он должен находться в отеле в конце дня.
На планете Блук N отелей и все расположены на одной улице. Координата i-го отеля (1<=i<=N) равна xi.
Путешествуя по планете Блук, Громозека запланировал Q переездов. Каждым переездом он планирует менять отель aj на bj (1<=j<=Q). Для каждого переезда найдите минимальное количество дней, которое нужно Громозеке, чтобы добраться от aj-го отеля до bj-го, следуя его принципам.
Гарантируется, что он всегда может поехать из aj-го отеля до bj-го отеля.

Входные данные
В первой строке задается целое число N (2<=N<=105) - количество отелей на планете Блук. Во второй строке - N чисел xi - координаты i-го отеля (1<=x1<x2<...<xN<=109 , xi+1−xi<=L). В третьей строке записано число L (1<=L<=109).  В четвертой строке - число Q (1<=N<=105). 
В последних Q строчках находится по два различных числа aj и bj (1<=aj,bj<=N). Все числа целые.

Выходные данные
Выведите Q строк. В j-й строке (1<=j<=Q) должно быть указано минимальное количество дней, которое Громозеке нужно, чтобы добраться из  aj-го отеля до bj -го отеля.

 

Примеры
№ Входные данные Выходные данные Пояснение
1 9
1 3 6 13 15 18 19 29 31
10
4
1 8
7 3
6 7
8 5		 4
2
1
2		 По 1-му переезду он может проехать от 1-го отеля до 8-го за 4 дня следующим образом:

День 1: Переезд из 1-го отеля во 2-й отель. Пройденное расстояние - 2.
День 2: Переезд из 2-го отеля в 4-й. Пройденное расстояние - 10.
День 3: Переезд из 4-го отеля в 7-й. Пройденное расстояние - 6.
День 4: Переезд из 7-го отеля в 8-й. Пройденное расстояние - 10.

 
ID 38926. Снежик Сугробович - 2
Темы: Циклы    Массивы   

В некотором мире сейчас 31 декабря и все веселье только начинается. Снежик Сугробович слепил N больших снежков и расположил их в ряд слева направо. На каждом i-м снежке, если считать слева (1 <= i <= N), он написал целое число ai. Он предлагает вам сыграть в игру. Снежик Сугробович разрешил сломать не более N − 1 снежков по вашему выбору. 

Допустим, осталось K снежков. Снежик Сугробович будет удовлетворен и подарит вам хороший подарок, если для каждого целого числа i (1<=i<=K) на i-м снежке, если считать слева оставшиеся снежки, будет написано целое число i.
Найдите минимальное количество снежков, которое вам нужно сломать, чтобы получить подарок. Если не получится, то выведите -1.

Входные данные
В первой строке программа получает на вход целое число N (1 <= N <= 200000). Во второй строке - N натуральных чисел ai (1<=ai<=N). 

Выходные данные
Выведите минимальное количество снежков, которые нужно сломать, чтобы получить подарок, или выведите -1, если это невозможно сделать.
 

Примеры
№ Входные данные Выходные данные Пояснение
1 3
2 1 2		 1 Сломайте первый снежок, числа на остальных снежках будут удовлетворять условию Снежика Сугробовича
2 3
2 2 2		 -1  
3 10
3 1 4 1 5 9 2 6 5 3		 7  
4 1
1		 0  

ID 33200. Vector: Начало
Темы: Массивы   

Создайте вектор и заполните его только положительными элементами.


Входные данные
В первой строке вводится количество элементов в массиве. Во второй строке вводятся элементы массива.
 
Выходные данные
Выведите только положительные элементы из последовательности.

 
Примеры
№ Входные данные Выходные данные
1 4
2 -4 0 100		 2 100

ID 30686. Сортировка вектора: Начало
Темы: Массивы   

Дана последовательность, состоящая из целых чисел. Напишите программу, которая создает и сортирует массив по убыванию.
 
Входные данные
Сначала задано число N — количество элементов в массиве (1<=N<=100). Далее через пробел записаны N чисел - элементы массива. Массив состоит из целых чисел.
 
Выходные данные
Необходимо вывести массив, отсортированный по убыванию.
 
Примеры
№ Входные данные Выходные данные
1 5
4 56 23 67 100		 100 67 56 23 4

ID 42324. Найти и посчитать
Темы: Массивы    Алгоритмы обработки   

Даны две целочисленные последовательности, каждая из которых имеет длину N: A = (A1, A2, ..., AN) и B = (B1, B2, ..., BN).
Все элементы A различны. Все элементы B тоже разные.

Выведите следующие два значения.

  1. Количество целых чисел, содержащихся в обоих A и B, появляющихся в одной и той же позиции в двух последовательностях. Другими словами, количество целых i чисел такое, что Ai = Bi.
  2. Количество целых чисел, содержащихся в обоих A и B, появляющихся в разных позициях в двух последовательностях. Другими словами, количество пар целых (i, j) чисел, таких, что Ai = Bj и i ≠ j.


Входные данные
Программа получает на вход три строки. В первой строке записано одно число N (1 <= N <= 1000) - количество чисел последовательности. Во второй строке записаны числа A1, A2, ..., AN, все числа различные. В третьей строке - числа B1, B2, ..., BN , все числа различные (1 <= Ai, Bi <= 109). 

Выходные данные
Выведите в первой строке ответ на первый вопрос, во второй строке - на второй.
 
 
Примеры
№ Входные данные Выходные данные
1 
4
1 3 5 2
2 3 1 4
 
1
2
2 
3
1 2 3
4 5 6
 
0
0

ID 38463. Мирные ладьи
Темы: Двумерные массивы    Массивы   

На шахматной доске размером N × N расставлено N шахматных ладей не бьющих друг друга, то есть на каждой вертикали и каждой горизонтали стоит ровно одна ладья.


Шахматную доску повернули на 90° по часовой стрелке. Выведите получившуюся расстановку ладей.


Входные данные
Первая строка входных данных содержит целое число N, 1 ≤ N ≤ 105 — размер доски. Следующие N строк содержат по одному числу от 1 до N, а именно, в i-й строке записано число ai — номер вертикали, в которой стоит ладья на i-й горизонтали. В этой задаче горизонтали нумеруются числами от 1 до N сверху вниз, вертикали нумеруются числами от 1 до N слева направо (см.рисунок).

Выходные данные
Программа должна вывести N чисел — расстановку ладей после поворота в таком же формате.

Примеры
№ Входные данные Выходные данные
1 5
4
2
3
5
1		 1
4
3
5
2

Замечание
Пример в условии соответствует рисункам. Первоначально ладьи стояли в столбцах 4, 2, 3, 5, 1
при перечислении их по строкам сверху вниз. После поворота ладьи стоят в столбцах 1, 4, 3, 5, 2.