Строка называется правильной тогда и только тогда, когда она состоит из символов "0" и "1", а также в ней отсутствуют избыточные лидирующие нули. Вот несколько примеров: «0», «10», «1001».
Задана правильная строка s.
Над этой строкой можно проводить два типа операций:
- поменять местами два соседних символа (например, «101»
«110»); - заменить «11» на «1» (например, «110» «10»).
Определим val(s), как такое число, что s является его двоичным представлением.
Правильная строка a меньше другой правильной строки b тогда и только тогда, когда val(a) < val(b).
Ваша задача — найти минимальную правильную строку, которую можно получить из заданной, применив некоторую последовательность выше описанных операций. Операции можно использовать в любом порядке любое количество раз (или не использовать совсем).
Примечание
В первом примере можно получить ответ следующей последовательностью операций:
«1001» «1010» «1100» «100».
Во втором примере невозможно получить меньший ответ никакой последовательностью операций.