Из цифр двух натуральных чисел создать наименьшее возможное число, сохраняя порядок следования цифр

#cpp #алгоритм #олимпиада

Требуется написать программу, которая из цифр двух натуральных чисел создает наименьшее
возможное число, сохраняя при этом порядок следования цифр в этих числах.

Входной поток содержит два натуральных числа, записанных в двух строках. Числа больше
нуля и меньше 10^255.
(например, 125 и 34)

В единственную строку выходного потока нужно вывести наименьшее возможное число,
удовлетворяющее условию задачи. (например, 12345)

#include 
#include 
using namespace std;
int main()
{
  string a, b;
  cin >> a >> b;
  int x=0,y=0;
  while ((x

Ответы
Ответ 1

Проще всего, мне кажется, написать такую рекурсивную функцию:

bool compare(string a, int ia, string b, int ib)
{
    if (ia == a.length()) return true;
    if (ib == b.length()) return false;
    if (a[ia] == b[ib]) return compare(a, ia+1, b, ib+1);
    return a[ia] > b[ib];
}


И использовать ее так:

int main()
{
    string a = "12";
    string b = "21";
    int ia = 0;
    int ib = 0;
    while (ia < a.length() || ib < b.length())
    {
        if (compare(a, ia, b, ib))
            cout << b[ib++];
        else
            cout << a[ia++];
    }
    return 0;
}


https://ideone.com/PPtYY0

Максимальная глубина рекурсии при этом может быть 255, думаю, памяти хватит на всё
(есть ограничения на память?).


Ответ 2

Давайте разбираться.

a = 12, b = 21 


должно получиться 1212 - a[0]b[0]b[1]a[1], а у Вас получается 1221 - a[0]a[1]b[0]b[1].

В чем тут дело? Дело в принятии решения, по какому числу двигаться, когда цифры одинаковые.
Значит, волевое решение переходить к следующей цифре первого числа - как у Вас в коде
- нас не устраивает.

Чтобы принять правильное решение, надо заглянуть за эти одинаковые цифры и двигаться
по тому числу, у которого за этой одинаковой цифрой следует цифра меньшая, чем у другого
числа.

Но это еще не все...

Продолжаем. Интересный момент здесь состоит в том, что таких одинаковых цифр в числах
может идти больше одного подряд. Таким образом, нам нужно "заглядывать" за такие цепочки
одинаковых цифр в обоих числах.

И наконец, последний нюанс. Число может заканчиваться этой цепочкой одинаковых цифр.
Если оба числа ими заканчиваются, то все одинаковые цифры просто окажутся в конце результата.
Если только одно число заканчивается такой цепочкой, то надо смотреть на цифру, идущую
после цепочки в другом числе. Если эта цифра меньше одинаковых цифр, то надо выводить
цифры этого числа и не продвигаться в другом. И наоборот. 

Вам осталось перевести этот рассказ в код.



P.S. Не понимаю, что Вас смущает в размере чисел. Входные "числа" - это строки включающие
в себя до 255 десятичных цифр.