ОЛИМПИАДЫ

М.С. Густокашин,
Москва

Задача "Минимальное число"

Дано натуральное четырехзначное число. Найдите минимальное натуральное четырехзначное число, состоящее из тех же цифр, что и заданное. Заметим, что четырехзначные числа не могут начинаться с нуля.

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

Натуральное четырехзначное число.

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

Натуральное минимальное четырехзначное число, состоящее из тех же цифр.

Примеры

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

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

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

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

var

digits : array[0..9] of integer;

i, j, n : integer;

begin

for i := 0 to 9 do

digits[i] := 0; // вначале цифр нет

read(n);

for i := 1 to 4 do begin // всего их будет четыре

j := n mod 10; // вынимаем последнюю

// прибавляем 1 к соответствующему счетчику

inc(digits[j]);

n := n div 10 // и убираем последнюю

end;

// ищем первую цифру (кроме 0)

for i := 1 to 9 do

if digits[i] > 0 then begin // нашли

write(i); // выводим

dec(digits[i]); // ее уже использовали

break // выходим из цикла

end;

for j := 1 to 3 do // выводим три оставшихся

// теперь ищем уже с нуля

for i := 0 to 9 do

if digits[i] > 0 then begin // нашли

write(i); // выводим

dec(digits[i]); // уменьшаем счетчик

break // выходим из цикла

end

end.

Задача "Шаблоны"

Шаблоном размера п назовем строку длины п, каждый из символов которой входит в множество {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, a, b, c, d, e, f, g, ?}. Шаблоны преобразуются в строки из цифр по следующим правилам:

символы от 0 до 9 могут быть преобразованы только сами в себя;

символ а может быть преобразован в любой из символов 0, 1, 2, 3;

символ b может быть преобразован в любой из символов 1, 2, 3, 4;

символ с может быть преобразован в любой из символов 2, 3, 4, 5;

символ d может быть преобразован в любой из символов 3, 4, 5, 6;

символ е может быть преобразован в любой из символов 4, 5, 6, 7;

символ f может быть преобразован в любой из символов 5, 6, 7, 8;

символ g может быть преобразован в любой из символов 6, 7, 8, 9;

символ ? может быть преобразован в любой из символов от 0 до 9.

Даны два шаблона: р1 и р2. Рассмотрим множество S1 строк, которые могут быть получены из p1 по описанным правилам, и множество S2 строк, которые могут быть получены из р2. Необходимо найти количество строк, входящих в оба этих множества.

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

Первая строка входного файла содержит шаблон р1, вторая — шаблон р2. Шаблоны имеют одинаковый положительный размер, не превосходящий 9.

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

Примеры

Решение

Сначала научимся решать задачу для одной буквы, а затем переделаем ее в полное решение. Для заданной (в нашем случае единственной) позиции определим, какие цифры могут стоять на этом месте, и пометим их в булевском массиве. Проделаем эту операцию для обоих шаблонов и в результате получим два булевских массива с индексами от 0 до 9, где на месте возможной цифры будет стоять true, а на месте невозможной — false. Остановимся на заполнении массива более подробно. Конечно, можно для всех 18 допустимых символов описать, какие цифры можно поставить на этом месте, но такой код будет очень длинным. На самом деле можно разбить все символы на 3 класса: цифры, буквы и знак вопроса (?). Так как цифры и буквы алфавита кодируются последовательными числами, то по известному коду символа, соответствующего цифре, мы можем получить саму эту цифру. Для этого достаточно вычесть из кода цифры код нуля. Аналогично определяется порядковый номер буквы в алфавите. Теперь посмотрим более подробно на буквы. Если нумеровать буквы с нуля (т.е. букве a соответствует цифра 0), то можно заметить, что каждая буква покрывает 4 цифры, начиная со своего порядкового номера в алфавите. То есть нам достаточно запомнить позицию, начиная с которой мы будем заполнять (это цифра или номер буквы в алфавите), и сколько элементов помечать (1 для цифры и 4 для буквы). Вопросительный знак следует проверять отдельно и действовать по той же схеме: начальная позиция у него равна нулю, а заполнять надо все 10 цифр. После этого достаточно просто пройти циклом от начальной позиции до начальной позиции плюс количество и поставить везде true.

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

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

Что касается размера переменных, то нам достаточно 32-битного типа longint, так как в худшем случае на всех 9 позициях будут стоять вопросительные знаки, что в итоге даст ответ 10⁹.

var

p1, p2 : string[10];

s : array[1..2, 0..9] of boolean;

n, i, j, k, answer, nowans : longint;// определение подходящих цифр

procedure fill(c : char; num : longint);

var

pj, st, len : longint;

// пока никакие цифры не подходят

for pj := 0 to 9 do

s[num, pj] := false;

// была цифра

if (c in ['0'..'9']) then begin

// определяем, что за цифра

st := ord(c) — ord('0');

len := 0; // и за ней никого размечать не будем

// буква

end else if (c in ['a'..'g']) then begin

// определяем номер по алфавиту

st := ord(c) — ord('a');

// и 3 следующих за ней тоже допустимы

len := 3

// вопросительный знак

end else if (c = '?') then begin

st := 0; // начиная с нуля

len := 9 // и оставшиеся 9 цифр за ней

end else st := -1; // а вдруг что-то другое?

// если что-то другое — то ничего не делаем

if (st <> -1) then

// расставляем true

for pj := st to st+len do

s[num, pj] := true

end;

begin

answer := 1; // будем накапливать ответ тут

readln(p1); readln(p2); // считали строки

// посчитали длину — она совпадает

n := length(p1);

// идем по всем позициям

for i := 1 to n do begin

fill(p1[i], 1); // заполняем первый массив

fill(p2[i], 2); // и второй

// на данной позиции пока может стоять 0 цифр

nowans := 0;

for j := 0 to 9 do // идем по цифрам

if (s[1, j] = true) and (s[2, j] = true) then

// подходит

// увеличиваем на 1 число подходящих

inc(nowans);

// и умножаем на это ответ

answer := answer * nowans

end;

writeln(answer)

end.