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

20/12/2019 by Таня Осипенко

Задача

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

Похожее

8 thoughts on “e-olymp 1290. Номерной знак”

Мазурок Игорь Евгеньевич says: 21/12/2019 at 00:32

Интересно.
Обязательно обсудим ваше решение на экзамене.
Только…
— Поставьте метки (ключевые слова);
— Расширьте объяснение. Если бы все задача состояла в простом вычислении $26^B\cdot 10^A$, то код был бы горздо кроче. В чем была основная сложность?
— Вы вычислили количество номерных знаков в которых идут сначала все буквы, потом все цифры. И еще столько же их будет если сначала будут идте все цифры. А еще их можно переставлять. Значит их гораздо больше. Как же так? Решение прошло все тесты? Пожалуйста, прочтите страницу обсуждения задачи и дайте уточнение условия.
— В обсуждении автор сказал, что картинка является частью условия. А Вы ее не привели…

Войдите, чтобы ответить
- Таня Осипенко says: 21/12/2019 at 08:07
  
  Игорь Евгеньевич, спасибо за подробный комментарий. Вроде у меня стоят метки. А по поводу условия, естественно, я заметила, что вариантов перестановки гораздо больше, если перемешивать цифры и буквы между собой, но тесты проходят только, если «зафиксировать» место цифр или букв, то есть рассматривать вариант, когда они между собой не перемешаны. Я решила, что это недочет в условии задачи. И хотелось бы уточнить. Под расширением описания Вы имеете в виду объяснение сложности вычисления огромных чисел?
- Мазурок Игорь Евгеньевич says: 21/12/2019 at 19:46
  - С метками видимо что-то не заметил. Все есть. Хоть и без главных, о чем именно задача — «длинная арифметика» или «умножение длинных чисел».
  - Обсуждение так и не прочли? Автор задачи утверждает, что рисунок является частью условия. Рисунок же (вроде бы?) задает определенный формат: Одна буква, все цифры, остальные буквы. Только если формат фиксирован, формула работает. И, да, я тоже считаю, что это недочет в условии. Но автору я оценку не ставлю. А Вам нужно в решении указать в каких предположениях выводилась формула.
  - Да, я имею в виду длинную арифметику. Вы реализовали некоторую функцию, которую называете «перемножение массивов» это не очень удачный термин. Во всем интернете он встречается только 361 раз и ни разу с тем значением, которое вы подразумеваете. Значит нужно подробно объяснить этот момент — что функция делает, какой алгоритм реализует. И постарайтесь это сделать в общепринятой терминологии. Фактически Вы ведь не массивы перемножаете, а то, что они хранят. Иначе большинство законов физики называлось бы законами о перемножении переменных 🙂
- Таня Осипенко says: 21/12/2019 at 22:46
  
  Игорь Евгеньевич, спасибо еще раз, постаралась учесть все Ваши замечания
Мазурок Игорь Евгеньевич says: 22/12/2019 at 00:37
- Вы пишите «проблема возведения чисел в большую степень является проблемой перемножения больших чисел». У вас нет больших степеней — максимум 26. Но в любом случае, это совершенно разные проблемы. При больших степенях думают как уменьшить число вполне себе обычных умножений. А перемножение больших целых чисел затруднено наличием фиксированной разрядности в большинстве языков программирования.
- Этого я вообще не понял «…с переводом разрядов при выходе из выбранной десятичной системы». Что значит выход из системы счисления?
- Если Вам нужна десятичная запись числа $10^A$, то я знаю ответ — единичка и $A$ ноликов. Я даже могу подсказать как умножить на эту степень любое число — просто дописать к нему $A$ ноликов. Зачем Вы та усложнили эту часть программы?
- Удивительно, но существует довольно много алгоритмов умножения чисел в позиционной системе счисления. И даже несколько конкретно поразрядных алгоритмов. Вы пишите «осуществляет алгоритм умножения в столбик». Умножение в столбик предполагает наличие столбика. Т.е. необходимость запоминания и суммирования нескольких целых чисел (по числу разрядов второго сомножителя. Ничего подобного вы не делаете. У Вас другой алгоритм.
Войдите, чтобы ответить
- Таня Осипенко says: 22/12/2019 at 13:17
  
  Спасибо за замечания, упростила код, убрав цикл возведения 10 в степень А, к остальным замечаниям тоже прислушалась, надеюсь, теперь написано все грамотно.
- Мазурок Игорь Евгеньевич says: 22/12/2019 at 18:41
  
  Я зачту работу, но описание алгоритма понятнее не стало. Я подумаю, как аргументировать это заявление.
- Таня Осипенко says: 22/12/2019 at 18:54
  
  Спасибо, Игорь Евгеньевич.