Задача на комбинаторику

[vrtnev]

Резервное копирование документов выполняется путем создания архива с паролем. Известно, что пароль имеет длину ровно 4 символа и состоит из строчных букв английского алфавита (ASCII). От каждой неудачной попытки ввода пароля до следующей возможности ввести пароль проходит X миллисекунд, где X – сумма кодов таблицы ASCII, соответствующих символам введенного пароля, в миллисекундах (например, если введен неправильный пароль info, то X = «код символа i» + «код символа n» + «код символа f» + «код символа o»).

После сбоя в системе документы были утеряны. За какое минимальное время (в мс) гарантированно удастся восстановить утерянные документы из резервного архива, если пароль неизвестен?

Варианты ответа:
200155488
1994512
245600374
1050434

Я рассчитал так:
максимальный код символа(z) = 122
122*3 = 366 (т.к 3 символа неизвестны)
код символа s = 115
366+115=481 - время обработки одного пароля.
А всего паролей: ([количество вариантов]^3)*4 = (35^3) * 4 = 171500
171500*481 = 82491500.
Ответ: 82491500.
Но такого варианта ответа нет. Подскажите, в чём ошибка?

[Serge_Bliznykov]

А всего паролей: ([количество вариантов]^3)*4 = (35^3) * 4 = 171500

это неверно.

во-первых, строчных букв английского алфавита всего 26

во-вторых,

Число всевозможных размещений с повторениями из n элементов по k равно
n в степени k

поэтому 26^4 = 456976

а вот с вычислением времени всё немного хуже.
у вас аналитика написана неверно. при чём здесь, например, буква "s" ?
допустим, проверяем пароль zzzz
если он неверный, пауза будет 122+122+122+122 = 122 * 4 = 488 мс
т.е. время подбора ГАРАНТИРОВАНО МЕНЬШЕ, чем
456976 * 488 мс => время меньше, чем 223004288 мс

но чтобы подсчитать время точнее, нужно или написать простенькую программу, которая переберёт все варианты и сложит коды букв,
либо выводить формулу аналитически.

я бы, честно говоря, сделал по первому варианту.

[Serge_Bliznykov]

Всего вариантов паролей: 456976 задержка в ms = 200155488

var ms : int64;
  a,b,c,d : byte;
  cnt:integer;
begin
  ms:=0;
  cnt:=0;
  for a := $61 to $7a do
    for b := $61 to $7a do
     for c := $61 to $7a do
       for d := $61 to $7a do begin
         ms := ms + a + b + c + d;
         inc(cnt)
       end;
  WriteLn('Всего вариантов паролей: ',cnt,' задержка в ms = ',ms);
  ReadLn
end.

FYI. если Вы посмотрите на время разницы постов, то увидите, что время на запуск компилятора, написание программы, её запуск и получение результата составило примерно 7 минут.
это намного дольше, чем я писал первый пост!

[evg_m]

(т.к 3 символа неизвестны)

откуда информация про три..

366+115=481 - время обработки одного пароля.

время ожидания величина ПЕРЕМЕННАЯ

до следующей возможности ввести пароль проходит X миллисекунд, где X – сумма кодов таблицы ASCII

сначала будем считать что задержки будут от 0 до 25

00 00 00 00 --время ожидания до следующего есть их СУММА =0
00 00 00 01
...
25 25 25 25 =100
всего строк в записи 26**4. А каково же Общее время??

посчитаем по КАЖДОЙ колонке (0+1+..+25) * (26**3)
и всего 4 * (26**3) * (0+25)*26/2

вместо 0..25 ставим нужные числа,
рассчитываем,
учитываем ЧТО первый пароль НЕ требует ожидания,
учитываем что последний пароль НЕ имеет следующего и время ожидания за ним нас не интересует.
для снижения затрат выбираем "правильный" пароль для первого опробования.

[Serge_Bliznykov]

evg_m, хочу обратить ваше внимание на то, что постом выше есть решение.
правильный ответ: 200155488

[evg_m]

evg_m, хочу обратить ваше внимание на то, что постом выше есть решение.

когда начинал ответов еще не было.
тем паче это что это "набросок"

либо выводить формулу аналитически.

[Аватар]

4*26^3*(97+122)*26/2 = 200155488

учитываем что последний пароль НЕ имеет следующего

без учета

[Serge_Bliznykov]

(97+122)/2 - среднее время задержки
умножить на количество символов в пароле 4 и умножить на количество паролей 456976 ?
получаем
109.5 мс * 4 * 456976 = 200155488 мс

Аватар, браво!

[Аватар]

Вообще-то без среднего. но оно вытекает. 4 позиции на число комбинаций на других позициях и на вес (сумма арифметической прогрессии 97,98,...,122). Отсюда и среднее 2*(97+122): 4*26^3*(97+122)*26/2=4*26^4*(97+122)/2 -> среднее=2*(97+122). Но это еще догадаться нужно было, что оно такое. Изначально мне в голову не пришло

[kik777]

Сообщение от Аватар

Вообще-то без среднего. но оно вытекает. 4 позиции на число комбинаций на других позициях и на вес (сумма арифметической прогрессии 97,98,...,122). Отсюда и среднее 2*(97+122): 4*26^3*(97+122)*26/2=4*26^4*(97+122)/2 -> среднее=2*(97+122). Но это еще догадаться нужно было, что оно такое. Изначально мне в голову не пришло

Откуда 97 взялось? По подробнее, пожалуйста