Вешалка. Папа Карло нашел длинную палку в сарае и решил сделать из нее вешалку для ключей. Для этого он по всей длине забивает в палку гвоздики в разных местах. Папа Карло время от времени считает, сколько он уже забил гвоздиков на разных участках палки. Каждое действие Папы Карло — это либо забивание очередного гвоздика в точке с заданной координатой X, либо подсчет числа забитых гвоздиков на отрезке [X, Y]. Все координаты неотрицательные и не превосходят 10⁹, количество действий не более 10⁵.

Буратино, узнав, в чем дело, решил помочь Папе Карло. Буратино подробно записал все действия Папы Карло в процессе изготовления вешалки и теперь хочет проверить расчеты по числу гвоздиков на разных интервалах, сделанные во время работы. Помогите ему в этом. Требуется выдать результаты всех расчетов по числу гвоздиков на разных интервалах.

Если для каждой координаты хранить количество забитых в точку с этой координатой гвоздиков, то подсчет числа гвоздиков на отрезке [X, Y] является запросом Rsq(X, Y) к соответствующему дереву Фенвика. Однако при ограничениях на координаты до 10⁹ такой подход не проходит ни по требуемой памяти, ни по времени работы.

Решением проблемы в данном случае является так называемый "метод сжатия координат”. Отсортируем по координате все точки, встречающиеся во входном файле (их количество не превосходит 2 · 10⁵). Тут надо учитывать как точки, в которые забиваются гвоздики, так и концы отрезков, на которых производится подсчет числа гвоздиков.

Перенумеруем точки в соответствии с их позицией в отсортированном массиве. При этом точкам с одинаковыми координатами присвоим одинаковые номера.

После этого, заменив координаты всех точек их номерами, можно решать задачу с помощью дерева Фенвика, поскольку все номера не превосходят величины 2 · 10⁵.

Задачи для самостоятельного решения

16.1. Инверсии (6)

Задана некоторая перестановка X = (X₁, X₂, …, X_N) чисел от 1 до N. Требуется найти количество инверсий в этой перестановке, то есть количество пар чисел (i, j) таких, что i < j, а X_i > X_j.

Ввод из файла INPUT.TXT. В первой строке задано число N (1   N   60000). Во второй строке заданы через пробел элементы перстановки X₁, X₂, …, X_N.

Вывод в файл OUTPUT.TXT. В единственной строке выводится количество инверсий.

Пример

Ввод

5

4 3 1 5 2

Вывод

6

2. Палиндром (9)

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

Ввод из файла INPUT.TXT. В первой строке задана длина слова N (1   N   10⁶). Во второй строке задано слово из N заглавных латинских букв.

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

Пример

Ввод

ABBYY

Вывод

13

Пояснение. К палиндрому приводит следующая последовательность преобразований:

ABBYY

BABYY

BAYBY

BYABY

BYABY

Подсказка

В данной задаче справедливо жадное решение. Если первая и последняя буквы не совпадают, то нужно обменять одну из них на ближайшую к ней букву, которая совпадает с другой буквой. После этого размерность задачи уменьшается на 2.

Это решение имеет трудоемкость O(N²). На самом деле обмены не требуются. Достаточно помечать буквы признаком удаления. Применение дерева Фенвика позволяет добиться трудоемкости O(N log N).

3. Красные и синие точки (9)

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

Ввод из файла INPUT.TXT. В первой строке находятся через пробел два числа M и N (1   M, N  100000) – количество красных и синих точек соответственно. В следующих M строках задаются координаты красных точек в виде двух целых чисел через пробел. Далее в N строках аналогично задаются координаты синих точек. Все координаты не превосходят по модулю 10⁶.

Вывод в файл OUTPUT.TXT. В единственной строке выводится длина стороны минимального квадрата, содержащего точки обоих цветов.

Пример

Ввод

2 3

0 0

3 5

2 3

4 -1

3 2

Вывод

2

Подсказка

Будем двигать вдоль оси X полосу шириной D, параллельную оси Y. При попадании синей точки в полосу будем делать запрос, есть ли в полосе красные точки, отличающиеся по координате Y от данной синей точки не более, чем на D. Для этого введем массив F, каждый элемент которого определяет количество красных точек с определенной ординатой в текущей полосе. Построим дерево Фенвика, соответствующее массиву F. Как его использовать? Как найти минимальное значение D?

17. "Простые” задачи

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

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

Рассмотрим задачу, название которой говорит само за себя.

Шутка. Найти значение √ 1³+2³+…+N³ при 1  N  10¹² с точностью до 30 знаков. Время счета 1 сек.

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

Все гораздо проще. По индукции доказывается, что

