Две простые олимпиадные задачи на использование сортировки подсчетом

Задача “Палиндром”

Палиндром — это строка, которая читается одинаково как справа налево, так и слева направо.

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

Формат входных данных

В первой строке записано число N (1 N 100 000). Во второй строке записана последовательность из
N больших латинских букв (буквы записаны без пробелов).

Формат выходных данных

В единственной строке выдайте искомый палиндром.

Примеры

Входные данные	Выходные данные
3 AAB	ABA
6 QAZQAZ	AQZZQA
6 ABCDEF	A

 

Решение

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

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

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

Исходя из этого, можно построить решение для случая, когда все буквы входят в строку четное количество раз. Будем идти по буквам, начиная с меньших по алфавиту, и выводить каждую вдвое меньше раз, чем она входила в исходную строку. После этого необходимо вывести вторую половину палиндрома. Ее вывод отличается только тем, что перебирать буквы нужно от больших к меньшим (от Z к A).

Теперь рассмотрим случай, когда буквы встречаются нечетное количество раз. По свойству палиндрома можно понять, что каждая буква должна иметь пару (т.е. входить в палиндром четное количество раз), кроме, возможно, одной буквы, которая будет находиться ровно посередине палиндрома (она будет парной “сама с собой”). Таким образом, для случая с нечетным количеством букв генерация “половинок” палиндрома будет полностью совпадать с четным случаем, но между половинками будет еще одна буква. Критерии выбора этой буквы следующие: во-первых, она должна входить в строку нечетное число раз, а во-вторых, среди всех букв, входящих нечетное количество раз, она должна быть наименьшей в алфавитном порядке (это требуется для того, чтобы сгенерировать наименьший в алфавитном порядке палиндром).

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

var
i, n : integer;
c : char;
symb : array['A'..'Z'] of longint;
begin
for c := 'A' to 'Z' do // заполняем нулями
symb[c] := 0;
readln(n);
for i := 1 to n do begin
read(c);
// увеличиваем на 1 соответствующий элемент
inc(symb[c]);
end;
for c := 'A' to 'Z' do
for i := 1 to symb[c] div 2 do
write(c); // первая половина палиндрома
for c := 'A' to 'Z' do
// ищем "нечетный" символ
if symb[c] mod 2 = 1 then begin
write(c);
// вывели его, остальные нечетные
// неинтересны
break;
end;
for c := 'Z' downto 'A' do
for i := 1 to symb[c] div 2 do
// вторая половина палиндрома
write(c);
end.

Задача “Шифровка”

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

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

Формат входных данных

Во входном файле записано целое число N — количество чисел
(1 N 300 001). Далее записано N целых чисел Mi (1 Mi 2•10⁹).

Формат входных данных

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

Пример

Входные данные	Выходные данные
11 3 1 2 3 1 3 2 2 1 3 3	3

Решение

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

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

Теперь попробуем найти решение для двузначных чисел. В принципе мы можем сделать “сортировку подсчетом” для всех чисел от 0 до 99, и этот метод будет работать. Но наша задача подразумевает числа до двух с лишним миллиардов и таким методом уже не решится, хотя бы потому, что мы не имеем доступа к 8 гигабайтам памяти. Поэтому будем искать правильное решение на примере двузначных чисел.

Поступим следующим образом: разобьем каждое двузначное число на разряд десятков и разряд единиц (однозначные числа будут иметь в качестве разряда десятков 0). Таким образом, мы получим две цифры, для которых можно по отдельности применить описанное выше решение задачи для цифр! После этого из двух полученных в качестве ответа цифр мы с легкостью можем получить ответ: умножим цифру десятков на 10 и прибавим к ней цифру единиц.

Аналогично составляется решение и для полной задачи, только вместо 2 используется уже 10 разрядов.

var
table : array [1..10, 0..9] of longint;
  i, j, k, n : longint;
begin
for i := 1 to 10 do
for j := 0 to 9 do
// заполняем таблицу нулями
table[i, j] := 0;
read(n);
for i := 1 to n do begin
read(k);
j := 1; // номер разряда
while k <> 0 do begin
// на месте j добавилась цифра k mod 10
inc(table[j, k mod 10]);
// выкидываем последнюю цифру
k := k div 10;
// переходим к следующему разряду
inc(j);
end;
end;
k := 0; // здесь будем восстанавливать число
// начиная со старших разрядов
for i := 10 downto 1 do begin
// переходим к следующей цифре
k := k * 10;
// перебираем все цифры
for j := 0 to 9 do
// нашли "секретную" цифру
if table[i, j] mod 3 <> 0 then
// и прибавляем ее к ответу
k := k + j;
end ;
write(k);
end .

У этой задачи существует и другое решение, в котором используется тема “системы счисления”. Представим каждое число в троичной системе счисления. Каждый троичный разряд будем рассматривать отдельно. Воспользуемся тем, что каждое число встречается трижды, т.е. в каждом разряде одна и та же цифра (допустим, x) встречается три раза. При суммировании в этом разряде получим 3•x. Будем проводить поразрядное суммирование по модулю 3 (т.е. после каждого суммирования брать в каждом разряде остаток от деления на 3). Так как порядок слагаемых не имеет значения, то все тройки чисел дадут в каждом разряде 0 (остаток от деления 3•x на 3 равен 0 независимо от значения x). В итоге, после такого суммирования всех чисел мы получим искомое число в троичной системе счисления (все остальные в сумме дадут 0 во всех разрядах). Остается только перевести это число в десятичную систему счисления и вывести его. При этом количество разрядов в троичном числе определяется из соотношения 3^m 2•10⁹. Подбором легко определить минимальное m = 20.

Мы научились восстанавливать число, если оно встречалось один раз (или 3k + 1 раз). Если число встречалось дважды (или 3k + 2 раза), то следует в каждом разряде 2 заменить на 1, а 1 — на 2. Это объясняется тем, что два числа, имеющие 1 в данном разряде, в сумме дадут 2, а две 2 – 1 (2 + 2 = 4, берем остаток от деления на 3 и получаем 1). Самый простой способ произвести замену — умножить каждый разряд на 2 и взять остаток от деления на 3. Для нулей ничего не меняется, они и в сумме дают ноль. Определить, какой из случаев имеет место, можно, посчитав остаток от деления на 3.