Задача о цифрах (вычеркнуть так, чтобы получить max число)

[Whitaker]

Из числа $12345678910111213…9899100$ вычеркните $100$ цифр так, чтобы оставшееся число было наибольшим.
Эту задачу я решил так:
Всего цифр в этом числе $192=1\cdot9+2\cdot90+1\cdot3$ (однозначных чисел - $9$, двузначных - $90$, трехзначных -$1$) и после удаления $100$ цифр у нас будет $92$-значное число.
Наибольшее $92$-значное число имеет вид $\underbrace{99...99}_{92}$.
Сначала удалим первые $8$ цифр числа $12345678910111213…9899100$, оставим цифру $9$, удалим затем последующие $19$ цифр и снова оставим цифру $9$, и снова удалим последующие $19$ цифр и оставим цифру $9$, удалим последующие $19$ цифр и оставим цифру $9$ и еще раз удалим $19$ цифр и оставим $9$. После этих $8+19\cdot4$=84 удалений цифр получим число: $9999950515253...9899100$. Но нам еще осталось удалить $16$ цифр, чтоб полученное число стало наибольшим. Сделаем это таким образом: в нашем полученном числе $9999950515253...9899100$ удалим $13$ цифр подряд после после пяти подряд идущих девяток и получим число $999996575859...9899100$. И затем в этом числе зачеркнем еще три подряд идущие цифры после цифр $999996$ и наконец-то получу число $9999968596061...9899100$, которое по моему мнению является наибольшим.
Скажите пожалуйста правильно ли я решил задачу?

[ИСН]

Вместо "И затем в этом числе зачеркнем еще три подряд идущие цифры после цифр $999996$" я зачеркну эту 6 и ту 5, что за ней; тем самым число станет начинаться на 999997. Уже лучше. Потом я положу ноги на стол, закурю сигару (хотя вообще-то не курю), и не спеша подумаю, где бы выкинуть ещё одну цифру.

[Whitaker]

ИСН в сообщении #464819 писал(а):

Вместо "И затем в этом числе зачеркнем еще три подряд идущие цифры после цифр $999996$" я зачеркну эту 6 и ту 5, что за ней; тем самым число станет начинаться на 999997. Уже лучше. Потом я положу ноги на стол, закурю сигару (хотя вообще-то не курю), и не спеша подумаю, где бы выкинуть ещё одну цифру.

Получается число $99999758596061...99100$ и зачеркнём цифру 5, которая стоит за 7. Получаем число $9999978596061...99100$. Думаю, что это число и является наибольшим.

[Whitaker]

Та же самая задача, но уже нужно чтоб получилось наименьшее число.
То есть: Из числа $12345678910111213....9899100$ вычеркните 100 цифр так, чтобы оставшееся число было наименьшим.
У меня в ответе получилось число $10000012345555550123456666869...9899100$. Скажите пожалуйста правильно ли у меня?

[Whitaker]

Из числа $12345678910111213....9899100$ вычеркните 100 цифр так, чтобы оставшееся число было наименьшим.
Так как в данном числе ровно 192 цифры, то после удаления 100 цифр останется 92-значное число, а наименьшее 92-значное число это: $1\underbrace{00...00}_{91}$.
В нашем числе $12345678910111213....9899100$ оставим первую цифру (т.е. цифру 1), удалим последующие 9 цифр, оставим цифру 0, затем удалим 19 цифр и оставим цифру 0, совершим такой процесс еще 3 раза. В итоге мы удалили $85=9+19\cdot4$ и получим следующее число:
10000051525354555657585960616263646566676869...9899100, но нам еще осталось зачеркнуть 15 цифр, чтобы оставшееся число стало наименьшим.
В этом числе удалим первые 4 пятерки (они выделены вверху) и получаем число: 1000001234555657585960616263646566676869...9899100.
А уже в этом числе удалим цифру 6, которая выделена вверху и получим число:
100000123455557585960616263646566676869...9899100.
Удалим все цифры, которые выделены вверху и получим число $10000012345555550123456666869...9899100$, которое является наименьшим.

[ИСН]

Какой смысл был удалять цифры после нуля, если можно было удалить перед ним и поднять его повыше?

[Whitaker]

ИСН в сообщении #465581 писал(а):

Какой смысл был удалять цифры после нуля, если можно было удалить перед ним и поднять его повыше?

