|
Сумма двух чисел
(Время: 1 сек. Память: 16 Мб Сложность: 46%)
Для решения этой задачи следует организовать перебор всех возможных комбинаций перестановки цифр первого числа A и выбрать среди них то минимальное, при котором возможно тождество X+Y=C, где X - некоторая перестановка цифр числа A и Y - некоторая перестановка цифр числа B. При этом проще занести цифры числа A в массив, отсортировать его (тогда не нужно будет находить минимальное, это ускорит процесс) и организовать стандартный алгоритм поиска всех перестановок в массиве в порядке возрастания. При рассмотрении каждой перестановки мы будем преобразовывать текущий массив обратно в число X и смотреть: совпадает ли набор цифр числа Y=C-X с набором цифр числа B. Если это так, то процесс поиска прекращается и в качестве ответа выводятся найденные X и Y. Если же такой пары не найдется по завершению рассмотрения всех перестановок, то следует вывести NO.
Проверка двух чисел на совпадение набора цифр не представляет большой сложности. Но и здесь есть где ошибиться, т.к. самое простое и понятное решение - это сортировка цифр в числах и последующее их сравнение, но при этом возникают временные затраты, что может привести к Time Limit Exceeded, поэтому лучше использовать стандартный алгоритм: использовать некоторый массив D, сначала обнулив его, а затем расцепляя первое число на цифры, увеличивать каждый элемент D[Y[i]] на единицу (Y[i] - i-я цифра числа Y), после чего выполнять обратный процесс для второго числа, аналогичным образом уменьшая на единицу значение D[B[i]]. Если в результате массив D окажется нулевым, то наборы совпадают, а иначе - нет.
Заметим так же, что максимальное число перестановок, которое может быть равно 9!=362880, что вполне приемлемо. Даже при использовании неэффективного квадратичного алгоритма сравнения чисел на набор цифр, о котором говорилось выше, возможно прохождение всех тестов. Но идея решения данной задачи с организацией всех возможных перестановок не только первого числа, но и второго сильно увеличивает перебор до 9!*9!, что просто невыполнимо.
| |
