Задача 27
А вот эта задача очень простая. Бывает трёх видов (сводящихся к одной и той же схеме):
- выбрать из кучи пар чисел по одному числу так, чтобы что-нибудь максимизировать или минимизировать
- найти самый частовстречающийся результат какого-нибудь отображения, применённого к каждому элементу массива
- редуцировать (в какой-нибудь полугруппе) все пары элементов массива, индексы которых в этом массиве различаются не менее чем на заданную величину
И то, и другое нужно либо сделать хоть как-то (тогда за задачу дадут 2 балла), либо за один проход по входным данным, не сохраняя их в массив (тогда за задачу дадут 4 балла).
Редукция
Самая частая разновидность.
Типичное задание: найти количество пар разных элементов входного массива, сумма которых делится на 6. Обратите внимание на то, что в конкретно этой задаче неявно присутствует минимальное ограничение на разность индексов элементов пары, равное 1.
#include <iostream>
#include <deque>
#include <map>
using namespace std;
int main() {
unsigned N; cin >> N; // входной размер массива
deque<unsigned> queue; // задержка между получением элементов и обработкой
map<unsigned,unsigned> mod_count; // таблица количеств по остаткам
unsigned answer = 0;
for (unsigned i = 0; i < N; i++) {
unsigned x; cin >> x;
queue.push_back(x);
if (i < 1) { continue; }
mod_count[queue.front()%6] += 1;
queue.pop_front();
unsigned mod = queue.back()%6;
answer += mod_count[(6 - mod) % 6];
}
cout << answer << endl;
}
Может показаться, что очередь длины 1 — весьма странное решение, но в некоторых
ситуациях любые альтернативы (кроме банальных замен deque на две переменных)
оказываются более сложными. Всегда есть соблазн (если в условии ничего
явно не сказано при минимальную разность индексов) просто завести
несколько переменных, в каждую из которых редуцировать неким образом
все элементы массива, а затем написать одну большую формулу, выражающую
ответ в терминах этих переменных. Такой соблазн лучше игнорировать.
Рассмотрим ещё одно похожее задание: найти максимальное произведение пары элементов входного массива (все элементы — целые положительные числа), индексы которых различаются хотя бы на 6, делящееся на 15.
#include <iostream>
#include <deque>
#include <map>
using namespace std;
int main() {
unsigned N; cin >> N;
deque<unsigned> queue;
map<unsigned,unsigned> mod_max; // таблица максимумов по остаткам
unsigned answer = 0;
for (unsigned i = 0; i < N; i++) {
unsigned x; cin >> x;
queue.push_back(x);
if (i < 6) { continue; } // здесь поменялась длина очереди
unsigned mod = queue.front() % 15;
mod_max[mod] = max(mod_max[mod], queue.front()); // сумма сменилась на максимум
queue.pop_front();
mod = queue.back()%15;
if (mod == 0) {
for (unsigned m = 0; m < 15; m+=1) { answer = max(answer, queue.back()*mod_max[m]); }
} else if (mod % 3 == 0) {
for (unsigned m = 0; m < 15; m+=5) { answer = max(answer, queue.back()*mod_max[m]); }
} else if (mod % 5 == 0) {
for (unsigned m = 0; m < 15; m+=3) { answer = max(answer, queue.back()*mod_max[m]); }
}
}
cout << answer << endl;
}
Таблица частот
Требуется, например, найти и напечатать самую частую первую цифру десятичной записи чисел. Задание весьма тривиально, если завести таблицу частот цифр.
#include <iostream>
#include <map>
using namespace std;
unsigned first_digit(unsigned x) {
while (x > 9) { x /= 10; }
return x;
}
int main() {
unsigned N; cin >> N;
map<unsigned,unsigned> digit_freq;
for (unsigned i = 0; i < N; i++) {
unsigned x; cin >> x;
digit_freq[first_digit(x)] += 1;
}
// дальнейшее написано в предположении, что
// если несколько частот совпадают, то нужно вывести
// наибольшую из цифр
unsigned best_digit = 0;
unsigned best_freq = digit_freq[0];
for (unsigned digit = 1; digit <= 9; digit++) {
if (digit_freq[digit] >= best_freq) {
// если бы требовалось вывести наименьшую из цифр,
// достаточно было бы поменять знак на >
best_freq = digit_freq[digit];
best_digit = digit;
}
}
cout << best_digit << endl;
}
Выбор одного из двух
Типичное задание таково. На вход подаются пары (целых положительных) чисел. Нужно выбрать из каждой пары одно число так, чтобы:
- сумма выбранных чисел не делится на 42
- она является максимальной среди возможных
Если такой выбор сделать нельзя, требуется напечатать 0. В противном случае нужно напечатать сумму.
Ключевой момент заключается в том, что:
- либо подходит сумма наибольших (в каждой паре) чисел
- либо в одной из пар можно взять вместо наибольшего числа наименьшее
- либо сумма наибольших чисел и все разности в парах делятся на 42 и, соответственно, любой выбор чисел имеет сумму, делящуюся на 42
Это приводит к следующему решению (очень напоминающему решение типичной 25 задачи):
#include <iostream>
using namespace std;
int main() {
unsigned N; cin >> N;
unsigned large = 10001; // ограничение сверху плюс один
unsigned total = 0; // сумма наибольших
unsigned min_diff = large; // минимальная из разностей, не делящихся на 42
for (unsigned i = 0; i < N; i++) {
unsigned x,y; cin >> x >> y;
total += max(x,y);
unsigned diff = max(x,y) - min(x,y);
if (diff % 42 != 0) {
min_diff = min(min_diff, diff);
}
}
unsigned answer = total;
if (answer % 42 == 0 and min_diff != large) {
answer -= min_diff;
}
if (answer % 42 == 0) {
answer = 0;
}
cout << answer << endl;
}
Общая схема
Нетрудно заметить, что вторая и третья разновидности задачи являются частными случаями первой с нулевой длиной очереди.
Собственно, общая схема решения предполагает следующие входные данные:
- начальное состояние и начальный ответ
- величину задержки (длину очереди)
- функцию обновления состояния по элементу, удалённому из очереди
- функцию обновления ответа по состоянию и элементу, пришедшему в очередь
Эту схему можно записать (на хаскеллоподобном языке) так:
solve :: s -> a -> Int -> (x -> s -> s) -> (x -> s -> a -> a) -> [x] -> a
solve s0 a0 n updateS updateA xs = go s0 a0 $ zip xs (drop n xs)
where
go _ a [] = a
go s a ((old,new):rest) =
let s' = (updateS old s)
in go s' (updateA new s' a) rest
По-научному такая схема (а точнее говоря, некоторое её обобщение) называется зигохистоморфизмом.
Казалось бы, причём здесь зигохистоморфные препроморфизмы?..