Я Вас не понял что Вы имеет в виду, ИСН ?
P.S. Мне же нужно найти наименьшее число поэтому я так и сделал.

[TOTAL]

А если удалить 100 самых левых цифр (оставляя нули)?

[Whitaker]

TOTAL в сообщении #465674 писал(а):

А если удалить 100 самых левых цифр (оставляя нули)?

Если удалить первые 100 цифр, но оставляя при этом нули, то получим число $1000008596061....9899100$, но ведь это число больше чем $10000012345555550123456666869....9899100$

[MrDindows]

Тут простая система:
Нам надо удалить $k$ цифр. Для этого мы выбираем из первых (слева) $k$ цифр наименьшую по значению ( либо же наибольшую, смотря какое нам число необходимо получить), если таких несколько выбираем самую левую и стираем все цифры что стоят перед ней. Теперь нам надо стереть меньшее число цифр, и мы повторяем эту процедуру снова, пока не сможем больше стирать цифры).
ТС так правильно и начинал, но почему-то сбился)

Вот только возник вопрос: почему мы не можем оставить на 1 месте ноль? Ведь $0000001234...$ по сути тоже является числом...

[TOTAL]

Whitaker в сообщении #465696 писал(а):

TOTAL в сообщении #465674 писал(а):

А если удалить 100 самых левых цифр (оставляя нули)?

Если удалить первые 100 цифр, но оставляя при этом нули, то получим число $1000008596061....9899100$, но ведь это число больше чем $10000012345555550123456666869....9899100$

$099 < 100$ согласны?

[Whitaker]

MrDindows в сообщении #465701 писал(а):

Тут простая система:
Нам надо удалить $k$ цифр. Для этого мы выбираем из первых (слева) $k$ цифр наименьшую по значению ( либо же наибольшую, смотря какое нам число необходимо получить), если таких несколько выбираем самую левую и стираем все цифры что стоят перед ней. Теперь нам надо стереть меньшее число цифр, и мы повторяем эту процедуру снова, пока не сможем больше стирать цифры).
ТС так правильно и начинал, но почему-то сбился)

Вот только возник вопрос: почему мы не можем оставить на 1 месте ноль? Ведь $0000001234...$ по сути тоже является числом...

Это конечно число. Но в задаче сказано, что записи начинающиеся с нуля недопустимы

-- Ср июл 06, 2011 15:10:06 --

TOTAL в сообщении #465722 писал(а):

Whitaker в сообщении #465696 писал(а):

TOTAL в сообщении #465674 писал(а):

А если удалить 100 самых левых цифр (оставляя нули)?

Если удалить первые 100 цифр, но оставляя при этом нули, то получим число $1000008596061....9899100$, но ведь это число больше чем $10000012345555550123456666869....9899100$

$099 < 100$ согласны?

В задаче сказано, что числа начинающиеся с нуля недопустимы...если я конечно правильно Вас понял.
А если сделать как Вы сказали, т.е. удалить первые 100 цифр, при этом оставить нули, то получится число $1000008596061....9899100$, которое больше чем $10000012345555550123456666869....9899100$. Но ведь нам нужной найти наименьшее.

-- Ср июл 06, 2011 15:14:39 --

Кто-нибудь может сказать правильный ли у меня ответь?
А ответ у меня такой: $10000012345555550123456666869.....9899100$.
P.S. Повторяю еще раз. Числа начинающиеся с нуля недопустимы.

[venco]

Whitaker в сообщении #465756 писал(а):

Кто-нибудь может сказать правильный ли у меня ответь?
А ответ у меня такой: $10000012345555550123456666869.....9899100$.

У меня получилось меньше.

[Whitaker]

venco в сообщении #465764 писал(а):

Whitaker в сообщении #465756 писал(а):

Кто-нибудь может сказать правильный ли у меня ответь?
А ответ у меня такой: $10000012345555550123456666869.....9899100$.

У меня получилось меньше.

Очень интересно. Сейчас нука я сам попытаюсь сделать меньше.

[Whitaker]

venco в сообщении #465764 писал(а):

Whitaker в сообщении #465756 писал(а):

Кто-нибудь может сказать правильный ли у меня ответь?
А ответ у меня такой: $10000012345555550123456666869.....9899100$.

У меня получилось меньше.

Может быть Вы напишите, а то у меня никак меньше не получается.