Массивы

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.

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

Примеры

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·10⁵). Во второй строке записано N целых чисел Ai (1 <= Ai <= 10⁹).

Выходные данные
Выведите на экран минимально возможную абсолютную разницу между максимумом и минимумом между P, Q, R, S.
 

Примеры

ID 38647. Путешествие Громозеки

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

Входные данные
В первой строке задается целое число N (2<=N<=10⁵) - количество отелей на планете Блук. Во второй строке - N чисел xi - координаты i-го отеля (1<=x₁<x₂<...<x_N<=10⁹ , x_i+1−x_i<=L). В третьей строке записано число L (1<=L<=10⁹).  В четвертой строке - число Q (1<=N<=10⁵). 
В последних Q строчках находится по два различных числа aj и bj (1<=a_j,b_j<=N). Все числа целые.

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

Примеры

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, если это невозможно сделать.
 

Примеры

ID 33200. Vector: Начало

ID 30686. Сортировка вектора: Начало

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.

Примеры

4
1 3 5 2
2 3 1 4

1
2 

3
1 2 3
4 5 6

0
0

ID 38463. Мирные ладьи

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


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


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

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

Примеры

ID 43908. Список делителей

На вход программе подается натуральное число n >= 2, а затем n целых чисел. Напишите программу, которая создает из указанных чисел новый список, состоящий из сумм соседних чисел (0 и 1, 1 и 2, 2 и 3 и т.д.).

Входные данные
Программа получает на вход натуральное число n, а затем n целых чисел, каждое на отдельной строке.

Выходные данные
Программа должна вывести список, состоящий из сумм соседних чисел.

 

Примеры

ID 12471. 12471

Примеры

ID 7074. Пара с максимальной суммой

Напишите программу поиска номера первого из двух последовательных элементов в целочисленном массиве из 30 элементов, сумма которых максимальна (если таких пар несколько, то выбрать первую из них). Индексация элементов начинается с 0.


Входные данные
Программа получает на вход 30 строк, в каждой из которых записано по одному числу - элементу массива. Каждое число не превышает по модулю 10⁹.

Выходные данные
Выведите одно число - ответ на задачу.
 
 

ID 47509. Максимус спасает Элстейд

Одарённый невероятной магией и всезнанием Максимус заметил группу из n монстров, приближающихся к городку Элдстейд. Своими волшебными способностями он мгновенно определил расстояние в километрах от города до каждого монстра. Он также заметил, что все монстры двигаются с постоянной скоростью. У Максимуса есть оружие, способное уничтожить одного монстра после полной зарядки. Зарядка занимает ровно одну минуту. Чтобы победить монстра, оружие должно быть полностью заряжено к моменту приближения монстра к городу. Другими словами, невозможно убить монстра достигшего города, даже если в этот момент оружие закончило полную зарядку.
Максимус задается вопросом, сможет ли он сам спасти город от всех монстров или ему нужна помощь.
Напишите программу, которая поможет Максимусу мгновенно определить максимальное количество монстров, которое он сможет уничтожить до того момента, как хотя бы один монстр достигнет города.

Входные данные
Первая строка содержит число n - количество монстров. Во второй строке записано n чисел dist[i] - начальное расстояние в километрах от города для i-го монстра. Третья строка содержит n чисел speed[i] - скорость i-го монстра в километрах в минуту.

Ограничения

• n == длина массива dist == длина массива speed
• 1 <= n <= 105
• 1 <= dist[i], speed[i] <= 105

Примеры

3
1 3 4 
1 1 1

3

4
1 1 2 3
1 1 1 1

1

ID 48418. Симметричный подарок

Максимус любит симметричные строки. В качестве новогоднего подарка, он попросил ему подарить несколько натуральных чисел.  При этом, Максимус будет доволен, если он сможет записать все значащие цифры шестнадцатеричной записи этих чисел так, чтобы полученная строка было симметричной (читалась одинаково как слева направо, так и справа налево). 
Дед Мороз выбрал для Максимуса N натуральных целых чисел, каждое из которых не больше 1000. Он просит вас помочь ему определить, будет ли доволен Максимус таким подарком.
Если Максимус будет доволен, то ваша программа должна вывести на экран число 1, а иначе - число 0.

ID 54966. Справедливая последовательность

Последовательность из нулей и единиц четной длины назовем справедливой, если на четных местах этой последовательности столько же единиц, сколько на нечетных. Например, последовательность "011011" является справедливой, а последовательность "011101" – нет.

Задана некоторая последовательность нечетной длины из нулей и единиц. Из нее разрешается удалить одну цифру. Какую цифру следует удалить, чтобы последовательность стала справедливой?

Например, из последовательности "0111011" с этой целью можно удалить вторую цифру.

Входные данные
На вход программы поступает одна строка. Эта строка содержит последовательность нечетной длины из нулей и единиц. Длина последовательности не превышает 200001.

Выходные данные
Выведите одно число - номер цифры в последовательности, которую следует удалить, чтобы последовательность стала справедливой. Цифры нумеруются, начиная с 1.

Если это сделать невозможно, выведите 0. Если решений несколько, выведите любое.

ID 57843. Сосны

В городе П для подготовки к празднику решили украсить аллею. Для этого наняли две бригады, одна отвечает за освещение аллеи, а вторая "— за озеленение аллеи, закупку саженцев сосны.

Аллею можно представить как прямую, и её решили украсить следующим образом — начать с сосны, чередовать лампы и сосны. В итоге на аллее будет высажено \(n + 1\) сосен и установлено \(n\) ламп.

Лампы поставили почти сразу же, причём двух типов — <<A>> и <<B>>. Лампы типа <<B>> светят всегда белым светом, а цвет лампы типа <<A>> зависит от её окружения. Если дерево, которое стоит слева от лампы, выше, чем дерево, которое стоит справа от лампы, то она загорается красным цветом, иначе синим.

