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

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

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

    • Игорь Евгеньевич, спасибо за подробный комментарий. Вроде у меня стоят метки. А по поводу условия, естественно, я заметила, что вариантов перестановки гораздо больше, если перемешивать цифры и буквы между собой, но тесты проходят только, если «зафиксировать» место цифр или букв, то есть рассматривать вариант, когда они между собой не перемешаны. Я решила, что это недочет в условии задачи. И хотелось бы уточнить. Под расширением описания Вы имеете в виду объяснение сложности вычисления огромных чисел?

      • С метками видимо что-то не заметил. Все есть. Хоть и без главных, о чем именно задача — «длинная арифметика» или «умножение длинных чисел».
      • Обсуждение так и не прочли? Автор задачи утверждает, что рисунок является частью условия. Рисунок же (вроде бы?) задает определенный формат: Одна буква, все цифры, остальные буквы. Только если формат фиксирован, формула работает. И, да, я тоже считаю, что это недочет в условии. Но автору я оценку не ставлю. А Вам нужно в решении указать в каких предположениях выводилась формула.
      • Да, я имею в виду длинную арифметику. Вы реализовали некоторую функцию, которую называете «перемножение массивов» это не очень удачный термин. Во всем интернете он встречается только 361 раз и ни разу с тем значением, которое вы подразумеваете. Значит нужно подробно объяснить этот момент — что функция делает, какой алгоритм реализует. И постарайтесь это сделать в общепринятой терминологии. Фактически Вы ведь не массивы перемножаете, а то, что они хранят. Иначе большинство законов физики называлось бы законами о перемножении переменных 🙂
    • Игорь Евгеньевич, спасибо еще раз, постаралась учесть все Ваши замечания

    • Вы пишите «проблема возведения чисел в большую степень является проблемой перемножения больших чисел». У вас нет больших степеней — максимум 26. Но в любом случае, это совершенно разные проблемы. При больших степенях думают как уменьшить число вполне себе обычных умножений. А перемножение больших целых чисел затруднено наличием фиксированной разрядности в большинстве языков программирования.
    • Этого я вообще не понял «…с переводом разрядов при выходе из выбранной десятичной системы». Что значит выход из системы счисления?
    • Если Вам нужна десятичная запись числа $10^A$, то я знаю ответ — единичка и $A$ ноликов. Я даже могу подсказать как умножить на эту степень любое число — просто дописать к нему $A$ ноликов. Зачем Вы та усложнили эту часть программы?
    • Удивительно, но существует довольно много алгоритмов умножения чисел в позиционной системе счисления. И даже несколько конкретно поразрядных алгоритмов. Вы пишите «осуществляет алгоритм умножения в столбик». Умножение в столбик предполагает наличие столбика. Т.е. необходимость запоминания и суммирования нескольких целых чисел (по числу разрядов второго сомножителя. Ничего подобного вы не делаете. У Вас другой алгоритм.
    • Спасибо за замечания, упростила код, убрав цикл возведения 10 в степень А, к остальным замечаниям тоже прислушалась, надеюсь, теперь написано все грамотно.

Добавить комментарий