1³ + 2³ +…+ N³ = (1 + 2 +…+ N)² = N²  (N+1)² / 4

Результат вычислений – целое число.

Следующая задача тоже может претендовать на название предыдущей задачи.

Операция Confuse. Пусть A - массив, состоящий из N элементов A₁, ..., A_N (2 ≤ N ≤ 10000). Обозначим его максимальное и минимальное значение через max(A) и min(A) соответственно. Вычислим сумму элементов S = A₁ + A₂ + ... + A_N.

Заменим каждый элемент массива A_i на разность S и этого элемента: A_i:= S - A_i. Такое преобразование массива A назовем операцией Confuse.

Напишите программу, которая по массиву, полученному в результате K-кратного применения операции Confuse (1 ≤ K ≤ 10⁹) к некоторому массиву A, вычислит разность

D = max(A) - min(A).

Можно, конечно, попытаться выполнить в обратном порядке указанные преобразования, но вряд ли стоит это делать. Пусть X - начальный массив, а сумма его элементов S. Обозначим через Y массив, который получается после преобразования. Тогда S - max(X) = min(Y), т. к. отнимая от любой константы наибольшее значение из всех возможных, получаем наименьшее. Аналогично max(Y) = S - min(X). Отсюда

D = max(Y) - min(Y) = S - min(X) - S + max(X) = max(X) - min(X)

Следовательно, нужно найти наибольший и наименьший элемент массива, а затем определить их разность. Временная сложность этого алгоритма O(N), то есть нам достаточно одного прохода по массиву.

А вот задача "с подводными камнями”.

Соединение строк. Задается множество строк. Требуется соединить их в одну так, чтобы она была наименьшей в лексикографическом порядке (по алфавиту).

Оказывается, недостаточно просто отсортировать строки и затем соединить их, как это кажется на первый взгляд. Например, при вводе двух строк ‘ab’ и ‘aba’ такой подход приводит к выводу ‘ababa’, тогда как соединение строк в обратном порядке дает в результате меньшую по алфавиту строку ‘abaab’. Такой эффект может проявиться, когда одна из строк является подстрокой другой строки, но может и не проявиться.

Можно учесть описанный случай простой модификацией пузырьковой сортировки. После ввода строк в массив перед каждым обменом двух соседних строк необходимо проверить соединение этих строк в разном порядке, выяснить, какая из получаемых строк меньше, и проводить обмен только тогда, когда он приводит к меньшей строке.

Рассмотрим следующую задачу, встречавшуюся ранее и допускающую различные способы решения.

Даешь квадрат. Ломаная без самопересечений и самокасаний разделяет четырехугольник на две части, которые не лежат одна внутри другой. Каждая часть представляет собой многоугольник и задается отдельно путем перечисления координат вершин. Определить, является ли исходный четырехугольник квадратом.

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

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

Еще одна задача с простой постановкой. На четвертьфинальных отборочных соревнованиях 2009 года чемпионата мира по программированию в Саратове ее решила единственная команда из 70.

Встречи. Есть пункты A и B с расстоянием между ними L. Навстречу друг другу двигаются велосипедист и пешеход со скоростями V₁ и V₂. Определить, сколько раз они встретятся за первые T секунд. Все числа в диапазоне от 1 до 10⁹.

При начальном анализе можно подумать, что подходит метод заметания или скользящей прямой. Отметим на оси времени ключевые точки, когда велосипедист и пешеход оказываются в пунктах A и B. Добавим к ним конечную точку T. Двигаясь по оси времени слева направо можно отметить такие интервалы, в которых встреча гарантированно происходит. Однако для всех интервалов это сделать невозможно, да и размерность слишком велика. Будем решать иначе.

Рассмотрим сначала случай, когда велосипедист и пешеход двигаются при встрече в противоположных направлениях. Каждый из них перед встречей преодолел целое число отрезков длины L, и еще один отрезок они прошли совместными усилиями. Пусть x -момент их встречи. Тогда

V₁x + V₂x = mL

x = mL / (V₁ + V₂) ≤ T

Отсюда

m ≤ T (V₁ + V₂) / L (1)

Еще одно важное замечание. Если перед встречей велосипедист преодолел m₁ отрезков, а пешеход m₂ отрезков, то m₁ и m₂ - неотрицательные целые числа одинаковой четности. Поскольку m = m₁ + m₂ + 1, то число m нечетно.

Таким образом, количество встреч M при движении в противоположных направлениях равно количеству нечетных чисел в отрезке [0; T (V₁ + V₂) / L].

