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

[retran]

Задача про вирусную инфекцию:
1. Отложим пока три таблетки и пересчитаем сколько осталось в бутылках. В одной из бутылок будет на одну таблетку больше. Заберем эту лишную таблетку и положим к трем высыпавшимся. Таким образом в куче высыпавшихся таблеток будет по две таблетки из каждой бутылки.
2. Разломим каждую таблетку пополам. «Левые» половины сложим в одну кучу. «Правые» в другую.
Таким образом, в каждой куче будет по две половинки таблетки из каждой бутылки. Или по одной целой таблетке из каждой бутылки.
3. Сегодня съедим левую кучку, завтра съедим правую.

[j8kin]

Думаю, суть задачи в том, что открывать бутылки повторно нельзя и пересчитывать таблетки тоже (типа их там гугол штук и если вы прям ща не выпьете, то каюк). Поэтому скорее интересует ход мыслей, я тоже склоняют к разламыванию таблеток.

[retran]

«Нужно принимать по одной таблетке из каждой бутылки ежедневно в течении месяца, чтобы приобрести иммунитет к вирусу.»
«Таблетку выбросить нельзя, поскольку их количество ограничено.»

Их там не более 31.

[nickolaym]

Современные таблетки ещё и упаковывают в растворимые оболочки, чтобы они попали в нужный отдел пищеварительного тракта. (Например, чтобы не прореагировали с желудочным соком).

Поэтому даже не растолочь, а разрезать пополам — может быть фатально.

[andyudol]

Вопр. 1. Случай, когда перевод требует некоторого знания физики. Потому что «намагниченный материал» = «магнит». На самом деле имеются в виду магнит, магнитный материал (ферромагнетик) и немагнитный материал.
Кроме того, условие нечётко сформулировано: можно ли применять дополнительные средства, например, железные опилки или нагрев? Предположим, что нельзя.
Тогда проблема в различении магнита и магнитного материала. Воспользуемся тем, что сила притяжения магнитного материала к полюсу магнита больше, чем между полюсами (если бы кусок магнитного материала был точкой, = 0).

[reci]

Замечание принято, спасибо.

[IgnisDeus]

1.

int[] SortByFrequency(int[] arr) 
{
 return arr
    .Select(i => new Tuple<int, int>(i, arr.Count(v => v == i)))
    .OrderByDescending(t => t.Item2)
    .ThenBy(t => t.Item1)
    .Select(t => t.Item1)
    .ToArray();
}

[olen]

> If 2 numbers have same frequency then print the one which came first.
.ThenBy(t => t.Item1) — отсортирует по возрастанию

[IgnisDeus]

Ох, не заметил. Тогда так должно работать как надо

int[] SortByFrequency(int[] arr) 
{
 return arr
    .GroupBy(i=>i)
    .OrderByDescending(g=>g.Count())
    .SelectMany(l=>l.ToArray())
    .ToArray();
}

[nickolaym]

Вопрос 1
Для различения нужен магнит (хотя бы электрический)

• магнит во внешнем поле будет ориентироваться, возникнет и сила, и крутящий момент
• магнитный материал будет притягиваться (диамагнетик) или отталкиваться (парамагнетик)
• немагнитному материалу пофиг

Если "вопрос по железу" имеется в виду русский сленг (железо — hardware), то магнит можно добыть из любого моторчика.

[nickolaym]

Вопрос 2.

Умри, но сдохни!

Выбор между умереть медленно и мучительно от болезни и быстро и мучительно от отравления.
Захлопни пасть и жри две таблетки! А завтра возьми ещё одну таблетку из бутылки и сожри с оставшейся.

А вообще, возьми эти три таблетки и отложи на конец месяца. А сейчас прими новую порцию, уже заведомо правильную. Если в конце месяца останется запас таблеток в бутылках, то и чёрт с ними. Если же там впритык, то в предпоследний день будет одна таблетка в бутылке, и три таблетки в заначке. Захлопни пасть и жри! С вероятностью 2/3 тебе повезёт.

[nickolaym]

Задача 1

Гистограммы, не?

from collections import Counter
counts = Counter(arr)
result = sorted(arr, reverse=True, key=lambda a: counts[a])  # sorted устойчиво

[nickolaym]

Задача 2

(пишу спойлер! потому что задача немного некорректна — и некорректно переведена)

В этом дереве ключи уникальны и упорядочены при поперечном обходе.
Пишем процедуру поперечного обхода и проверяем.

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

Рассмотрим дерево, вырожденное в правый список: X -> Y -> Z.
При поперечном обходе мы, допустим, выяснили, что X<Y, Y<Z. А нам нужно, чтобы ещё и X<Z ("все ключи правого поддерева меньше ключа корня").
Но если отношение транзитивности не выполняется, то вполне может быть X<>Z какое угодно.

Таким образом, честная процедура — это сравнивать все дочерние узлы со всеми родительскими.
В худшем случае алгоритм квадратичный (забег по дереву, вырожденному в список).

[nickolaym]

Два дымящихся сосуда — это детская задачка из Перельмана, если вообще не из Магницкого.

Просто берём и повторяем одну процедуру
1) налить доверху сосуд А
2) слить из А в Б (доверху или сколько получилось)
3) если в А ещё что-то осталось, вылить всё из Б и повторить с шага 2;
4) если в А ничего не осталось, повторить с шага 1

Рано или поздно в одном из сосудов будет НОД(А, Б).

[nickolaym]

Этот алгоритм единственный и поэтому наиболее (и наименее тоже) эффективный.
Всё, что мы можем варьировать — это что принять за сосуд А, а что за сосуд Б.

Ну и какой критерий эффективности, количество вылитой впустую воды, количество перелитой воды (совершённая работа), количество операций?

Если жалко думать и не жалко моделировать — можно смоделировать обе ветки алгоритма и сравнить. Сложность моделирования — O(А*Б / НОД(А, Б)^2)

[nickolaym]

Рассмотрим плоскость с осями "заполнение сосуда А" и "заполнение сосуда Б".
Понятно, что область допустимых значений — это всего лишь прямоугольник (0,0)-(А, Б).
Но мы размножим его, замостив копиями всю плоскость. Получится такая сетка.

Операция "заполнить сосуд" — это сместиться по оси А (или Б) на один шаг сетки вперёд.
Операция "слить" — сместиться по другой оси назад.
Операция "перелить" — сместиться по диагонали до пересечения с ближайшей линией сетки (горизонтальной или вертикальной, как повезёт).
После такого пересечения последует операция "заполнить" или "слить", которая заставляет текущую точку перепрыгнуть на то же самое место на противоположной стороне прямоугольника, — а поскольку прямоугольники у нас по всей плоскости, то мы просто делаем себе зарубку "была операция" и остаёмся на том же месте.

Проведём диагональную линию из точки (0,0). И посмотрим, как скоро она приведёт нас в точку (t,t) = (kA+1,mB) или (kA,mB+1). При этом мы выполним k операций долива, m операций слива и k+m операций перелива.
(На этом пока мысль иссякла, — как точнее сформулировать и объяснить, как из этого определить, который путь быстрее — доливать в А или сливать в А).