Привет.
Хочу рассказать вам об одной задаче, которая занимает меня уже очень продолжительное время. Сразу хочу сказать, что я не знаю ее решения (чтобы не превращать топик в очередной топик зла). Также я не встречал задач, подобной этой, в интернете, хотя вполне допускаю, что первый же коммент будет со ссылкой на решение.
Итак, задача.
Предположим, у нас есть сейф с цифровым замком. Чтобы открыть сейф, необходимо набрать на цифровой клавиатуре код, состоящий из n цифр (цифры могут повторяться). Сейф откроется, как только код будет набран — предыдущие неправильные цифры не учитываются. То есть, если код равен «1234», сейф откроется, даже если набрать «51234», «781234» или «11234». Задача заключается в том, чтобы найти такую последовательность цифр, которая со 100% вероятностью откроет сейф и которая будет минимальна по длине.
Хочу рассказать вам об одной задаче, которая занимает меня уже очень продолжительное время. Сразу хочу сказать, что я не знаю ее решения (чтобы не превращать топик в очередной топик зла). Также я не встречал задач, подобной этой, в интернете, хотя вполне допускаю, что первый же коммент будет со ссылкой на решение.
Итак, задача.
Предположим, у нас есть сейф с цифровым замком. Чтобы открыть сейф, необходимо набрать на цифровой клавиатуре код, состоящий из n цифр (цифры могут повторяться). Сейф откроется, как только код будет набран — предыдущие неправильные цифры не учитываются. То есть, если код равен «1234», сейф откроется, даже если набрать «51234», «781234» или «11234». Задача заключается в том, чтобы найти такую последовательность цифр, которая со 100% вероятностью откроет сейф и которая будет минимальна по длине.
