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

[Rsa97]

Первая задача

Дверь будет менять состояние, если её номер (D) нацело делится на номер прохода. Все такие номера проходов можно получить, если разложить номер двери на простые множители (p₁...p_k) и взять все различные их комбинации
D = p₁^n₁ × p₂^n₂ ×… × p_k^n_k
Количество различных комбинаций этих множителей даст количество проходов, на которых дверь сменит состояние. Его можно получить как
N = (n₁ + 1) × (n₂ + 1) ×… × (n_k + 1)
Для того, чтобы дверь в конце осталась открытой она должна сменить своё состояние нечётное количество раз. Такое возможно только если все множители (n_i + 1) будут нечётными, то есть все n_i будут чётными.
Но, раз все n_i — чётные, то мы можем записать изначальное разложение как
D = (p₁^n₁/2)² × (p₂^n₂/2)² ×… × (p_k^n_k/2)² = (p₁^n₁/2 × p₂^n₂/2 ×… × p_k^n_k/2)²
Таким образом, открытыми останутся только двери, чьи номера представляют собой квадраты целых чисел, то есть 1, 4, 9, 16, 25, 36, 49, 64, 81, 100.

[zhussupov]

На самом деле дверь номер 8 тоже в итоге будет открыта, но она не является квадратом целого числа

[Rsa97]

Давайте посчитаем: проход 1 — открыта, 2 — закрыта, 4 — открыта, 8 — закрыта. Какие ещё проходы меняют состояние этой двери?

[IgnisDeus]

Power of 2

public bool IsPowerOfTwo(int Number) { return ((Number & 1) == 0) ? IsPowerOfTwo(Number >> 1) : Number == 1; }

Find an element in a sorted and rotated array

        static int SearchInLeftPart(int[] Arr, int Number)
        {
            int BreakPointMin = Arr[Arr.Length - 1];
            int BreakPointMax = Arr[0];
            int Left = 0;
            int Right = Arr.Length - 1;
            int Med;
            while (Left < Right)
            {
                Med = (Left + Right) / 2;
                if (Arr[Med] == Number) return Med;
                if (Arr[Med] <= BreakPointMin)
                {
                    Right = Med - 1;
                    continue;
                }
                if (Arr[Med] > Number)
                {
                    Right = Med - 1;
                }
                else
                {
                    Left = Med + 1;
                }
            }
            if (Arr[Left] == Number) return Left;
            return -1;
        }
        static int SearchInRightPart(int[] Arr, int Number)
        {
            int BreakPointMin = Arr[Arr.Length - 1];
            int BreakPointMax = Arr[0];
            int Left = 0;
            int Right = Arr.Length - 1;
            int Med;
            while (Left < Right)
            {
                Med = (Left + Right) / 2;
                if (Arr[Med] == Number) return Med;
                if (Arr[Med] >= BreakPointMax)
                {
                    Left = Med + 1;
                    continue;
                }
                if (Arr[Med] > Number)
                {
                    Right = Med - 1;
                }
                else
                {
                    Left = Med + 1;
                }
            }
            if (Arr[Left] == Number) return Left;
            return -1;
        }

        static public int SearchInArr(int[] Arr, int Number)
        {
            int BreakPointMin = Arr[Arr.Length - 1];
            int BreakPointMax = Arr[0];
            if (BreakPointMin > BreakPointMax) return Array.BinarySearch(Arr, Number);

            if (Number > BreakPointMin && Number < BreakPointMax) return -1;

            if (Number <= BreakPointMin) return SearchInRightPart(Arr, Number);
            else return SearchInLeftPart(Arr, Number);
        }

[IgnisDeus]

Find a Number X whose sum with its digits is equal to N

Тут идет простой перебор, но перебор начинается с числа N-((порядок числа N)*9) и идет до N-1

        static int[] GetNumbers(int N)
        {
            List<int> res = new List<int>();
            int Order = 1;
            int tmp = N;
            while (tmp/10 != 0)
            {
                Order++;
                tmp /= 10;
            }
            int start = N - Order * 9;
            if (start < 0) start = 0;
            for (int i = start; i < N; i++)
            {
                if (i+ GetSumOfDigits(i) == N)
                {
                    res.Add(i);
                }
            }
            return res.ToArray();
        }
        static int GetSumOfDigits(int N)
        {
            int res = 0;
            while (N / 10 != 0)
            {
                res += N%10;
                N /= 10;
            }
            res += N;
            return res;
        }

