Задача №411. Число
Разбор добавил Роман Атангулов
Понятно, что нужно отсортировать строки в некотором смысле в порядке невозрастания и вывести подряд. Нужно понять, как определять отношения "больше" и "меньше" в данном случае. Если определять их в стандартном смысле, т.е. лексикографическим порядком, то ответ будет неверным ( "20" > "2", но "202" < "220" ).
Будем считать, что строка \(s_1\) меньше строки \(s_2\) (или "раньше"), если \(s_1+s_2 \geq s_2+s_1\) (здесь "+" обозначает конкатенацию). В таком случае сортировать будем в порядке неубывания и выведем в качестве ответа все строки из массива подряд.
Оценим сложность алгоритма.
Пусть \(N\) -- общее количество слов, \(M\) -- наибольшее число цифр в строках.
По условию \(N,M \leq 100\). Cложность сортировки с проверкой \(O(M)\) действий -- \(O(M\cdot{N^2})\) при использовании квадратичных сортировок
и \(O(M \cdot N\cdot{\log N})\) при использовании логарифмических, что удовлетворяет ограничению по времени.
Докажем корректность алгоритма.
В общем случае понятно, что если непустые строки \(s_1\) и \(s_2\) одинаковой длины, то неравенство \(s_1 \le s_2\) эквивалентно неравенству \(n_1 \le n_2\),
где \(n_1\) и \(n_2\) -- это числа, записываемые в виде строк \(s_1\) и \(s_2\) соответственно.
Если в отсортированном массиве строк \(s[0]\) - первая, то \(s[0]\) раньше любой другой, т.е. \(s[0]+s[i] \geq s[i]+s[0]\ \ \ (*)\). Докажем, что искомое число может начинаться с \(s[0]\) (если есть несколько различных порядков строк, дающих максимальное число, то среди них есть и тот порядок, который начинается \(s[0]\)).
Пусть это не так, т.е. нет порядка, при котором число максимально и \(s[0]\) находится в начале. \((**)\)
Пусть число максимально. Тогда \(s[0]\) где-то в середине и перед \(s[0]\) стоит какая-то \(s[i]\).
В силу неравенства \((*)\) верно, что \(\cdots s[i]s[0]\cdots\leq\cdots s[0]s[i]\cdots\), а значит, наше число не уменьшится, если поменять \(s[i]\) и \(s[0]\).
Так можно менять, пока \(s[0]\) не окажется в начале. Число не уменьшилось, а так как оно было максимальным, то не изменилось. Противоречие с предположением \((**)\).
Таким же образом докажем, что среди оставшихся строк, если \(s[1]\) раньше всех, то искомое число должно начинаться с \(s[0]+s[1]\) (в силу импликации \((s_1 \leq s_2) \Rightarrow (s_0+s_1 \leq s_0+s_2)\), если длины \(s_1\) и \(s_2\) равны). Далее очевидно.