e-olymp 1290. Номерной знак

Задача

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

Сколько существует различных таких номеров?

Входные данные

В единственной строке через пробел $2$ неотрицательных целых числа $B$ и $A$. Оба числа не превышают $26$.

Выходные данные

Единственное число — ответ к задаче.

Тесты

Входные данные Выходные данные
1 3 3 17576000
2 2 5 67600000
3 7 1 80318101760
4 1 1 260
5 26 26 615611958020715731079667428840020377600000000000000000000000000

Код

Решение

Начнем с того, что к условию задачи прилагается картинка, на которой видно, что во всех номерных знаках буквы и цифры не перемешаны между собой произвольно, а имеют свои четко распределенные места, в примере это последовательность, в которой на первой позиции стоит буква, далее три цифры и на последних двух позициях снова буквы. Это важный момент, поскольку если бы действительно было разрешено использовать любую последовательность, возможных комбинаций было бы гораздо больше. Поскольку в латинском алфавите $26$ букв, для выбора буквы на первое место существует $26$ возможных вариантов, на второе тоже $26$, как и на третье, четвертое и т. д. То есть для того чтобы найти все комбинации из букв для $B$ мест, нужно умножить $26$ на $26$ $B$ раз. Точно так же это работает с арабскими цифрами. Их всего $10$, соответственно, умножаем $10$ на $10$ $A$ раз, где $A$ — количество мест в номерном знаке для цифр. Поэтому, чтобы найти количество возможных комбинаций букв и цифр, перемножаем полученные результаты. Отсюда получаем формулу $26^B\cdot 10^A$.

Сложность задачи заключается скорее не в формуле вычисления, а в реализации кода, поскольку большинство значений уже на этапе возведения в степень не помещаются даже в самые большие типы данных. Именно поэтому код состоит не из пяти строк и встроенной операции возведения в степень, а из более сложных операций, подходящих для работы с большими числами. По сути, у нас возникает проблема, связанная с перемножением больших чисел, которые не помещаются в стандартные типы данных С++. Для решения этой проблемы я выбрала модель представления, в которой числа записываются в виде массивов в десятичной системе, и каждая цифра числа является элементом массива. Младший разряд числа находится в нулевом элементе массива, а старший в $n-1$-ом соответственно. Далее была реализована функция «MULT», которая фактически осуществляет алгоритм умножения поэлементно с сохранением остатка от деления на $10$ в соответствующем элементе массива и добавлением частного от деления на $10$ к следующему элементу массива. Следует отметить, что данная функция принимает два числа, записанные в выше указанной модели представления (в виде массивов), и характеристиками этих чисел является пара: сам массив и количество разрядов в числе (размер массивов иными словами). На выходе функция возвращает количество разрядов полученного произведения. Сам же результат умножения сохраняется в виде массива, который является одним из параметров функции. В коде данная функция внесена в цикл для многократного перемножения чисел, то есть для возведения в нужную степень. Домножение на $10^A$ осуществляется в последнем цикле приписыванием A нулей к полученному результату.

Ссылки

Задача на сайте e-olymp
Код решения на ideone

e-olymp 8254. Номера отеля

Задача

Отель имеет $n$ этажей. Лобби, ресторан и тренажерный зал расположены на первом этаже. Номера находятся со 2-го по $n$-ый этажи. На каждом этаже расположено $m$ стандартных номеров. Если каждый стандартный номер вмещает 3 гостя, какое наибольшее количество гостей может поместиться во всех стандартных номерах отеля?

Входные данные

Два натуральных числа $n$ и $m$ ($n, m\leqslant10^6$).

Выходные данные

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

Тесты

Входные данные Выходные данные
1 5 10 120
2 3 1 6
3 2 5 15
4 7 2 36
5 20001 450000 270000000000

Код

Решение

Для решения данной задачи выводим формулу $(n-1) \cdot m \cdot 3$, первый из сомножителей — количество этажей, на которых располагаются номера, второй — количество номеров на каждом из указанных этажей, третий — максимальное количество гостей в каждом номере. Заметим, что по условию на первом этаже номера отсутствуют, поэтому первый сомножитель в формуле будет на единицу меньше, чем количество этажей в отеле.

Ссылки

Задача на сайте e-olymp
Код решения на ideone