[SeptiM]

Я думаю, что про power of 2 скорее было

это.

x > 0 && ((x — 1) & x) == 0

[ultrinfaern]

По первому вопросу: посещение двери равно её порядковому номеру.
По второму вопросу: так как там лампы, можно попытаться определить по нагреву — горячая, теплая, бе нагрева — только причем тут программирование…
По первой задаче: в одну строку можно посчитать количество бит в числе — если равно 1 то степень двойки.
По второй задаче: глядя на первый и последний элементы возможно можно узнать точку поворота.

[Andy_U]

По второй задаче: глядя на первый и последний элементы возможно можно узнать точку поворота.

Однако, тоже за логарифмическое время (см. задачу за прошлую неделю). А потом второй проход по одному из двух подмассивов. Если сохранить значения из первого прохода, можно, наверное, немного сэкономить на втором.

[qw1]

По второму вопросу: так как там лампы, можно попытаться определить по нагреву — горячая, теплая, бе нагрева — только причем тут программирование…

В этом случае, условие задачи не полное, т.к. не исключает вариант, что лампы висят на высоте 5 метров и нет никаких подручных средств, чтобы их достать.

[Rsa97]

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

[LizardVojd]

По первому вопросу: посещение двери равно её порядковому номеру.

Сколько раз посещали двери под номерами 3,5,7,11,13....?

[Rsa97]

Power of 2

bool function isPowerOf2(int number) { return !(number & (number - 1)); }

[xi-tauw]

Чутка не хватает.
Проверяем

[Rsa97]

Согласен, ноль не учёл. Хотя,… 0 = 2^−∞

[Habra-Mikhail]

Отнюдь! У вас тут должен быть предел, т.к ∞ — не число.

[ads83]

IMHO, на задачу о лампочке лучше всего ответил (бы) Фейнман blogs.msdn.microsoft.com/ruericlippert/2011/02/28/983

TL;DR

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

[xi-tauw]

Что-то сегодня простые задачи.

Power of 2

v && !(v & (v — 1))

Find an element in a sorted and rotated array

Сначала бинарным поиском найдем излом, затем бинарный поиск в нужной части.

Find a Number X whose sum with its digits is equal to N

Разница X и N не более 81, значит проще всего от N проверять вниз ближайшие 81 число.

[kardan2]

Заголовок спойлера

1 вопрос. Открытыми будут только двери, чьи номера образуют квадрат, т.е. 1,4,9,16,25,...100
2 вопрос. Баян, и вообще вопрос многими считается не корректным.
1. Задача. Отнимаем от числа 1, и побитово умножаем с исходным числом.
2. Задача. Опять повороты массивов. Смысл давать похожие задачи между 2-мя выпусками?
Над последней задачей ещё думаю.

[IIvana]

Ради интереса - чуть менее тривиальное решение последней задачи

f 0 a 0 = [a]
f 0 _ _ = []
f d a n | c >  9    = []
        | c == 0    = [c] >>= f'
        | otherwise = [c, c-1] >>= f' where
    d1 = d + 1
    c  = div n d1
    d' = div d 10
    f' v = f d' (v:a) (n-v*d1)

toi = foldr (\x a -> a*10 + x) 0

g n = map toi . f (10^(length $ show n)) [] $ n

main = do
    mapM (\x -> putStrLn $ show x ++ "   " ++ show (g x)) [10000000000000..10000000000010]

[reci]

Что это за язык?

[IIvana]

Должно быть, Эльфийский

[IIvana]

Хотя не, вот кажется ключ к разгадке

[Karpion]

del

[aslepov78]

Порция унижения. 1й вопрос — даже готовое решение с трудом понимаю. Это тест на мат эрудию? Или что, действительно вот так приходят и выкладывают решение в приятной беседе?

[ptyrss]

Это известный факт, что только у полных квадратов нечётное число делителей. Доказать тоже не сложно (до корня и после всегда поровну. Значит есть сам корень). Все длинные рассуждения можно не писать.