Когда наконец-то доставили саженцы сосен, оказалось, что высоты всех саженцев попарно различны и принимают значения от \(1\) до \(n + 1\). Решено было разместить сосны так, чтобы количество красных и количество синих ламп были как можно ближе друг к другу.

Помогите ответственным за деревья разместить все \(n + 1\) саженцев так, чтобы разница между количеством красных и синих ламп была минимальна. Формально, если после высадки сосен будет \(r\) красных и \(b\) синих ламп, необходимо минимизировать величину \(|r-b|\).

Формат входных данных
В первой строке вводится одно единственное число \(n\) — количество ламп (\(1 \leq n \leq 2 \cdot 10^5\)). Во второй строке вводится \(n\) символов, \(i\)-й из которых равен <<A>> или <<B>> — тип \(i\)-й лампы.

Формат выходных данных
Выведите \(n + 1\) различных чисел от \(1\) до \(n + 1\) — высоты сосен при оптимальном размещении. Если оптимальных ответов несколько, можно вывести любой из них.

Иллюстрация ко второму примеру

Для наглядности, на иллюстрации красные лампы имеют формулу пятиугольника, а синие имеют форму звезды.

Тогда \(r = 1\), \(b = 1\), \(|r - b| = 0\) и это размещение будет одним из оптимальных.

ID 50865. Подземелья Одинокой горы

Однажды люди, эльфы, гномы и другие жители Средиземья собрались отнять у Смога украденные у них сокровища. Во имя этой великой цели они сплотились вокруг сильного эльфа Тимофея и начали планировать свержение правителя Одинокой горы.

Армия жителей Средиземья будет состоять из нескольких отрядов. Известно, что каждая пара существ одной расы, которые находятся в разных отрядах, прибавляет \(b\) единиц к суммарной силе армии. Но так как Тимофею будет сложно руководить армией, состоящей из большого числа отрядов, то суммарная сила армии, состоящей из \(k\) отрядов, уменьшается на \((k - 1) \cdot X\) единиц. Обратите внимание, что армия всегда состоит из хотя бы одного отряда.

Известно, что в Средиземье проживают \(n\) рас, и количество существ \(i\)-й расы равно \(c_i\). Помогите жителям Средиземья определить максимальную силу армии, которую они могут составить.

Формат входных данных
Первая строка входных данных содержит три целых числа \(n\), \(b\) и \(X\) (\(1 \le n \le 200\,000\), \(1 \le b \le 10^6\), \(0 \le X \le 10^9\)) — количество рас и константы \(b\) и \(X\), описанные выше.

Вторая строка содержит \(n\) целых чисел \(c_1, c_2, \ldots, c_n\) (\(1 \le c_i \le 200\,000\)) — количество существ каждой из \(n\) рас.

Гарантируется, что \(c_1 + c_2 + \ldots + c_n \le 200\,000\).

Формат выходных данных
Выведите одно целое число — максимальную силу армии, которую могут составить жители Средиземья.

Обратите внимание, что ответ может быть больше, чем возможное значение 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C и C++, тип long в Java и C#). Язык Python будет корректно работать.

Замечание

В первом примере жители Средиземья могут составить \(3\) отряда. Так как \(X = 0\), то сила армии не уменьшится из-за количества отрядов. Далее жителей по отрядам можно распределить так:

• Единственного представителя первой расы можно отправить в первый отряд.

• Первого представителя второй расы можно отправить в первый отряд, второго представителя второй расы можно отправить во второй отряд. Тогда суммарная сила армии увеличится на \(b = 1\).

• Первого представителя третьей расы можно отправить в первый отряд, второго представителя третьей расы можно отправить во второй отряд, третьего представителя третьей расы можно отправить в третий отряд. Тогда суммарная сила армии увеличится на \(3 \cdot b = 3\), так как они образуют три пары, находящиеся в разных отрядах.

Таким образом, суммарная сила армии равна \(4\).

ID 56661. Праздники

На планете в звездной системе Альфа Кентавра неделя состоит из A дней, а год - из B дней. Годы нумеруются последовательными натуральными числами: 1, 2, 3, ... Кроме того, годы с номерами C1, C2, ..., CN являются високосными и состоят из (B+1) дней. В году дни с номерами D1, D2, ..., DM являются праздничными. Если праздник попадает на (B+1)-й день года, то он отмечается только в високосные годы. Первый день первого года является первым днем недели.

Один из жителей планеты решил устроиться на новую работу. В соответствии с заключенным трудовым договором он будет числиться на данной работе в течение E дней, начиная с первого дня 1-го года. По договору он имеет право выбрать один день недели (с 1 по A), который будет для него выходным. Праздничные дни также считаются нерабочими. Житель хочет выбрать себе выходной день таким образом, чтобы за период действия договора у него было максимальное количество нерабочих дней.

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

Входные данные
В первой строке входного файла через пробел записаны числа A и B - количество дней в неделе и в невисокосном году соответственно (1 ≤ A ≤ 2500, 1 ≤ B ≤ 10000). Во второй строке записано число N - количество високосных лет, и в третьей - номера C1, C2, ..., CN високосных лет в возрастающем порядке (0 ≤ N ≤ 5000, 1 ≤ C1 < C2 < ... < CN ≤ 107). В следующей строке число M - количество праздничных дней в году, и на новой строке - D1, D2, ..., DM в возрастающем порядке (1 ≤ D1 < D2 < ... < DM ≤ B+1). В последней строке записано число E (1 ≤ E ≤ 109). Известно, что житель заключил контракт не более чем на 10⁷ лет.

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