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

[qw1]

Задача chickens

Скрытый текст

Обозначим X_N — кол-во перед продажей N-му покупателю.
Тогда X_N=X_N/2 + 0.5 + X_N+1.
Знаем, что X₅=0 (5-му покупателю ничего не осталось), получаем
X₄=1, X₃=3, X₂=7, X₁=15.
Ответ: 15

[qw1]

Да, действительно. Но тут ещё проще. В условии сказано, что последнему достался один, отсюда X₄=1

[qw1]

Про револьвер

Скрытый текст

Лучше стрелять второй раз. Так вероятность выжить 1/2, а если покрутить барабан ещё раз — 1/3

[AlexTest]

Если стрелять второй раз, то у вас уже не играет пустая камора барабана, выпавшая в первый раз. Т.е. у вас играют два патрона в пяти каморах. А если крутануть барабан, то у вас играет еще раз эта же пустая камора, т.е. у вас снова два патрона в шести каморах. Вероятность быть убитым без прокрутки 2/5, с прокруткой 2/6, т.е. с прокруткой вероятность быть убитым — меньше.

[AlexTest]

Даже еще хуже, после первого выстрела у вас уже не играют две каморы, т.к. мы знаем что патроны заряжены последовательно. Т.е. шанс быть убитым без прокрутки — 1/2, а с прокруткой — 1/3, т.е. надо крутить, чтобы шанс выжить был выше.

[Rsa97]

Если в первый раз выстрела не было, значит выпало одно из четырёх пустых гнёзд. Гнёзда эти идут подряд, причём после трёх из них снова пустое гнездо, после четвёртого — патрон. Следовательно, вероятность выстрела без прокрутки барабана — 1/4.

[AlexTest]

да, ваше рассуждение вернее моего — после первой осечки в этом случае крутить не надо!

[Rsa97]

Вопрос 1

Пусть N_i — остаток перед продажей i-му покупателю. Тогда:
Четвёртый: N₄/2 + 1/2 = 1 ⇒ N₄ = (1 — 1/2) * 2 = 1
Третий: N₃ — N₃/2 — 1/2 = 1 ⇒ N₃/2 = 3/2 ⇒ N₃ = 3
Второй: N₂ — N₂/2 — 1/2 = 3 ⇒ N₂/2 = 7/2 ⇒ N₂ = 7
Первый: N₁ — N₁/2 — 1/2 = 7 ⇒ N₁/2 = 15/2 ⇒ N₁ = 15
Ответ: 15 кур

Вопрос 2

Вероятность того, что в следующем гнезде барабана находится патрон — 1/4
Если прокрутить барабан, то вероятность того, что он остановится на патроне — 2/6 = 1/3
Вывод — крутить не надо.
Правда, если русский гангстер неправильно хранил патроны, то есть вероятность осечки. Тогда всё гораздо сложнее.

Задача 1

function sortStack(stack, min) {
  if (is_empty(stack)) {
    return min;
  }
  cur = top(stack);
  pop(stack);
  if (cur < min) {
    cur = sortStack(stack, cur);
  } else {
    min = sortStack(stack, min);
  }
  if (cur < min) {
    push(cur);
    return min;
  } else {
    push(min);
    return cur;
  }
} 

function sortStack(stack) {
  if (is_empty(stack)) {
    return;
  }
  cur = top(stack);
  pop(stack);
  push(stack, sortStack(stack, cur));
}

[Ellias]

Если всё таки прочитать задачу до конца, то нужно посчитать сколько всего было продано кур за день, а не сколько первый купил. Итого из вашего расчета ответ: 15+7+3+1 = 26.
Простенькая проверка, исходя из условий задачи: будем делить пополам и прибавлять 0,5 курицы.
1: 26/2 + 0,5 = 13,5 (12,5 в остатке)
2: 12/2 + 0,5 (та что в остатке оставалась) = 6,5 (6 в остатке)
3: 6/2 + 0,5 = 3,5 (2,5 в остатке)
4: 2/2 + 0,5 = 1,5 (1 в остатке) или 2/2 = 1 (1,5 в остатке)
То есть, всё сходится, хоть значения N и не совпадают (про то, что у продавца куриц не осталось ни одной курицы в условии ничего нет, значит всё ок).
В задаче есть противоречие, либо это просто исключение, что последний купил одну курицу, но при этом ВСЕ купили половину и ещё пол курицы.
Странно, но кажется ответом может быть и 19 куриц (если принимать, что половина от нечётного числа куриц это округление до чётного числа в меньшую сторону):
1 купил 9,5
2 купил 4,5
3 купил 2,5
4 купил 1,5 (или одну)

[Rsa97]

А вы внимательней прочитайте решение. N₁ — остаток перед продажей первому покупателю, то есть изначальное количество кур.

[Ellias]

Неверно понял, но тогда получается, что у задачи не менее 4 решений в диапазоне от 12,5 до 26. Интересен правильный ответ, или тут скорее более важен ход мыслей, чем результат.

[nasl]

В первой задаче не очень понятен вопрос в плане целочисленности действия «половина оставшихся кур и еще пол куры». Очевидное решение, двигаться верх по значению 2^n — 1, может быть не очень правильным. Согласитесь, попросив у продавца выдать половину оставшихся кур и пол куры из 15 штук, вряд ли он выдаст вам 8 штук:) Хотя чисто математически это верно.

Предлагаю другое решение:
У продавца было 12 целых кур и пол куры;
Первому он отдал 6 целых кур (половину от оставшихся 12 целых) и пол куры, осталось 6 целых кур;
Второму отдал 3 (половину от оставшихся 6 целых) и еще пол куры, осталось 2 целых куры и пол куры;
Третьему отдал 1 (половину от оставшихся 2 целых) и еще пол куры, осталось 1 целая кура;
Вот четвертому и осталась одна целая кура