[longclaps]

Find a Number X whose sum with its digits is equal to N

def f(N):
    res = []
    for x in range(max(N - 9 * len(str(N)), 1), N):
        if x + sum(map(int, str(x))) == N:
            res.append(x)
    print(f'N = {N}, X : {res or [-1]}')


f(21)
f(5)
f(100000001)

вывод
N = 21, X : [15]
N = 5, X : [-1]
N = 100000001, X : [99999937, 100000000]


[IIvana]

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

на неземном волшебном

f n = n==1 || r==0 && f q where (q,r) = quotRem n 2

про сортированный массив — тоже очевидно.

Но для школьников старших классов вполне подходящие задачки на факультатив.

[Deosis]

Не знаю, была ли подобная задача тут или нет.

В комнате находится шахматная доска, на каждой клетке которой лежит по одной монете.
Первый участник заходит в комнату и узнает "ключевую" клетку.
Он может перевернуть не более одной любой монеты.
Задача второго участника найти "ключевую" клетку.

ПС

Попытка передать информацию с помощью сдвига монеты к краю, поворота, царапин и т.п. недопустима.

[ptyrss]

Была. Даже статья отдельная на хабре была. habrahabr.ru/post/250585

[Nick_mentat]

прячу ответы

1) остануться открытыми полные квадраты и 1. 1,4,16,64,9,81,25,36,49,100
2) уже видел когда-то. Один выключатель нужно включить на время и выключить, чтобы найти соответствие по температуре.
1. if (sumarray(char a[] = (string(binary(x)))) == 1) then println(«power of two!»)
2. ищем пивот как в прошлонедельной задаче. Дальше переопределяем начало кольца этим пивотом. Всё, массив вернули в исходное состояние, для которого уже было готовое решение за такое время.
3. Положим, на входе 7 значное число. Максимум, который могут дать цифры в сумме — это 6 девяток и первая цифра числа — 1. Отступим от числа на 6*9+первая_цифра-1, и переберём небольшое число вариантов. Количество проверяемых чисел — пропорционален логарифму от входного числа. Проверка суммы цифр так же пропорциональна длине чисел, так что всего получаем быстроту O((log(N))^2).

[Nick_mentat]

Дополнение про двери: интересно, что в задаче упомянуто, что двери стоят в ряд, а не в кольцо. В этом смысле задача напоминает задачу о заключённом, и мы должны следить за положением человека — каждый раз доходя до конца ряда он будет вынужден проходить его в противоположном направлении. То есть каждую дверь он открыл, затем, идя в обратную сторону, закрыл каждую вторую — и это все нечётные двери, а не чётные. Точно так же в последнюю ходку он меняет состояние 1 двери, а не последней. Открытыми останутся 1,2,3,4,8,9,16,18,25,29,32,36,49,50,51,64,69,72,81,83,93,98,99,100.
Глядя на этот ряд у меня возникает два вопроса: существует ли аналитический способ получить его? И почему он всё ещё содержит весь правильный ряд, как если бы мы делали прогоны в одну сторону? Если поменять количество дверей (я пробовал 101, чётные, нечйтные, полные квадраты и простые) то можно избавится от последней сотни, но на дальней перспективе, уже к 81, все меньшие полные квадраты сохраняются… Так странно… Очень не похоже на совпадение.

[smer44]

положение двери изменяется число раз равное количеству делителей числа включая единицу и само число, и соответственно если количество делителей нечётное, состояние двери изменится.
Но это если бы чувак ходил каждый раз в одном направлении, но тут явно имеется в виду что он ходит туда — обратно так что я сразу так не могу придумать формулу

[kimisa]

Я наверное в своей прошлой работе перерешала задач, что сейчас уже не хочу решать ничего из этого. Тем более на работе с такими задачами каждый день процентов 90 находящихся здесь не сталкиваются.
Но решить задачу это не показатель. На их решения обычно натаскивают. Не тривиальных задач довольно мало. Остальные решаются по известным алгоритмам. Поэтому основная проблема — отнести задачу к соответствующему типу задач.
P.S. Утверждаю это как бывший преподаватель высшей математики, готовила и к олимпиадным задачам и к ЕГЭ.