Комментарии 47
Тогда XN=XN/2 + 0.5 + XN+1.
Знаем, что X5=0 (5-му покупателю ничего не осталось), получаем
X4=1, X3=3, X2=7, X1=15.
Ответ: 15
Четвёртый: N4/2 + 1/2 = 1 ⇒ N4 = (1 — 1/2) * 2 = 1
Третий: N3 — N3/2 — 1/2 = 1 ⇒ N3/2 = 3/2 ⇒ N3 = 3
Второй: N2 — N2/2 — 1/2 = 3 ⇒ N2/2 = 7/2 ⇒ N2 = 7
Первый: N1 — N1/2 — 1/2 = 7 ⇒ N1/2 = 15/2 ⇒ N1 = 15
Ответ: 15 кур
Если прокрутить барабан, то вероятность того, что он остановится на патроне — 2/6 = 1/3
Вывод — крутить не надо.
Правда, если русский гангстер неправильно хранил патроны, то есть вероятность осечки. Тогда всё гораздо сложнее.
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));
}
Простенькая проверка, исходя из условий задачи: будем делить пополам и прибавлять 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 (или одну)
Предлагаю другое решение:
У продавца было 12 целых кур и пол куры;
Первому он отдал 6 целых кур (половину от оставшихся 12 целых) и пол куры, осталось 6 целых кур;
Второму отдал 3 (половину от оставшихся 6 целых) и еще пол куры, осталось 2 целых куры и пол куры;
Третьему отдал 1 (половину от оставшихся 2 целых) и еще пол куры, осталось 1 целая кура;
Вот четвертому и осталась одна целая кура
P.s. Но как мы выяснили выше, при текущем решении значения fix(N) удачно оказались четными, a с нечетными появляется некая неоднозначность при такой условии.
Мне кажется это очевидны.
Просто включаем обратный перебор:
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%
Всё правильно писали:
При продолжении, получается так, что в барабане остается еще 3 пустых гнезда, которые нас устраивает, а только один следующий патрон ведёт нас к фаталу.
Соотвественно:
- шанс выжить — 3/4;
- шанс погибнуть — 1/4;
При прокрутке мы возвращаемся к вероятности:
- шанс выжить — 2/3;
- шанс погибнуть — 1/3;
$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);
}
}
}
}
}
Задача 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
- если строк много, или строка длинная, или ещё какие-то проблемы производительности вылезли, — сгенерировать конечный автомат по словам и признакам их повторения.
Задача 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.
Напрашивается тупое решение — посчитать рекурсивно с мемоизацией, либо рекуррентно.
Выпуск#24: ITренировка — актуальные вопросы и задачи от ведущих компаний