Выпуск#21: ITренировка — актуальные вопросы и задачи от ведущих компаний

function countVariants(codeString)
{
  //Нули могут быть только вторым знаком кода, 
  // поэтому разобьем кодовую строку на части с разделителем 0,
  // посчитаем количество вариантов в каждой из них и перемножим
  var parts = codeString.split('0');
 
  var variants = 1;
  for(var i = 0; i < parts.length; i++){
    var part = parts[i];
    
    //Уберем последнюю цифру перед нулем 
    if(i + 1 < parts.length){
      //Если перед нулем ничего нет, или перед нулем цифра больше 2
      // возвращаем нуль вариантов, то есть ошибку
      if(!part.length){
        return 0;
      } else if (+part.substr(-1) > 2) {
        return 0;
      }
      
      part = part.substr(0, part.length - 1);
    }
    
    var partVariants = 1;  
    
    //Считаем количество вариантов в части
    if(part.length){
      partVariants = 0; 
      
      //Смотрим кол-во возможных вариантов в начале строки, 
      //если первые две цифры составляют число меньшее 27, то варианта два
      var startOptions = 1;
      if(part.length > 1 && +part.substr(0, 2) < 27) startOptions = 2;
      
      //Для каждого из вариантов рекурсивно вызываем функцию
      for(var j = 1; j <= startOptions; j++){
        partVariants += countVariants(part.substr(j));
      }
    }

    variants = variants * partVariants;  
  }
  
  return variants
}

document.write(countVariants('1231012'));

function freePlaceProbability()
{
    var percent = 1;
    for(var i = 99; i > 1; i --){
      percent += percent/i;
    }

    return percent;
}

document.write('Probability: ' + freePlaceProbability() + '%');

• вероятность что моё место останется свободным после того как сел Гарри 99/100
• вероятность что моё место останется свободным после второго (1 — 1/100 (на моё сел Гарри, остальное не важно) — 1/100 (гарри сел на место второго)* 1/99(второй сел на моё
• и так далее, пока последний передо мной не будет выбирать между двумя местами, то есть 1 — 1/100 — 1/(100*99) -… — 1(100*99*...*2)

function multiplyStrings(s1, s2){
  
  var numbers = [];
  var multipleLength = s1.length + s2.length;
  
  for(var i = 0; i < multipleLength; i++) numbers[i] = 0;
  
  //Умножаем в столбик, но не по цифре, а сразу большими разрядами,
  //насколько позволяет система, в js корректно работает при следующих
  //step-ах, то есть при максимальном произведении двух чисел - 15 знаков после запятой
  var steps = [10, 5];
  
  var digits = [[], []];
  var stringCopies = [s1, s2]; 
  
  //Заполняем массивы для умножения по заданным разрядам
  for(var ind in digits){
    var copy = stringCopies[ind];
    var step = steps[ind];
    
     while(copy){
      if(copy.length <= step){
        var part = copy;
        copy = null;
      } else {
        var part = copy.substr(-step);
        copy = copy.substr(0, copy.length - step);
      }
      digits[ind].push(+part);
    }  
  }
  
  //Умножаем в столбик
  for(var i = 0; i < digits[1].length; i++){
    for(var j = 0; j < digits[0].length; j++){
      
      //Задаем сдвиг в зависимости от текущих разрядов
      var shift = i * steps[1] + j * steps[0];
      
      multipleLine = ('' + (digits[0][j] * digits[1][i])).split('').reverse();
      
      //Произведение добавляем в массив numbers
      for(var k = 0; k < multipleLine.length; k++ ){
        var ind = k + shift;
        numbers[ind] += +multipleLine[k];
      }
    }
  }
  
  //Подсчитываем каждую позицию в numbers, перенося десятки в следующий разряд
  for(var i = 0; i < numbers.length - 1; i++){
    var nextPos = Math.floor(numbers[i] / 10);
    numbers[i] = numbers[i] % 10;
    numbers[i + 1] += nextPos;
  }
  
  //Удаляем возможные лишние нули в начале
  while(numbers[numbers.length - 1] === 0) numbers.pop();
  
  return numbers.reverse().join('');
    
}

document.write('<br>' + multiplyStrings('654154154151454545415415454', '63516561563156316545145146514654'));

del

Free place:
197/9900
Вероятность что Гарри сел сразу на свое место: 0.01
Вероятность что никто не сядет на мое место и гарри не сел на свое место: 98/100 98/99 97/98… * 1/2
В сумме: 98/9900 + 0.01 = 197/9900

Умножение строк? Легко!

def multiplyStrings(s1, s2):
    return str(int(s1)*int(s2))

потому что целые числа в питоне — неограниченной разрядности.

А если бы не было питона, пришлось бы реализовывать какой-нибудь алгоритм типа умножения Карацубы или Штрассена (если не жалко времени на программирование) или в столбик (если не жалко процессорного времени).

ФБР — если бы нам надо было расшифровывать по-честному, мы бы сделали декодер Витерби.
А раз только посчитать количество, то вырождаем Витерби до тупейшего автомата.

def fbi(digits):
    valid_numbers = {str(n) for n in range(1, 27)}

    num_prev = 0  # сколько вариантов закончилось на предыдущем шаге
                  # (нисколько, т.к. нет такого шага)
    num_here = 1  # сколько вариантов закончилось прямо здесь
                  # (единственный вариант из пустой строки)
    here = '$'    # последняя цифра
                  # (её нет, поэтому сделаем заглушку)

    for then in digits:
        num_then = (  # сколько вариантов закончатся на следующем шаге
            num_prev * ((here+then) in valid_numbers)  # предыдущие + 2-разрядное
            +
            num_here * (then in valid_numbers)         # текущие + 1-разрядное
        )
        # сдвигаем состояние
        num_prev, num_here, here = num_here, num_then, then

        if not num_prev and not num_here:
            break  # если никаких вариантов не осталось, не будем молотить дальше

    # итого, сколько вариантов закончилось здесь, когда проглочены все цифры?
    return num_here