|
Непрограммист,
В программировании нельзя отличить числа 0036 и 36. Стало быть, мы имеем дело со строками, судя по примерам (к слову, второй пример решён неверно).
Далее. У нас есть строковые записи А и Б, равной длины и состоящие из символов 0-9. Описание "диапазона" несложно получить следующим образом (до этого вполне можно было бы додуматься, расписав руками ещё пару-тройку примеров):
Пусть А и Б начинают (считая слева) различаться в некоторой цифре. Очевидно, что все цифры левее тупо повторятся во всех записях, так что будем считать, не ограничивая общности, что они различаются в первой слева цифре либо равны; второй случай тривиален.
Если первая цифра А - а1, а Б - б1, то промежуток содержит все числа, начинающиеся с цифр между а1 и б1 (будем рассматривать А=0350, Б=3300. Тогда промежуток включает 1ХХХ и 2ХХХ).
Выписали ли мы весь промежуток? Разумеется, нет - он пока не включает ни А, ни Б. Начнём расширять его в сторону А: остаток промежутка начинается с а1; если вторая цифра А - а2, то в него попадает всё, у чего вторая цифра больше а2 (в нашем примере, в промежуток добавились 04ХХ, 05ХХ, 06ХХ, 07ХХ, 08ХХ и 09ХХ). Неохваченный остаток промежутка со стороны А теперь начинается с а1,а2 и мы можем перейти к следующей цифре (036Х, 037Х, 038Х, 039Х). И так далее, пока не кончится число (в нашем случае, остался один шаг - 0351, 0352, 0353, 0354, 0355, 0356, 0357, 0358, 0359). Наконец, дополним его самим А (0350) и половина списка готова.
Аналогично можно поступить со стороны Б, только на сей раз нас будут интересовать цифры меньше бi (30ХХ, 31ХХ, 32ХХ, 3300). Как видим, в случае цифр 9 в А или 0 в Б соответствующий шаг надо пропускать.
Легко видеть, что последние десять элементов, дописанные со стороны А, можно было бы объединить в один. Как это можно сделать? Например, с помощью предварительной подготовки строк. После того, как мы определили первую различающуюся цифру, можно идя от правого края, заменять в А 0, а в Б 9 на Х (в нашем примере, такая подготовка даст А=035Х, Б=3300). Можно вместо этого поставить в А запись числа на 1 меньше, а в Б - на 1 больше и не включать края (проведите самостоятельно описанный вначале алгоритм для строк 0349, 3301).
Всегда ли мы будем получать таким образом минимальное количество строк? Увы, нет: для А=01, Б=98 такой метод даст 26 строк, в то время как можно обойтись шестнадцатью (подумайте, как).
Шагнём с противоположного конца: вот у нас есть строка, в которой на некоторой позиции стоит Х. Что это значит? Что при любой цифре на месте Х мы не выйдем за пределы диапазона от А до Б. Возьмём две любые цифры - 0 и 9. До тех пор, пока, идя слева направо, мы не натолкнулись на "вилку" аi=0, бi=9, мы можем пользоваться вышеописанным алгоритмом: никакое "конкурирующее" покрытие не сможет охватить одной строкой пару чисел, относящихся к разным нашим строкам. А вот 0-9, это и впрямь "вилка": можно попытаться подставить здесь Х, а можно поступить вышеописанным образом. В принципе, при недлинных строках можно рассчитывать оба варианта и смотреть, какой получился лучше.
Дальше пока не придумал
|
