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

    Публикуем очередную подборку задач и вопросов с собеседований в крупных IT-компаниях (для тех, кому мало задач из предыдущего сета :)

    КДПВ

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

    Вопросы


    1. Ants in corners
      There are 3 ants sitting on three corners of a triangle. All ants randomly pick a direction and start moving along edge of the triangle. What is the probability that any two ants collide?

      Перевод
      3 муравья находятся в разных углах треугольника. Все муравьи начинают движение в случайно выбранном направлении вдоль сторон треугольника. Какова вероятность столкновения 2-х муравьёв?

    2. Red hat / blue hat
      A team of three people decide on a strategy for playing the following game. Each player walks into a room. On the way in, a fair coin is tossed for each player, deciding that player’s hat color, either red or blue. Each player can see the hat colors of the other two players, but cannot see her own hat color. After inspecting each other’s hat colors, each player decides on a response which are one of the following:
      — “I have a red hat”
      — “I had a blue hat”
      — “I pass”

      The player’s responses are recorded, but the responses are not shared until every player has recorded her response. The team wins if at least one player responds with a color and every color response correctly describes the hat color of the player making the response. In other words, the team loses if either everyone responds with “I pass” or someone responds with a color that is different from her hat color. What strategy should one use to maximize the team’s expected chance of winning?

      For example, one possible strategy is to single out one of the three players. This player will respond “I have a red hat” and the others will respond “I pass”. The expected chance of winning with this strategy is 50%. Can you do better?

      Перевод
      Команда из трёх человек выбирает стратегию для игры в следующую игру: каждый игрок заходит в комнату. На входе подкидыванием правильной монеты определяется цвет шляпы игрока — красная или синяя. Каждый игрок может видеть цвета шляп 2-х других игроков, но не своей. После ознакомления с цветами, игрок может выбрать один из вариантов ответа:
      — У меня красная шляпа
      — У меня синяя шляпа
      — Я пас
      Ответы всех игроков записываются, но не показываются другим игрокам, до того момента, пока все не ответят. Команда побеждает, если хотя бы один игрок написал цвет в ответе и если все цвета были указаны правильно. Другими словами, команда проигрывает, если все ответят «Я пас» или кто-то ошибётся с определением своего цвета. Какая стратегия может увеличить шансы команды на победу?

      Например, одним из возможных вариантов является ответ только избранного игрока. Этот игрок отвечает «У меня красная шляпа» или «У меня синяя шляпа», остальные пасуют. Ожидаемая вероятность победить при такой стратегии — 50%. Сможете ли Вы предложить лучшее решение?


    Задачи


    1. Special keyboard
      Imagine you have a special keyboard with the following keys:
              A
              Ctrl+A
              Ctrl+C
              Ctrl+V 
      

      where CTRL+A, CTRL+C, CTRL+V each acts as one function key for “Select All”, “Copy”, and “Paste” operations respectively.
      If you can only press the keyboard for N times (with the above four keys), please write a program to produce maximum numbers of A. If possible, please also print out the sequence of keys.
      That is to say, the input parameter is N (No. of keys that you can press), the output is M (No. of As that you can produce).

      Ex:

      Input: N = 3
      Output: 3
      We can at most get 3 A's on screen by pressing following key sequence.
      A, A, A

      Input: N = 7
      Output: 9
      We can at most get 9 A's on screen by pressing following key sequence.
      A, A, A, Ctrl A, Ctrl C, Ctrl V, Ctrl V

      Input: N = 11
      Output: 27
      We can at most get 27 A's on screen by pressing following key sequence.
      A, A, A, Ctrl A, Ctrl C, Ctrl V, Ctrl V, Ctrl A, Ctrl C, Ctrl V, Ctrl V

      Перевод
      Представьте, что у Вас есть специальная клавиатура со следующим клавишами:
              A
              Ctrl+A
              Ctrl+C
              Ctrl+V 
      

      где CTRL+A, CTRL+C, CTRL+V работают как «Выбрать всё», «Скопировать», «Вставить» соответственно.
      Вы можете нажать на клавиатуру N раз (только на указанные клавиши). Напишите программу, дающую максимальное количество «A» с помощью этих операций. Если возможно, выведите также последовательность нажатий. Иначе говоря, вход — N (количество нажатий), вывод — M (количество «А», которые можно получить).
      Примеры:
      Вход: N = 3
      Выход: 3
      Можем получить максимум 3 A следующей последовательностью нажатий: A, A, A

      Вход: N = 7
      Выход: 9
      Максимум — 9 А, последовательность: A, A, A, Ctrl A, Ctrl C, Ctrl V, Ctrl V

      Вход: N = 11
      Выход: 27
      Максимум — 27 А, последовательность: A, A, A, Ctrl A, Ctrl C, Ctrl V, Ctrl V, Ctrl A, Ctrl C, Ctrl V, Ctrl V

    2. Boolean parenthesization
      Given a boolean expression with following symbols.

      Symbols
      'T' ---> true
      'F' ---> false

      And following operators filled between symbols

      Operators
      & ---> boolean AND
      | ---> boolean OR
      ^ ---> boolean XOR

      Count the number of ways we can parenthesize the expression so that the value of expression evaluates to true.

      Let the input be in form of two arrays one contains the symbols (T and F) in order and other contains operators (&, | and ^}

      Examples:

      Input: symbol[] = {T, F, T}
      operator[] = {^, &}
      Output: 2
      The given expression is «T ^ F & T», it evaluates true in two ways "((T ^ F) & T)" and "(T ^ (F & T))"

      Input: symbol[] = {T, F, F}
      operator[] = {^, |}
      Output: 2
      The given expression is «T ^ F | F», it evaluates true in two ways "( (T ^ F) | F )" and "( T ^ (F | F) )".

      Input: symbol[] = {T, T, F, T}
      operator[] = {|, &, ^}
      Output: 4
      The given expression is «T | T & F ^ T», it evaluates true in 4 ways ((T|T)&(F^T)), (T|(T&(F^T))), (((T|T)&F)^T) and (T|((T&F)^T)).

      Перевод
      Дано логическое выражение со следующими символами:

      Символы
      'T' ---> true
      'F' ---> false

      И следующие операторы, вставляемые между символами:

      Операторы
      & ---> логическое И
      | ---> логическое ИЛИ
      ^ ---> исключающее ИЛИ

      Подсчитайте количество вариантов расстановки скобок, чтобы значение выражения стало равным true.

      Допустим, вводные данные представлены в виде 2-х массивов — символов (T и F) и операторов (&, | и ^).

      Примеры:

      Вход: symbol[] = {T, F, T}
      operator[] = {^, &}
      Выход: 2
      Выражение «T ^ F & T», становится равным true в 2-х случаях: "((T ^ F) & T)" и"(T ^ (F & T))"

      Вход: symbol[] = {T, F, F}
      operator[] = {^, |}
      Выход: 2
      Выражение «T ^ F | F», становится равным true в 2-х случаях "( (T ^ F) | F )" и "( T ^ (F | F) )".

      Вход: symbol[] = {T, T, F, T}
      operator[] = {|, &, ^}
      Выход: 4
      Выражение «T | T & F ^ T», становится равным true в 4-х случаях: ((T|T)&(F^T)), (T|(T&(F^T))), (((T|T)&F)^T) and (T|((T&F)^T)).

    3. Alien language
      Given a sorted dictionary (array of words) of an alien language, find order of characters in the alien alphabet.

      Examples:

      Input: words[] = {«baa», «abcd», «abca», «cab», «cad»}
      Output: Order of characters is 'b', 'd', 'a', 'c'
      Note that words are sorted and in the given language «baa» comes before «abcd», therefore 'b' is before 'a' in output. Similarly we can find other orders.

      Input: words[] = {«caa», «aaa», «aab»}
      Output: Order of characters is 'c', 'a', 'b'

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

      Примеры:

      Вход: words[] = {«baa», «abcd», «abca», «cab», «cad»}
      Выход: Порядок букв 'b', 'd', 'a', 'c'
      Заметим, что 'baa' идёт перед 'abcd', следовательно в алфавите 'b' стоит перед 'a'. Аналогичным образом узнаем порядок других букв.

      Input: words[] = {«caa», «aaa», «aab»}
      Выход: Порядок букв 'c', 'a', 'b'.



    Решения


    1. Вопрос 1
      В комментарии нашли правильный ответ.

    2. Вопрос 2
      В комментариях нашли правильный ответ для варианта «вслепую», когда игроки не видят кто уже ответил.

    3. Задача 1
      Вариант решения на Java:
      /* A recursive C program to print 
        maximum number of A's using 
        following four keys */
      import java.io.*;
      
      class GFG {
      
          // A recursive function that returns 
          // the optimal length string  for N keystrokes
          static int findoptimal(int N)
          {
              // The optimal string length is N
              // when N is smaller than 7
              if (N <= 6)
                  return N;
          
              // Initialize result
              int max = 0;
          
              // TRY ALL POSSIBLE BREAK-POINTS
              // For any keystroke N, we need to
              // loop from N-3 keystrokes back to 
              // 1 keystroke to find a breakpoint 
              // 'b' after which we will have Ctrl-A,
              //  Ctrl-C and then only Ctrl-V all the way.
              int b;
              for (b = N - 3; b >= 1; b--)
              {
                      // If the breakpoint is s at b'th 
                      // keystroke then the optimal string 
                      // would have length
                      // (n-b-1)*screen[b-1];
                      int curr = (N - b - 1) * findoptimal(b);
                      if (curr > max)
                          max = curr;
              }
              return max;
          }
          
          // Driver program
          public static void main(String[] args)
          {
              int N;
          
              // for the rest of the array we
              // will rely on the previous
              // entries to compute new ones
              for (N = 1; N <= 20; N++)
                  System.out.println("Maximum Number of A's with keystrokes is " +
                                      N + findoptimal(N));
          }
      }
      
      


    4. Задача 2
      Вариант решения:
      #include<iostream>
      #include<cstring>
      using namespace std;
      
      // Returns count of all possible parenthesizations that lead to
      // result true for a boolean expression with symbols like true
      // and false and operators like &, | and ^ filled between symbols
      int countParenth(char symb[], char oper[], int n)
      {
          int F[n][n], T[n][n];
      
          // Fill diaginal entries first
          // All diagonal entries in T[i][i] are 1 if symbol[i]
          // is T (true).  Similarly, all F[i][i] entries are 1 if
          // symbol[i] is F (False)
          for (int i = 0; i < n; i++)
          {
              F[i][i] = (symb[i] == 'F')? 1: 0;
              T[i][i] = (symb[i] == 'T')? 1: 0;
          }
      
          // Now fill T[i][i+1], T[i][i+2], T[i][i+3]... in order
          // And F[i][i+1], F[i][i+2], F[i][i+3]... in order
          for (int gap=1; gap<n; ++gap)
          {
              for (int i=0, j=gap; j<n; ++i, ++j)
              {
                  T[i][j] = F[i][j] = 0;
                  for (int g=0; g<gap; g++)
                  {
                      // Find place of parenthesization using current value
                      // of gap
                      int k = i + g;
      
                      // Store Total[i][k] and Total[k+1][j]
                      int tik = T[i][k] + F[i][k];
                      int tkj = T[k+1][j] + F[k+1][j];
      
                      // Follow the recursive formulas according to the current
                      // operator
                      if (oper[k] == '&')
                      {
                          T[i][j] += T[i][k]*T[k+1][j];
                          F[i][j] += (tik*tkj - T[i][k]*T[k+1][j]);
                      }
                      if (oper[k] == '|')
                      {
                          F[i][j] += F[i][k]*F[k+1][j];
                          T[i][j] += (tik*tkj - F[i][k]*F[k+1][j]);
                      }
                      if (oper[k] == '^')
                      {
                          T[i][j] += F[i][k]*T[k+1][j] + T[i][k]*F[k+1][j];
                          F[i][j] += T[i][k]*T[k+1][j] + F[i][k]*F[k+1][j];
                      }
                  }
              }
          }
          return T[0][n-1];
      }
      
      // Driver program to test above function
      int main()
      {
          char symbols[] = "TTFT";
          char operators[] = "|&^";
          int n = strlen(symbols);
      
          // There are 4 ways
          // ((T|T)&(F^T)), (T|(T&(F^T))), (((T|T)&F)^T) and (T|((T&F)^T))
          cout << countParenth(symbols, operators, n);
          return 0;
      }
      


    5. Задача 3
      Вариант решения:
      // A C++ program to order of characters in an alien language
      #include<iostream>
      #include <list>
      #include <stack>
      #include <cstring>
      using namespace std;
      
      // Class to represent a graph
      class Graph
      {
          int V;    // No. of vertices'
      
          // Pointer to an array containing adjacency listsList
          list<int> *adj;
      
          // A function used by topologicalSort
          void topologicalSortUtil(int v, bool visited[], stack<int> &Stack);
      public:
          Graph(int V);   // Constructor
      
          // function to add an edge to graph
          void addEdge(int v, int w);
      
          // prints a Topological Sort of the complete graph
          void topologicalSort();
      };
      
      Graph::Graph(int V)
      {
          this->V = V;
          adj = new list<int>[V];
      }
      
      void Graph::addEdge(int v, int w)
      {
          adj[v].push_back(w); // Add w to v’s list.
      }
      
      // A recursive function used by topologicalSort
      void Graph::topologicalSortUtil(int v, bool visited[], stack<int> &Stack)
      {
          // Mark the current node as visited.
          visited[v] = true;
      
          // Recur for all the vertices adjacent to this vertex
          list<int>::iterator i;
          for (i = adj[v].begin(); i != adj[v].end(); ++i)
              if (!visited[*i])
                  topologicalSortUtil(*i, visited, Stack);
      
          // Push current vertex to stack which stores result
          Stack.push(v);
      }
      
      // The function to do Topological Sort. It uses recursive topologicalSortUtil()
      void Graph::topologicalSort()
      {
          stack<int> Stack;
      
          // Mark all the vertices as not visited
          bool *visited = new bool[V];
          for (int i = 0; i < V; i++)
              visited[i] = false;
      
          // Call the recursive helper function to store Topological Sort
          // starting from all vertices one by one
          for (int i = 0; i < V; i++)
              if (visited[i] == false)
                  topologicalSortUtil(i, visited, Stack);
      
          // Print contents of stack
          while (Stack.empty() == false)
          {
              cout << (char) ('a' + Stack.top()) << " ";
              Stack.pop();
          }
      }
      
      int min(int x, int y)
      {
          return (x < y)? x : y;
      }
      
      // This function fidns and prints order of characer from a sorted
      // array of words. n is size of words[].  alpha is set of possible
      // alphabets.
      // For simplicity, this function is written in a way that only
      // first 'alpha' characters can be there in words array.  For
      // example if alpha is 7, then words[] should have only 'a', 'b',
      // 'c' 'd', 'e', 'f', 'g'
      void printOrder(string words[], int n, int alpha)
      {
          // Create a graph with 'aplha' edges
          Graph g(alpha);
      
          // Process all adjacent pairs of words and create a graph
          for (int i = 0; i < n-1; i++)
          {
              // Take the current two words and find the first mismatching
              // character
              string word1 = words[i], word2 = words[i+1];
              for (int j = 0; j < min(word1.length(), word2.length()); j++)
              {
                  // If we find a mismatching character, then add an edge
                  // from character of word1 to that of word2
                  if (word1[j] != word2[j])
                  {
                      g.addEdge(word1[j]-'a', word2[j]-'a');
                      break;
                  }
              }
          }
      
          // Print topological sort of the above created graph
          g.topologicalSort();
      }
      
      // Driver program to test above functions
      int main()
      {
          string words[] = {"caa", "aaa", "aab"};
          printOrder(words, 3, 3);
          return 0;
      }
      


    Spice IT Recruitment
    82.22
    ИТ специализированное кадровое агентство
    Share post
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More
    Ads

    Comments 45

      +2
      Вопрос 1
      Всего существует 2 ** 3 = 8 вариантов движения муравьёв. Муравьи не столкнутся, если движутся в одну сторону — 2 варианта из 8.
      Ответ: (8 — 2) / 8 = 0.75

        +1
        Муравьи
        Всего комбинаций 8, не столкнутся в 2, когда идут в одну сторону. Шанс 3/4

        Шляпы
        Раздам номера от 1 до 3 игрокам. Пусть, если на игроке 3 красная шляпа, первым спасует игрок 1, иначе игрок 2. Тогда игрок 3 знает цвет своей шляпы, отвечает, а оставшийся пасует. Шанс победы 100%

          +1
          Шляпы
          Ответы всех игроков записываются, но не показываются другим игрокам, до того момента, пока все не ответят

          Тайминг-атака не пройдёт :)

            0
            Шляпы
            В условии задачи не написано, что я не вижу что другой игрок дал ответ. Сказано лишь то, что я не вижу какой.
          +1
          Вопрос 1
          Муравьи не столкнутся, если двигаются в одну и ту же сторону — по часовой стрелке или против. Вероятности таких событий P1CW × P2CW × P3CW и P1CCW × P2CCW × P3CCW.
          Значит вероятность столкновения P = 1 − P1CW × P2CW × P3CW − P1CCW × P2CCW × P3CCW.
          Если направления движения выбираются равновероятно, то P = 1 − (1/2)3 − (1/2)3 = 3/4

          Вопрос 2
          Тут всё зависит от того, могут ли игроки подавать друг-другу какие-либо сигналы. Если да, то игрок, видящий на других шляпы одного цвета подаёт такой сигнал (например, первым пишет ответ 'pass'). Тогда два других игрока знают, что их шляпы одного цвета и могут правильно ответить.
            0

            Есть некоторые сомнения относительно того, что эти вопросы задают в Гугле. "Alient Language" — задача с квалификационного раунда Google Code Jam 2009, а пул задач обычно держится в относительном секрете, и задачи, получившие определённую популярность или будучи замеченными на публичных ресурсах, из пула удаляются. Задачи про муравьёв или шапки и вовсе не задаются уже очень давно.

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

              Сами же по себе задачи мне показались довольно любопытными.
              0

              Муравьи.
              75% шанс столкновения, т.к.только в 2 случаях из 8 все муравьи начинают двигаться в одну и ту же сторону.


              Шляпы
              Игроки дают ответ в зависимости от цветов шляп игроков, которых они видят перед собой. Если перед игроком дающим ответ, двое других с разными шляпами, он пасует, поскольку шанс угадать всего 50% и это покрывает большую часть из возможных позиций. Если отвечающий видит перед собой игроков с 2-мя одинаковыми шляпами синими или красными, то он называет противоположный цвет. Поскольку для каждого цвета возможны всего 3 подобные позиции, шанс на выигрыш уже 66.67%.

                0
                Давайте посмотрим возможные комбинации и ответы игроков по вашей системе"
                Комбинации
                K-K-K => С-С-С, проигрыш
                K-K-C => X-X-C, выигрыш
                K-C-K => X-C-X, выигрыш
                K-C-C => К-X-X, выигрыш
                C-K-K => С-X-X, выигрыш
                C-K-C => X-К-X, выигрыш
                C-C-K => X-X-K, выигрыш
                C-C-C => K-K-K, проигрыш

                Вероятность выпадения каждой комбинации одна и та же, выигрыш идёт в 6 случаях из 8, то есть его вероятность 75%.
                  0

                  Да, я уже понял, что ошибся, не все комбинации взял в учёт :)

                0
                1 вопрос муравьи — 75% вероятность столкновения.
                2 вопрос шляпа — тактика на 100% — заранее договариваются: кто видит одинаковые шляпы — отвечает, кто разные — пасует. Получается кто видит синие, на нем — красная, кто видит красные — на нем синяя. Кто видит красную и синюю — на нем или красная или синяя — надо пасовать)
                  0

                  Учитывай, что если ты видишь 2 одинаковые Шляпы, на тебе может быть так же шляпа этого цвета с вероятностью 33.3%

                    0
                    Там же в вопросе условие — «правильная монета». Значит из 3-х раз не может выпасть 3 в пользу одного и того же цвета.
                      0

                      Правильная момента подразумевает её верную физическую форму и прочие данные, то есть шанс выпадения того или иного результата ровно 1/2. Причем тут количество этих самых результатов?

                        0
                        Вот, вот — 1/2, а не 1/3 :)
                          0
                          1/2 это значит, если первая — синяя, то вторая — красная, а третья — или синяя или красная!
                            0

                            Точняк!

                      0
                      Тактика на 75%. Обратите внимание что ответы скрываются пока не ответили все игроки. То есть стратегия не сработает если были все шляпы одинакового цвета или в двух случаях из восьми.
                        0
                        все шляпы одинакового цвета быть не могут, потому что вероятность правильной монеты 1 к 2, в не 3 к 3. И 8 случаев быть не может, потому что игроков трое )))
                          0
                          Восемь это два в степени три (потому что игроков трое).
                          Почему все шляпы не могут быть одинакового цвета?
                          Давайте начнем так
                          Если один игрок то вероятностью 1 у него шляпа одного цвета.
                          Если игрока два то будет четыре варианта цветов равновероятных из них благоприятных два. То есть с вероятностью 0.5 на игроках будут шляпы одинакового цвета, потому что монета правильная. В этом правильная монета отличается от правильного бутерброда для которого вероятность 1.
                          Если игроков три то вариантов равновероятных будет 8 из них неблагоприятных по прежднему два (все синие все красные).

                            0
                            правильная монета — которая выпадает в четных случаях одинаковое количество раз на обе стороны, т.е. если бросить 2 раза, будет 1 раз синяя, другой — красная. Или наоборот. А третий раз — может синяя, а может красная.Значит 3 раза 1 цвет не может выпасть ))
                              +2
                              Давайте уйдем от тонкостей перевода и скажем термин как в условии fair coin.
                              Это монета которая в одном независимом испытании даст равную вероятность событий и все. Никакой мистики, никакой способности предугадывать последующие события и количество подбрасываний, никакой памяти монета не имеет. Каждое из подбрасываний является независимым и не исключает ни одного из событий.
                                0
                                Давайте уйдем.Но в вопросе слова «правильна монета» — это ссылка, где разъясняется, что это значит. И там другая интерпретация, чем у Вас.
                                  +2
                                  en.wikipedia.org/wiki/Fair_coin
                                  In probability theory and statistics, a sequence of independent Bernoulli trials with probability 1/2 of success on each trial is metaphorically called a fair coin.
                                  Сказано, что в каждом испытании вероятность успеха равняется 1/2. Где здесь вы увидели одинаковое количество выпадений?
                                    0
                                    Там написано то же что и я Вам сказал выше: идеальная монета при бросании имеет равную вероятность выпадания орла или решки 0,5+0,5. В отличии от реальной монеты результат бросания который зависит от ее реальных параметров и может быть например 0,4 + 0,6.

                                    При двух подряд испытаниях не гарантируется выпадание с вероятностью 100% разных результатов.

                                      0
                                      Возможно Вы и правы, а может — я. Посмотрим ответы через неделю.
                                        0
                                        Правильная монета — монета, у которой предел отношения количества выпавших орлов на количество бросков в бесконечности равен 1/2
                                          +1
                                          Хорошо. Убедили.Тактика на 75%.
                                  +1
                                  Правильная монета может выпасть одной стороной хоть сто раз подряд, но вероятность такого события крайне мала — только и всего. Можешь построить цепь Маркова.
                                  0
                                  Про правильный бутерброд — это точно!!! )))
                            0
                            Муравьи

                            50% — или встретятся или не встретятся

                              0
                              Хотелось бы узнать ваше обоснование
                                0
                                Обоснованием является рофл)
                              0
                              1. 0.75
                              2. одинаковые шляпы отвечает иное, остальные пас
                              3.…
                              4. находим первый F, для каждого способа превратить его в T (что может захватить и следующий F, в том числе), рекурсивно делаем поиск вариантов по следующему незахваченному F.
                                0
                                Последняя задача тоже проста — срезаем по одной букве все слова, заполняя массив с алфавитом в указанном порядке. Повторять до тех пор, пока слов не останется. Порядок букв в алфавите не меняется, новые буквы вставляются в соответствующие места.
                                  0
                                  Эта задача может не иметь однозначного решения. Например, по словарю 'аб', 'в' невозможно судить о взаимном порядке букв 'б' и 'в'.
                                    0
                                    Ага, поспешил
                              • UFO just landed and posted this here
                                  0
                                  На этой неделе я пас.
                                    0
                                    Задача 3
                                    Можно решить через матрицу предшествия. Заводим словарь предшественников для каждой буквы. Берём слова, начиная со второго, находим совпадающие начала в предыдущих словах и по первым несовпадающим буквам добавляем в словарь для буквы текущего слова букву из предшествующего.
                                    Пройдя по всем словам ищем буквы, у которых нет предшественников (пустые словари), выводим их в произвольном порядке. Удаляем эти буквы из всех словарей предшествия и из общего списка. Повторяем, пока в списке есть буквы.
                                    {«baa», «abcd», «abca», «cab», «cad»}
                                    'b' => {}
                                    'a' => {'b', 'd'}
                                    'c' => {'b', 'a'}
                                    'd' => {'b'}
                                    Ответ: {'b', 'd', 'a', 'c'}

                                      0
                                      Задача 1. — там по примерам почти видно.
                                      до семи символов выигрывают просто А
                                      потом после трёх А идёт комбинация ctrl+a, ctrl+c, ctrl+v, ctrl+v, пока эти 4 символа влезут в остаток, или же в остаток влезает просто ctrl+a, ctrl+c, ctrl+v иначе остаток заполняется несколькими ctrl+v

                                      Задача 3. — я бы просто конструировал дерево поиска, и в него кидал бы буквы из расчёта между какими буквами новую вставлять.

                                      Задача 2. — бессмысленный вырвиглаз, решаемый перебором
                                        +1
                                        По первой задаче пример решение кажется неверный для 11.
                                        Заметим что для 6 есть два равнозначны варианта аааааа и ааа сa cc cv
                                        Для 11 aaa ca cc cv ca cc cv cv cv то есть 36 не 27
                                        То есть алгоритм такой с кратными 3 действуем тройками ааа са сс cv ca cc cv
                                        Если некратно то заполняем последние один или два нажатия cc
                                          0
                                          Для Вашей последовательности ответ будет 24 а не 36
                                            0
                                            Да действительно ошибся
                                          +1
                                          1
                                          1/4: выкидываем первого муравья — от его решения ничего не зависит, в силу симметрии задачи. Куда бы он не двинулся, смотрим на муравья, в угол которого он двинулся. Он может пойти навстречу, и тогда точно столкнется, значит -50%. Если же он всё-таки пойдёт в другую сторону, то третий муравей также может пойти ему на встречу с вероятностью 50%, а 50% от 100%-%50 — это -25%. Значит ответ 100%-50%-25% = 25%

                                          2
                                          Шляпы не так просты как кажутся. Раз уж они заинтересовны в кооперации, то наверное стоит сообщать друг-другу инфу фактом написания, или не написания какого-либо варианта. Пускай есть один Избранный, который либо сразу же пишет пас, если видит одинаковые шляпы, либо пишет тот же пас, но после того как другие напишут свой цвет. Двое других всегда ответят правильно. Если же игра каким-то образом запрещает такие стратегии (хотя в условии ничего не сказано об этом) то они должны исходить только из того, какие шапки видят. Тут больше 75% они не выжмут, как мне кажется. Пример такой стратегии: видишь одинаковые — пиши противоположный цвет, видишь разные — пиши пас.

                                          Only users with full accounts can post comments. Log in, please.