Перейдем ко второму случаю, когда при встрече велосипедист и пешеход двигаются в одинаковом направлении. Если V₁ = V₂, то такая встреча невозможна. Положим для определенности, что V₁ > V₂, т.е. скорость велосипедиста больше, хотя в условии может оказаться и наоборот. Снова каждый из них перед встречей преодолел целое число отрезков длины L. Пусть велосипедист преодолел n₁ отрезков, а пешеход n₂ отрезков. Получаем

V₁x - V₂x = nL

x = nL / (V₁ - V₂) ≤ T

Отсюда

n ≤ T (V₁ - V₂) / L (2)

Велосипедист изначально отставал на L, поэтому n₁ и n₂ - неотрицательные целые числа разной четности. Поскольку n = n₁ - n₂, то число n нечетно.

Таким образом, количество встреч N при движении в одинаковом направлении равно количеству нечетных чисел в [0; T (V₁ - V₂) / L].

Всегда ли дает ответ суммирование по обоим случаям? Нет! Все рассуждения неявно предполагали, что встречи происходят во внутренних точках отрезка. Если велосипедист и пешеход встречаются в точках A или B, то такие случаи будут учтены дважды.

Пусть, например, L = 30, V₁ = 10, V₂ = 5, T = 6. В случае встречного движения количество нечетных чисел в отрезке [0; T (V₁ + V₂) / L], т.е. в [0; 3] равно 2, а при попутном движении количество нечетных чисел в отрезке [0; T(V₁ - V₂) / L], т.е. [0; 1] равно 1. Тем не менее, общее количество встреч равно 2, а не 3. Действительно, в момент времени x = 6 встреча происходит в точке A, и эта встреча учитывается в каждом из двух случаев.

Для исключения общих точек рассмотрим уравнение

mL / (V₁ + V₂) = nL / (V₁ - V₂),

в котором числа m и n должны иметь разную четность.

Получаем

m / n = (V₁ - V₂) / (V₁ + V₂) = p / q, (3)

где p / q – несократимая дробь. Поскольку числа m и n должны иметь разную четность, остается найти количество пар K чисел вида m = (2j + 1) p, n = (2j + 1) q, удовлетворяющих ограничениям (1) и (2).

Таким образом, общее количество встреч C определяется выражением

C = M + N – K,

где M, N и K определяются из соотношений (1), (2) и (3), как описано выше.

Следующая задача встречалась выше в разделе по динамическому программированию.

Булева функция. Бинарная булева функция f сопоставляет значениям двух булевых аргументов, каждый из которых может быть равен 0 или 1, третье булево значение, называемое результатом. Если задана булева функция f и набор из N булевых значений a₁, a₂, ..., a_N , каждое из которых равно 0 или 1, то результат цепного вычисления этой булевой функции определяется следующим образом:

• если N = 1, то он равен a₁;

• если N >1, то он равен результату цепного вычисления булевой функции f для набора из (N–1) булевого значения f(a₁,a₂), a₃, …, a_N.

Задана таблица истинности функции в виде четырех значений, задающих результаты вычисления функции для значений аргументов 0 и 0, 0 и 1, 1 и 0, 1 и 1. Необходимо для заданного значения N вывести такую строку из N символов a_i, чтобы результат цепного вычисления функции был равен единице, а в строке содержалось максимально возможное число единиц. Если ответов несколько, выдать любой из них. Если такого набора значений a_i не существует, вывести слово No.

Подход динамического программирования ведет к достаточно сложной программной реализации. Можно предположить, что имеются закономерности, проявляющиеся при любых значениях N. Имеется 16 различных наборов значений булевой функции. Переберем их все вручную и найдем ответы. Реально перебор значительно сокращается. Введем следующие обозначения:

• Z₁ = f(0, 0);

• Z₂ = f(0, 1);

• Z₃ = f(1, 0);

• Z₄ = f(1, 1);

• S – входная строка из 4 битовых значений Z₁ Z₂ Z₃ Z₄;

• T – ответ – строка из N битовых значений.

Если S = 0000, то решений нет.

Если Z₄ = 1, то T состоит только из единиц. Рассмотрим остальные случаи при Z₄ = 0:

• если S = 0010, то T = 1000…0 – единственная строка, для которой f(S) =1;

• если S = 0100 или S =0110, то при N четном T = 111…01 (всего N-1 единица, на строке из N единиц f = 0), а при N нечетном T = 111…1 (все N битов единицы);

• если S = 1000 или S = 1100, то T = 111…10 (всего N-1 единиц, на строке из N единиц f =0);

• если S = 1100 или S = 1110, то при N четном T = 011…1 (всего N-1 единица, на строке из N единиц f = 0), при N нечетном T = 111…1 (все N битов единицы).

Таким образом, достаточно сформировать и выдать ответ по каждому случаю. Это доступно в Турбо Паскале даже для предельно большого значения N = 100000.