Задача

Международный номерной регистрационный знак легкового автомобиля состоит из $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

Код

#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;
}

#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

Related Images:

Задача

Отель имеет $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

Код

#include <iostream>
using namespace std;

int main() {
    long n, m; // Объявляем переменные (кол-во этажей и номеров на каждом из них)
    cin >> n >> m; // считываем входные данные
    cout << (n - 1) * m * 3; // выводим ответ
    return 0;
}

#include <iostream>

using namespace std;

int main() {

long n, m; // Объявляем переменные (кол-во этажей и номеров на каждом из них)

cin >> n >> m; // считываем входные данные

cout << (n - 1) * m * 3; // выводим ответ

return 0;

}

Решение

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