[nasl]

Я согласен, что 15 — правильный ответ! Да, просто я пытался взглянуть на условия задачи под другим углом.

[nasl]

Абсолютно согласен, а в жизни покажите мне хоть одного продавца, который после фразы «половина оставшихся кур и еще пол куры», даст ровно восемь:)

[nasl]

Это уже будет совсем другая задача:) Но в такомслучае, после первой же итерации, кур станет нечетное количество, если и было четсное. И тут вопрос деления пополам будет еще более интересным. И вряд ли можно будет сказать, что 7 или 8 — это будет пополам.

[tashihu]

У вас к третьему покупателю остается 2.5 курицы. Следуя условиям задачи он должен был купить 2.5/2 + 0.5 = 1.75. А 4 останеться только 0.75 курицы.

[nasl]

Да нет же, я предложил условие задачи интерпретировать не как [N/2 + 0.5], а говоря языком, например, матлаба [fix(N)/2 + 0.5], т.е. половину берем от целого количества куриц.
P.s. Но как мы выяснили выше, при текущем решении значения fix(N) удачно оказались четными, a с нечетными появляется некая неоднозначность при такой условии.

[SkylineIT]

Внимательней просто читайте про цыплят и всё станет понятно.
Мне кажется это очевидны.
Просто включаем обратный перебор:

4 итерация:

• Всего осталось = 0 ц;
• Всего было= 0 + 1 = 1 ц;

3 итерация:

• Всего осталось = 1 ц;
• Всего было: (1+0,5) * 2 = 3 ц;

2 итерация:

• Всего осталось = 3 ц;
• Всего было: (3+0,5) * = 7 ц;

1 итерация:

• Всего осталось = 7 ц;
• Всего было: (7+0,5) * 2 = 15 ц;

Ответ 15.
Не знаю как вы мистически больше получаете)

Про револьвер:

Сидим до выстрела = вероятность 2/6 = 1/3 шанс быть убитым;
Выживаем.

Просим еще раз стрелять = 2/5 шанс ~ 40%
Крутим повторно = 1/3 шанс ~ 33.3%

[reci]

Вы шутите?

[nasl]

Там и правда получается 1/4, а не 2/5. Вы видимо в условии пропустили, что пули вставлены последовательно.

[SkylineIT]

А нет.
Всё правильно писали:
При продолжении, получается так, что в барабане остается еще 3 пустых гнезда, которые нас устраивает, а только один следующий патрон ведёт нас к фаталу.
Соотвественно:

• шанс выжить — 3/4;
• шанс погибнуть — 1/4;

При прокрутке мы возвращаемся к вероятности:

• шанс выжить — 2/3;
• шанс погибнуть — 1/3;

[jmdorian]

Задача 2

Не самое быстрое решение, наверное и на PHP, но все же работает.

$string = 'ilikesamsung';

$vocab = ['i', 'like', 'sam', 'sung', 'samsung', 'mobile', 'ice', 'cream', 'icecream', 'go', 'mango', 'and'];

strContain($string, $vocab);

function strContain($string, $vocab, $result = [], $start = 0) {  
  $needle = '';
  for ($i = $start; $i < strlen($string); $i++) {
    $needle .= $string[$i];
    
    foreach ($vocab as $word) {
      if ($needle == $word) {
        $result[$start] = $needle;
        if (implode('', $result) == $string) {
          print "Yes, words are: " .  implode(", ", $result) . "<br>";
        } else {
          strContain($string, $vocab, $result, $i+1);
        }
      }
    }    
  }
}

[nickolaym]

Задача 2, если по-тупому, или если нужно вывести все варианты "да"

по-тупому

def split(text, words):
    if not text:
        yield []
        return
    for word in words:
        if text.startswith(word):
            for segments in split(text[len(word):], words-{word}):
                yield [word]+segments

Очевидные улучшения:

• делать предварительную проверку, основанную на подсчёте символов (если каких-то символов в строке больше, чем в коллекции слов — сразу на выход)
• использовать trie
• если строк много, или строка длинная, или ещё какие-то проблемы производительности вылезли, — сгенерировать конечный автомат по словам и признакам их повторения.

[nickolaym]

Задача 3 — комбинаторика. Программирование здесь постольку-поскольку.

Обозначим нашу функцию количества башен T(n,m,ktop,kmax) где n — высота башни, m — номенклатура плиток, ktop — остаток плиток верхнего размера, kmax — количество плиток прочих размеров.

Краевые значения

T(0,m,kt,km) = 1 — есть ровно одна башня нулевой высоты

T(n>0,m,kt,0) = 0 — если количества плиток нулевые, то не о чем говорить.

T(1,m>0,kt>0,km) = m — есть ровно m башен единичной высоты.
(на самом деле, это выводимое значение)

T(n,0,kt,km) = 0 — кончился ассортимент плиток.

T(n,m,0,km) = T(n,m-1,km,km) — кончились плитки текущего номинала — переходим к плиткам меньших номиналов (а их у нас ещё много).

T(n,m,kt>0,km) = T(n,m-1,km,km) + T(n-1,m,kt-1,km) — положили плитку текущего номинала либо свели задачу к меньшим номиналам.

Ну и понятно, что если высота очень большая, то решение или одно, или нет.
T(n>(m-1)km+kt,kt,km) = 0
T(n=(m-1)km+kt,kt,km) = 1.

Напрашивается тупое решение — посчитать рекурсивно с мемоизацией, либо рекуррентно.