Задача
В натуральном числе $A$ удалили некоторые цифры так, чтобы получить наибольшее натуральное число $B$ с разными цифрами. Какое это число?
Входные данные
Натуральное число $x \ (1 \leqslant x \leqslant 10^{100})$.
Выходные данные
Натуральное число $B$.
Тесты
| № | Входные данные | Выходные данные |
| 1 | 575747 | 754 |
| 2 | 123231 | 321 |
| 3 | 314159265359 | 4192653 |
| 4 | 1092010 | 9210 |
| 5 | 112221332 | 213 |
Код
|
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 42 43 44 45 46 47 48 49 50 |
#include <iostream> #include <cstring> #include <set> #include <vector> #include <algorithm> using namespace std; int main() { string current_number; string ansver = ""; cin >> current_number; set<char> digits_set; // Инициализируем и заполняем множество со всеми цифрами начального числа for (int i = 0; i < current_number.size(); i++){ char element = current_number[i]; digits_set.insert(element); } std::vector<char> digits; for (char i : digits_set){ digits.push_back(i); } std::reverse(digits.begin(), digits.end()); // Располагаем цифры в порядке убывания while (digits.size() != 1){ // Повторяем, пока не нашли все цифры кроме последней for (int i=0; i < digits.size(); i++){ // Перебираем цифры в порядке убывания char local_max = digits[i]; int position = current_number.find(local_max); string new_number; for (int j = position; j < current_number.size(); j++){ // Делаем срез по элементу new_number += current_number[j]; } set<char> digits_on_the_right; for (int j = 0; j < new_number.size(); j++){ // Находим цифры нового числа digits_on_the_right.insert(new_number[j]); } if (digits.size() == digits_on_the_right.size()){ // Проверяем, сохранится ли ранг ответа ansver += local_max; digits.erase(digits.begin() + i); string number_without_digit = ""; for (int t = 0; t < new_number.size(); t++){ // Удаляем добавленную в ответ цифру из числа if (new_number[t] != local_max){ number_without_digit += new_number[t]; } } current_number = number_without_digit; break; // Останавливаем цикл, т.к. необходимая цифра на позицию уже найдена } } } cout << ansver + digits[0]; // Добавляем к ответу последнюю оставшуюся цифру return 0; } |
Нажмите здесь, чтобы выполнить этот код.
Решение
По условию, нам предстоит работать с натуральным числом, но для решения задачи более оптимально рассматривать его как строку с одним важным уточнением: ноль не может быть первым символом этой строки. Легко видеть, что в ответе должны фигурировать все цифры из «входных данных» — наибольшим будет число максимально возможного порядка. Следовательно, для каждого разряда числа нам нужна такая цифра, выбор которой не уменьшит разрядность в дальнейшем.
Рассмотрим пример: для числа $121323$ правильным ответом будет $213$.
Ход рассуждений следующий: поскольку в числе содержатся три цифры, ответ также будет трехзначным. Наибольшая цифра в числе — 3, следовательно, она должна быть первой цифрой ответа. Для выполнения этого условия придется «вычеркнуть» все предыдущие цифры, но тогда мы сможем получить лишь двухзначное число $32$. Следующим кандидатом является двойка, и этот выбор нас полностью устраивает, поскольку справа от нее есть остальные цифры «входного» числа. Записав в ответ $2$, рассмотрим число за ней: $1323$. Мы можем видеть, что двойка повторяется, однако в ответе ее быть уже не может по условию задачи. Отбросим ее за ненадобностью и рассмотрим получившееся число $133$. Для полученного числа нам необходимо выполнить те же операции, что и для предыдущего, а значит, мы столкнулись с задачей на динамическое программирование (о чем нам, правда, уже заботливо сообщил e-olymp прямо под условием). Рассуждения аналогичны: взять $3$ мы не можем, поскольку это вынудит нас отбросить $1$, что в результате даст нам число $23$, то есть даже меньшее, чем то, что мы получали в начале. Следовательно, добавляем к ответу $1$. Последнюю оставшуюся цифру можно сразу добавлять к ответу, поскольку сравнивать ее не с чем. Получаем искомый ответ — $213$.
Как и оговаривалось вначале, работать будем со строчным представлением числа. До объявления цикла в строке 22 выполняются подготовительные процедуры: создается множество с целью определения цифр, составляющих число, а затем массив, в который помещаются элементы множества в порядке убывания. В теле цикла проходим по всем элементам массива, пока не находим такой, справа от которого будут все остальные элементы. Здесь важно отметить две вещи: во-первых, меня не интересуют сами цифры, имеет значение лишь их количество в соответствующих множествах; во-вторых, поскольку справа от элемента могут находится ему идентичные, включаем его в срез строки и проверяем, можно ли опустить левую часть числа без ущерба количеству цифр в нем. Если да, то этот элемент добавляется в ответ и извлекается из массива для следующего прохода, а если нет — программа переходит к следующему по старшинству элементу.
Ссылки
- Код на ideone
- Задача на e-olymp
- Засчитанное решение на e-olymp
— Пожалуйста, вычитайте работу. По крайней мере несогласования вроде «меня не интересует сами цифры» стоит исправить. И не принято в статьях писать от первого лица. Лучше использовать безличную форму или множественное число.
— Подберите метки. Они повторяют категорию или название.