Задача
Международный номерной регистрационный знак легкового автомобиля состоит из $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 |
Код
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
#include <iostream> #include <string.h> using namespace std; void print(char * x, int n) { // функция вывода массива чисел for (int i = n - 1; i >= 0; i--) { cout << (int) x[i]; } } int MULT(char * x, char * y, char * z, int n, int m) { // функция для перемножения больших чисел memset(z, 0, n + m); // обнуляем массив for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { char w = x[j] * y[i] + z[i + j]; z[i + j + 1] += w / 10; z[i + j] = w % 10; } } int res = (z[n + m - 1] == 0) ? (n + m - 1) : (n + m); // кол-во разрядов return res; } const int N = 100; // кол-во элементов массивов с небольшим запасом char acc[N] = {1}; int acc_size = 1; char tmp[N] = {0}; char v_26[] = {6, 2}; // 26 int main() { int A, B; // входные данные cin >> B >> A; for (int i = 0; i < B; i++) { // возведение 26 в степень B memcpy(tmp, acc, acc_size); acc_size = MULT(tmp, v_26, acc, acc_size, 2); // 2 - число разрядов в 26 } print(acc, acc_size); // вывод результата for (int i = 0; i < A; i++){ // домножение на 10 в степени A cout << "0"; } return 0; } |
Решение
Начнем с того, что к условию задачи прилагается картинка, на которой видно, что во всех номерных знаках буквы и цифры не перемешаны между собой произвольно, а имеют свои четко распределенные места, в примере это последовательность, в которой на первой позиции стоит буква, далее три цифры и на последних двух позициях снова буквы. Это важный момент, поскольку если бы действительно было разрешено использовать любую последовательность, возможных комбинаций было бы гораздо больше. Поскольку в латинском алфавите $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
