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

    Продолжаем публиковать интересные задачи от ведуших IT-компаний.

    КДПВ
    В подборку попали задачи, задаваемые на собеседованиях (обычно на должность инженера-разработчика) в Yahoo! Предлагаем Вам попробовать свои силы и постараться решить задачи самостоятельно — тогда вопросы на собеседовании вряд ли застанут Вас врасплох.

    Вопросы


    1. Total distance travelled by bee
      Two trains are on same track and they are coming toward each other. The speed of first train is 50 KMs/h and the speed of second train is 70 KMs/h. A bee starts flying between the trains when the distance between two trains is 100 KMs. The bee first flies from first train to second train. Once it reaches the second train, it immediately flies back to the second train … and so on until trains collide. Calculate the total distance traveled by the bee. Speed of bee is 40 KMs/h.

      Перевод
      Два поезда на одном пути едут навстречу друг другу. Скорость первого поезда — 50 км/ч, скорость второго — 70 км/ч. Пчела начинает летать между поездами, когда расстояние между ними равно 100 км. Пчела летит от первого поезда ко второму. Когда достигнет второго, немедленно летит обратно к первому… и продолжает так летать, пока поезда не столкнутся.
      Посчитайте дистанцию, пройденную пчелой, если её скорость 40 км/ч.

    2. Poisoned wine
      The King of a small country invites 240 senators to his annual party. As a tradition, each senator brings the King a bottle of wine. Soon after, the Queen discovers that one of the senators is trying to assassinate the King by giving him a bottle of poisoned wine. Unfortunately, they do not know which senator, nor which bottle of wine is poisoned, and the poison is completely indiscernible. However, the King has 5 prisoners he plans to execute. He decides to use them as taste testers to determine which bottle of wine contains the poison. After drinking the poisoned wine, one dies within 24 hours. The King needs to determine which bottle of wine is poisoned in 2 days so that the festivities can continue as planned. How can the King administer the wine to the prisoners to ensure that 48 hours from now he is guaranteed to have found the poisoned wine bottle?

      Перевод
      Король небольшой страны пригласил 240 сенаторов на ежегодное празднование. По традиции, каждый сенатор преподносит королю бутылку вина. Однако, вскоре королева узнала, что один из сенаторов пытается отравить короля, подарив ему отравленную бутылку вина. К несчастью, они не знают, ни кто этот сенатор, ни что за бутыль отравлена, к тому же, яд невозможно обнаружить. В королевской тюрьме есть 5 заключенных, приговоренных к скорой смерти. Король решает с их помощью вычислить отравленную бутылку вина. Яд подействует только через 24 часа — выпивший его умирает. Королю необходимо выявить, какая бутылка отравлена, за 2 дня, чтобы продолжить запланированные мероприятия. Как он может распределить вино между заключенными, чтобы гарантированно найти отравленную бутылку за 48 часов?

    Задачи


    1. Largest subarray with equal number of 0s and 1s
      Given an array containing only 0s and 1s, find the largest subarray which contain equal number of 0s and 1s.

      Examples:
      Input: arr[] = {1, 0, 1, 1, 1, 0, 0}
      Output: 1 to 6 (Starting and Ending indexes of output subarray)

      Input: arr[] = {1, 1, 1, 1}
      Output: No such subarray

      Input: arr[] = {0, 0, 1, 1, 0}
      Output: 0 to 3 Or 1 to 4

      Перевод
      Дан массив, содержащий нули и единицы. Необходимо найти наибольший подмассив, содержащий одинаковое количество 0 и 1.

      Примеры:
      Вход: arr[] = {1, 0, 1, 1, 1, 0, 0}
      Выход: 1 to 6 (Индексы входного массива)

      Вход: arr[] = {1, 1, 1, 1}
      Выход: No such subarray

      Вход: arr[] = {0, 0, 1, 1, 0}
      Выход: 0 to 3 Or 1 to 4

    2. Count total set bits
      Given a positive integer n, count the total number of set bits in binary representation of all numbers from 1 to n.

      Examples:

      Input: n = 3
      Output: 4

      Input: n = 6
      Output: 9

      Input: n = 7
      Output: 12

      Input: n = 8
      Output: 13

      Перевод
      Дано положительное целое число n, необходимо вычислить сумму битов всех чисел от 1 до n в двоичном представлении.

      Примеры:
      Вход: n=3
      Выход: 4

      Вход: n=6
      Выход: 9

      Вход: n=7
      Выход: 12

      Вход: n=8
      Выход: 13

    3. Find the repeating and the missing
      Given an unsorted n-sized array of integers. Array elements are in range from 1 to n. One number from set {1, 2, …n} is missing and one number occurs twice in array. Find these two numbers.

      Examples:

      arr[] = {3, 1, 3}
      Output: 2, 3 // 2 is missing and 3 occurs twice

      arr[] = {4, 3, 6, 2, 1, 1}
      Output: 1, 5 // 5 is missing and 1 occurs twice


      Перевод
      Дан неотсортированный массив целых чисел размерностью n. Элементы массива — последовательность чисел от 1 до n. Одно число в последовательности пропущено и одно — повторяется. Необходимо найти эти числа.

      Примеры:

      arr[] = {3, 1, 3}
      Output: 2, 3 // 2 пропущено, 3 повторяется

      arr[] = {4, 3, 6, 2, 1, 1}
      Output: 1, 5 // 5 пропущено, 1 повторяется



    Ответы будут даны в течение следующей недели — успейте решить. Удачи!

    Решения


    1. Вопрос 1
      Верный ответ был найден — 33, 3 км.

    2. Вопрос 2
      Решение состоит в том, чтобы пронумеровать бутылки числом в троичной системе, где каждый разряд соответствует действию каждого заключенного по отношению к бутылке:
      0 — не пил,
      1 — выпил в первый день
      2 — выпил во второй день.
      Так, например бутыль с кодом 11201 будет означать, что 1,2 и 5 заключенные выпили в первый день, третий заключенный выпил во второй день, а четвертый не пил — соответственно, если 1,2 и 5 умерли в первый день, а третий во — второй день, то эта бутыль отравлена.
      Всего уникальных комбинаций 3^5 = 243, т.е. по состоянию заключенный к истечению 48 часов можно будет однозначно определить какая бутыль отравлена.

      Решение тоже было предложено в комментариях.

    3. Задача 1
      Решение предполагает последовательное суммирование значений, причём, 0 рассматриваются как "-1". Один из вариантов был предложен тут

    4. Задача 2
      Вариант верного решения был предложени в комментарии

    5. Задача 3
      Один из вариантов решения — пройтись по массиву, используя абсолютное значение элемента как индекс и меняя знак у элемента под этим индексом. Тогда индекс элемента, который уже был помечен отрицательным — является повторяющимся значением.

      За второй проход нужно найти положительное значение:

      #include<stdio.h>
      #include<stdlib.h>
       
      void printTwoElements(int arr[], int size)
      {
          int i;
          printf("\n The repeating element is");
       
          for(i = 0; i < size; i++)
          {
              if(arr[abs(arr[i])-1] > 0)
                  arr[abs(arr[i])-1] = -arr[abs(arr[i])-1];
              else
                  printf(" %d ", abs(arr[i]));
          }
       
          printf("\nand the missing element is ");
          for(i=0; i<size; i++)
          {
              if(arr[i]>0)
                  printf("%d",i+1);
          }
      }
       
      /* Driver program to test above function */
      int main()
      {
          int arr[] = {7, 3, 4, 5, 5, 6, 2};
          int  n = sizeof(arr)/sizeof(arr[0]);
          printTwoElements(arr, n);
          return 0;
      }


      Сложность алгоритма — О(n).

    Spice IT Recruitment 143,44
    ИТ специализированное кадровое агентство
    Поделиться публикацией
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама
    Комментарии 49
    • +2
      Решения пока только вопросов.
      1 Вопрос.
      Как может пчела со скоростью 40 км\ч летать между поездами, когда у обоих скорость больше?
      Это тест на адекватность?
      Если убрать из рассмотрения этот момент, то скорость одного поезда относительно другого — 50+70 = 120 км\ч. 100 км они пройдут за 100\120 = 5\6 часа. За это время пчела пролетит (сама траектория не важна, она сама по себе летает) 5\6часа*40км\ч=100\3км. Т.е. чуть больше 33 км.

      2 Вопрос.
      Жутко не нравится моральная сторона вопроса. Это намек на рабовладельческий строй в компании? Можно же по другому сформулировать вопрос.
      Если бы по другому построили вопрос, тогда. решение такое. Мы можем разделить все бочки на 6 групп. Каждый раб выпивает только из одной своей группы все бочки. Если раб умирает, тогда бочка находится в его группе (если не умирает никто, то бочка в той группе, в которой никто не пил). Но тогда мы приходим к 240\6=40 бочкам и 4-м рабам на вторую попытку. Значит нужно действовать иначе.
      Делим все бочки на N групп, каждый раб выпивает из 2-х своих групп, так чтобы из каждой группы пили 2 раба. Понятно, что таких групп у нас (6*5\2=) 15. Тогда ценой потери 2-х рабов мы сократили перебор до 240\15 = 16 бочек и имеем 3-х рабов минимум. Теперь нумеруем каждую бочку, и переводим число в 2-е счисление. Теперь, нумеруем рабов. Каждый раб пьет из бочки с номером таким-то, если бит этого номера соответствует номеру раба. По состоянию рабов мы можем понять в какой из (2^3=) 8-ми бочек яд. Но нам надо протестить 16 бочек. Значит нужно поделить бочки на группы не в равном количестве, чтобы больше приходилось на ту группу, где гибнет меньшее число рабов.
      Итак, за вторую попытку если у нас осталось жить m рабов, мы можем определить ядовитую среди 2^m бочек.
      Делим все бочки на 32 группы. Из бочки группы пьем раб, если он соответствует биту номера группы. Итого, в 1 случае гибнут все рабы, в 5 случаях 4 раба, в 10 случаях 3 раба, 10 случаях 2 раба, в 5 случаях 1 раб и в 1 случае ни одного. Следовательно мы можем определить бочку из 1*1+5*2+10*4+10*8+5*16+1*32 = 243.

      • 0
        > Жутко не нравится моральная сторона вопроса.
        Согласен, однако, если отрешиться от морали — задача интересная. Завернул в другую обёртку.
        • 0
          Отличный ход про короля и сенаторов.
          1 задача
          Легко решить за 2 прохода, если использовать дополнительный массив длинной 2*n.
          Проходим по массиву. Изначально счетчик с=0. Если встречаем 1, то прибавляем 1, если встречаем 0, то вычитаем 1. Далее по адресу c+n заносим значение текущей позиции.
          Второй проход, делаем тоже самое, но вместо записи во второй массив считываем значение из ячейки c+n и вычитаем текущую позицию. И находим максимум вычисленного значения.
          Можно сократить размер массива до n+1 если номер ячейки вычислять как с%(n+1)

          Задача 2
          Влоб решается легко 2-мя циклами, вероятно от кандидата хотят сокращения вычисления.
          Пока в голову приходит что сумма битов чисел от 1 до (2^n)-1 равно (2^n)*n/2.

          Задача 3
          Ищем сумму чисел и квадрат суммы чисел за 1 проход. Вычитаем сумму и квадрат суммы чисел для случая, если бы все числа были правильными. Пусть m — лишнее число, а k — не хватает. С помощью суммы мы получаем A= (m-k), а через сумму квадратов получаем B=(m^2-n^2). Откуда например m = (A+B/A)/2.
          • +1

            Задачу 2 можно решить и в один цикл :)


            Способ решения за 1 цикл

            Можно посчитать, сколько раз каждый бит (с номером 0,1,2...) будет встречаться в значении 1 в числах от 1 до n.


            Если выписать в двоичном виде числа 0,1,2,3,4,5..., то можно увидеть, что:
            0-й бит встречается в каждом втором числе, паттерн: 0,1,0,1,0,1,0,1,…
            1-й бит встречается дважды в каждой четвёрке чисел, паттерн: 0,0,1,1,0,0,1,1,…
            2-й бит встречается четырежды в каждой восьмёрке чисел, паттерн: 0,0,0,0,1,1,1,1,…

            n-й бит встречается (2^n) раз в каждой полной группе из (2^(n+1)) чисел.


            Дополнительно нужно обработать "остатки" от деления числа n на степени 2-ки.
            Допустим, число 14 дало остаток 6 при делении на 8. При этом, в числах от 9 до 14 второй бит встретится в значении 1 трижды (числа 12,13,14), и эти 3 единичных бита тоже добавляем к результату.


            Код на языке C#
            using System;
            
            class Solution
            {
                static void Solve(int n)
                {
                    int result = 0;
            
                    for (int k = 1; k <= n; k = k << 1)
                    {
                        result += k * (n / (k << 1));
                        result += Math.Max(((n % (k << 1)) + 1) - k, 0);
                    }
            
                    Console.WriteLine($"n = {n}, result = {result}");
                }
            
                static void Main(string[] args)
                {
                    foreach (int n in (new int[] { 3, 6, 7, 8 }))
                        Solve(n);
                }
            }
            • 0
              Сам понял, что можно за 1 цикл, когда писал решение.
              • 0
                Причем ваш код работает, а в моем ошибка.
              • 0
                Решение в виде кода
                Задача 1
                public static int[] largestSubarray(int[] array){
                        final int n = array.length+1;
                        int[] secondArray = new int[n];
                        int c = 0;
                        // Первый проход - заполняем массив
                        for(int i=0; i<array.length; i++){
                            if(array[i]==1){
                                c++;
                            }else{
                                c--;
                            }
                            secondArray[c%n]=i;
                        }
                        // Второй проход - ищем максимальную длинну подмассива
                        c = 0;
                        int index = -1;
                        int maxValue = secondArray[0]+1;
                        for(int i=0; i<array.length; i++){
                            if(array[i]==1){
                                c++;
                            }else{
                                c--;
                            }
                            if(secondArray[c%n]-i>maxValue){
                                maxValue = secondArray[c%n]-i;
                                index = i;
                            }
                        }
                        // Если найден подмассив
                        if(maxValue>1){
                            int result[] = new int[2];
                            result[0] = index+1;
                            result[1] = index+maxValue;
                            return result;
                        }
                        return null;
                    }


                Задача 2
                public static int totalBits(int value){
                        int count =0;
                        int mask = 1;// 0001, 0010, 0100, 1000 ...
                        int mask2 =0;// 0000, 0001, 0011, 0111 ...
                        while(value>mask){   
                            count+=(value&mask2);
                            count+=(value -(value&(mask+mask2)) )/2;
                            mask2+=mask;
                            mask = mask + mask;
                        }
                        return count;
                    }
                


                Задача 3
                
                public static int[] findRepeatingMissing(int[] array){
                        int a =0;
                        long b =0;
                        for(int i=0; i<array.length; i++){
                            a+=array[i]-i;
                            b+=array[i]*array[i]-i*i;
                        }
                        int result[] = new int[2];
                        result[0] = (int)(a+b/a)/2;
                        result[1] = a - result[0];
                        return result;
                    }

                • 0
                  В задаче 2 ошибка
                  Правильное решение
                      public static int totalBits(int value){
                          int count =0;
                          int mask = 1;// 0001, 0010, 0100, 1000 ...
                          int mask2 =0;// 0000, 0001, 0011, 0111 ...
                          while(value>=mask){
                              if((value&mask)>0){
                                  count+=(value&mask2)+1;
                              }
                              count+=(value -(value&(mask+mask2)) )/2;
                              mask2+=mask;
                              mask = mask + mask;
                          }
                          return count;
                      }


                  Обидно, что перед отправкой проверял, но попал именно на те значения, на которых ошибки не было.
                  • 0
                    Решение задачи верное, но не содержит объяснения.

                    Обозначим Si суммарное кол-во единичек минус суммарное кол-во ноликов от начала последовательности до позиции i (не включая саму i).

                    Тогда нужный нам подмассив, начинающийся с позиции i и заканчивающийся на j, обладает свойством Si = Sj+1. Нам нужно найти сами индексы i и j. Можно использовать «жадный» алгоритм, что если Si = Sj+1 для разных i, j, мы берём минимальный i и максимальный j.

                    В массив R (secondArray) положим индекс j, такой, что R[Sj] = j.
                    Причём, если для разных j1 < j2 одинаковое Sj1 = Sj2, то в массив R положим последний j2 (т.е. больший). Это обеспечивается тем, что первый цикл, который последовательно вычисляет Si, замещает в массиве R ранее записанное значение i на следующее, большее.

                    Второй проход снова последовательно считает Si, и сразу для рассчитанного Si из массива R получает индекс j — максимальный индекс, такой, что Si=Sj.

                    Извращение с Si mod n нужно, чтобы привести значения Si, которые используются для индекса к X, из диапазона [-n;n] к [0;2*n] (кстати, не очень понял, почему для secondArray достаточно длины n).
                    • +1
                      (кстати, не очень понял, почему для secondArray достаточно длины n

                      Достаточно длины (n+1), если n — длина исходного массива. Если у нас например все 1, то счетчик дойдет до n, и так как n%(n+1)=n, то последний элемент все равно не совпадет с первым элементом, у которого индекс 0. Также верно и в обратную сторону.
              • 0
                Вы, вроде бы, не уложились в 48 часов?
                • 0
                  Почему? 48 часов — это 2 попытки. И в самом низу решения я указал, как за эти 2 попытки найти бочку. Может я скомкано объяснил. Всё, что выше последнего абзаца — это рассуждения в слух. Последний абзац — это решение.
                  • 0
                    Пардон, я не понял, что первые два абзаца вашего ответа нужно удалить.
                • 0
                  2 задача. а что если 1 день всех поить и записывать кто во сколько из какой бутылки выпил а на 2 день смотреть кто умрет,-24ч и бутылка известна, тут и заключенных можно меньше применить, и время сократиться
                  • 0
                    After drinking the poisoned wine, one dies within 24 hours
                    Не «через 24 часа», а «в течение следующих 24 часов».
                  • +1
                    Как может пчела со скоростью 40 км\ч летать между поездами, когда у обоих скорость больше?


                    Хорошее замечание. Надо было написать «пытается летать» — по тому правилу, которое сформулировано дальше. При этом результат не изменится.
                    • 0
                      про моральную сторону этоя сам был в шоке. оригинал задачи про короля и заключённых ожидающих смертную казнь. куда катится этот мир.
                    • –1
                      В реале ведь такое не спрашивают, везде все по разному

                      Было бы имхо больше пользы, если бы IT сообщество просто поделилось бы опытом о своих собеседованиях на ресурсах типа Jobingood.
                      • 0
                        Я ни разу не собеседовался в компании мирового уровня, однако такие посты и книги вроде «Cracking the coding interview» наводят на мысль, что задачи все-таки спрашивают. Да и похожего плана задачки встречались в менее крупных компаниях.

                        Ну и мне лично интересно порешать их после рабочей недели :)
                        • +1
                          Если интересно подготовиться к реальному интервью в компанию мирового уровня — лучше посмотреть отзывы про интервью именно в эту компанию на GlassDoor. Поэтому я и написал — что было бы круто если бы в России такой же ресурс был.

                          А интерес порешать — да, интересно. :)
                      • –2

                        Вопрос — какое отношение имеет физическая задача про муху к программированию — то есть что оценивается
                        Я такие задачи решал еще в школе (как и про яд)
                        На собеседовании по програмиированию ожидаешь более профессиональные вопросы в рамках профессиональных требований — типа а почему NoSQL — в чем преимущество.
                        Или как-то меня спрашивали про оценки времени запроса к серверу.
                        То есть ответы должны отражать имеющийся профессиональный уровень по отношению к ожидаемому

                        • 0
                          Да, вопросы технического плана составляют большую часть интервью, но нередко задают и такие задачи. Причин может быть несколько — например, оценить как человек себя ведёт, столкнувшись проблемой, решения которой не знает, посмотреть на ход рассуждений или на реакцию соискателя.
                          • –1

                            Я проходил достаточное количество собеседований в разные фирмы — и появление в них задач подобного плана оценивал, как пустую трату времени — тем более я мог задать подобную задачу задающему ее сотруднику, и не думаю. что он мог бы ее решить.
                            А причины указанные вами надуманные. Ход рассуждений никто не спрашивает. реакцию никто не оценивает — интересует ответ.

                            • +3
                              Вы можете оценивать, как хотите — ваше право.
                              Возможно, другая сторона думает совсем иначе.
                              Да, есть вакансии, где нужен конкретный спец под конкретное дело с учетом того, что выбранный инструмент — это надолго.
                              Но посмотрите с другой стороны, сейчас всё очень быстро меняется, через полгода ваш любимый фреймворк или любимая база данных (в которой вы спец и можете ответить на любой технический вопрос) устареет и будет заменена на другую. И компания получит бесполезного работника в виде вас.
                              А вот если человек не знает технических тонкостей, но соображает (хорошо решает подобные задачи), то он быстро разберется в технологии и по ходу разберется что и как.
                              Конечно, важно и умение соображать и знание конкретной технологии, но я бы оценивал их как 2 к 1.
                              тем более я мог задать подобную задачу задающему ее сотруднику

                              Смысл? Проверяются ваши качества, а не того сотрудника.
                              В лучшем случае у вас будет материал для беседы, в худшем минус бал (или 2) для вас за сомнительное поведение.

                              Вот меня часто просят рассказать «ход рассуждений». Так, что вот вам пример (в виде меня), опровергающий ваше мнение.
                              • –2

                                Как говорится в юриспруденции — ваше слово на мое слово ничего не опровергает, как и мое слово на ваше слово.
                                Интересн контекст.
                                Я работал сотрудником и работал руководителем, проводил собеседования и оценивал результаты собеседования по работе принятого сотрудника.
                                То есть для меня за моими словами стоит мой опыт — видимо он не пересекается с вашим опытом, но все же я уважаю ваше мнение и не опровергаю его — я высказываю свое мнение.
                                Кстати, ради интереса — а в чем изюминка задачи про муху

                                • +1
                                  Задача про муху для меня самого не понятна. Если бы там были корректные условия (муха в 2 раза быстрей), то такие задачи могут даваться, чтобы расслабить кандидата. Очень часто кандидаты волнуются (и этим мешают понять что они такое). А так человек получил простую задачу, решил, увидел, что ничего сверхестественного от него не требуется (как например разводить море подобно Моисею).
                                  Ещё есть класс задач, которые легко решают дети, но не могут решить взрослые люди. Т.е. будет лучше, если кандидат не сможет решить такую задачу. www.lprobs.ru/prob37solve.html
                                  Ещё был случай, когда на собеседовании после 9 чисто технических вопросов по языку дали простую задачу по геометрии. Зачем это сделали — не знаю. Видимо я много ещё чего не понимаю в собеседованиях.
                                  • –1

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

                                    • +1
                                      я думаю что такой класс задач на преодоление инертности мышления. про муху это нужно забыть о том что муха не догонит поезд и сконцентрироваться на условии что летит пока поезда не столкнуться. по поводу задачи с вином я признаюсь не решил её и подсмотрел ответ решение было абсолютно правильным но вот все делается гораздо проще если ****** ***** ******.
                                      • –1

                                        Не понял ваше замечание про муху — она всегда летит навстречу одному или другому поезду, то есть не догоняет, а встречает один или другой в полете.
                                        Даю подобную задачу — я нахожусь около трамвайных путей и имею возможность остановить трамвай в любой точке пути. Место, куда мне нужно прибыть, достаточно далеко, так что при движении пешком трамвай обязательно появится. Вопрос — в каком направлении выгодно двигаться: навстречу трамваю, чтобы быстрее его встретить или по ходу движения трамвая. чтобы меньше осталось расстояния до нужной точки. Ясно, что скорость трамвая больше, чем моя скорость движения.

                                        • 0
                                          в вашей постановке задачи направление движения каи само движение не имеет влияния на результат т.к. трамвай обязательно будет встречен и пассажир приедет в пункт назначения на одном и том же трамвае. моё замечание касалось не решения задачи а того зачем нужны подобные задачи. они не совсем стандартные хотя выглядят похоже на школьные задачи для учеников 1класса.
                        • 0
                          Вопрос 2

                          Делим бутылки поровну между заключенными: 48 на каждого. Каждый пьет из новой бутылки раз в 30 минут, закончит через 23 часа 30 минут. Ждем пока умрет заключенный, замеряем сколько минут прошло с момента начала эксперимента. Отравленная бутылка будет иметь номер (время-23.5*60) div 30.
                          Уменьшая задержку между бутылками можно увеличить количество бутылок для проверки.

                          • 0
                            Нет, известно лишь, что смерть наступит в течение 24 часов, а не ровно через 24 часа.
                            • 0

                              The poison when taken has no effect on the prisoner until exactly 24 hours later when the infected prisoner suddenly dies.
                              Как минимум 24 часа. Если больше, а не ровно, то решений уже нет: два раза по больше чем 24 превысит 48

                              • 0
                                Опс. В оригинальной формулировке, на которую дал правильный ответ kardan2, было именно так, как я только что написал. А так, как сейчас, конечно, проще.

                                Автор?
                                • 0
                                  Верно, изначально было «в течение», вернул исходный вариант. Решение GrigorGri правильно для варианта «точно через 24 часа».
                                  • 0
                                    В английском тексте тоже плохая формулировка.
                                    Русские варианты не читал вообще, но для английского «exact» получается довольно тривиальное решение: один смертник пьёт все 240 бутылок с перевывом в 5 минут. Если смерть наступает ровно через 24 часа, часы нам покажут, какая бутылка сработала.

                                    Есть формулировка получше: волшебный яд действует ровно в 12:00 (в полдень), поэтому до дедлайна есть только 2 попытки проверить бутылки на каждом смертнике.
                          • 0
                            .
                            • +2
                              В первой задаче имеется ввиду скорость относительно дороги или поезда от которого летит? Если первое, как это по дефолту, то пролетит до столкновения 100/(50+70)*40, отстав от первого поезда и до второго недолетев ни разу.
                              • 0
                                Задача про биты:
                                Помогите довести

                                Подсчитаем для каждого 2^n числа сумму всех бит чисел до него включительно:
                                Для 0: 0;
                                Для 1: 0, 1, s=1
                                Для 2^n = s[2^(n-1)] * 2 + 2^n; // так как на порядок ниже все числа повторяются, с 1

                                Далее имеем: {0..10100} = {0..10000} + 10{0..100}

                                Если это добить, получится решение, которое работает ~за кол-во бит операций
                                • +1

                                  Вроде бы никто не писал такое решение задачи 2. Занумеруем бутылки в системе счисления по основанию 3. Дальше думаю все понятно. 3^5=243 как раз.


                                  Как по мне решение простое и эффективное.

                                  • 0
                                    да это решение и предполагалось. Суть задачи это преодолеть стереотип что существует три системы счисления 2 10 и 16
                                    • 0
                                      Раскройте свою идею полнее.

                                      У эксперимента 2 исхода: умер или нет.
                                      Смертнику можно дать N-ю бутылку или нет.
                                      На этом основано решение с двоичной нумераций.
                                      Как переложить на троичную нумерацию?
                                      • +1
                                        3 состояния. не умер, умер в 1 день, умер во 2 день. Дальше не пишу — и так подсказка большая)
                                        • 0
                                          Под спойлер? :)
                                      • 0
                                        А можно чуть подробнее про алгоритм «дегустации»? Чем он проще, чем деление на 2^5 групп разного размера, чтобы выживших на первом шаге хватило на второй?
                                      • 0
                                        Если нумеровать бутылки двично то есть два состояния. Выпить или не выпить и этих состояний не хватает. Для того чтобы 5-ю разрядами занумеровать 240 бутылок.
                                        Если нумеровать бутылки троично то можно 5-ю разрядами занумеровать. Трактовать следующим образом
                                        0 — не пить из бутылки
                                        1 — выпить из бутылки
                                        2 — *** (пока удалил т.к. возможно кто-то еще захочет решить)
                                        • 0
                                          Те кто говорит что такие вопросы не нужны наверное тоже правы. Если компания разрабатывает например несложные сайты и не собирается делать что то другое то такой излишне творческий человек или уйдёт очень но скоро или же начнёт разрабатывать «свою CMS»(ТМ)
                                          • 0
                                            Маленький косяк в моем решении. Оператор деления по модулю даёт циклическую последовательность на выходе, т.е. 1,2,3,4,5,6,7,8… %3 даст 1, 2, 0, 1, 2, 0, 1, 2, 0…
                                            Я почему-то думал, что если 2%3=2, 1%3=1, 0%3=0, то и -1%3 даст опять 2. Но нет, -1%3=-1.
                                            Поэтому в моем решении нужно перед взятием по модулю прибавлять то самое n (или n+1).
                                            • 0
                                              По идее так и должно быть по модулю но не во всех языках так реализовано. Например в Пайтоне честно дается -1%3=-2

                                            Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                            Самое читаемое