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

    Мы подготовили для Вас новый, 23-й, выпуск ITренировки.

    КДПВВ подборку вошли вопросы, задаваемые претендентам на должность инженера-разработчика на собеседованиях в Intel. География вопросов (как выяснили в прошлом выпуске, это может накладывать отпечаток на содержание вопросов) — расширена (Корея, США). Вопросы традиционно различного уровня сложности — как простые, так и не очень

    Вопросы


    1. Water in bathroom
      I renovated my bathroom and got myself a new bath tub along with new accessories. I have two taps now — hot one and cold one. The hot tap fills the bath tub faster i.e. in fifteen minutes while it takes eighteen minutes for the cold tap to fill the bath tub.

      The drain hole can drain the entirely filled bathtub in ten minutes when the taps are not running.

      If I leave both the taps on with the drain plug left out, how long will it take the bath to fill?

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

      Если открыть слив — ванна опустеет через 10 минут при закрытых кранах.

      Если я оставлю оба крана открытыми, и не заткну слив — сколько потребуется времени для наполнения ванны?

    2. Mark and the traffic
      Mark went to visit his mother last weekend which is about 250 miles away from his home. He started 7am in the sunny morning of Saturday and found out that the road was too crowded. There were times that he has completely stationary. He reached his mother's house after lunch.

      He had to return on Sunday and he had to travel through the same route again. He left the place at 7 am and found no traffic at all and reached home before lunch time enjoying a smooth drive.

      What is the probability that he was at the same point at the same time on both the days he traveled?

      Перевод
      Марк на выходные поехал навестить свою мать, которая живет за 250 миль от его дома. Он выехал в 7 утра и обнаружил, что дороги переполнены. Временами он даже стоял и прибыл к матери после ланча (прим. в 13:00).
      Марку нужно было вернуться в воскресенье тем же маршрутом. Он выехал в 7 утра, отметив попутно, что на дороге нет машин, и приехал домой перед ланчем (прим. в 12:00), наслаждаясь неспешной ездой.

      Какова вероятность, что Марк мог оказаться в одной и той же точке в одинаковое время на пути туда и обратно?


    Задачи


    1. Print numbers with mobile pad
      Given the mobile numeric keypad. You can only press buttons that are up, left, right or down to the current button. You are not allowed to press bottom row corner buttons (i.e. * and # ).
         [ 1 ] [ 2 ] [ 3 ]
         [ 4 ] [ 5 ] [ 6 ]
         [ 7 ] [ 8 ] [ 9 ]
         [ * ] [ 0 ] [ # ]
      

      Given a number N, write a program to find out the number of possible numbers of given length.

      Examples:
      For N=1, number of possible numbers would be 10 (0, 1, 2, 3, …., 9)
      For N=2, number of possible numbers would be 36
      Possible numbers: 00,08 11,12,14 22,21,23,25 and so on.

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

         [ 1 ] [ 2 ] [ 3 ]
         [ 4 ] [ 5 ] [ 6 ]
         [ 7 ] [ 8 ] [ 9 ]
         [ * ] [ 0 ] [ # ]
      

      Дано число N, напишите программу, вычисляющую количество допустимых чисел заданной длины.

      Примеры:
      Для N=1, количество чисел — 10 (0, 1, 2, 3, …., 9)
      Для N=2, количество чисел — 36 (00,08 11,12,14 22,21,23,25 и т.д.)

    2. Clone binary tree
      Given a Binary Tree where every node has following structure.
      struct node {
      int key;
      struct node *left,*right,*random;
      }

      The random pointer points to any random node of the binary tree and can even point to NULL. Create a program to clone the given binary tree.

      Перевод
      Дано — бинарное дерево с узлами следующей структуры:
      struct node {
      int key;
      struct node *left,*right,*random;
      }


      Указатели *random ссылаются на случайный узел дерева, могут содержать NULL. Создайте программу для клонирования этого бинарного дерева.

    3. Book readers
      A person is determined to finish the book in ‘k’ days but he never wants to stop a chapter in between. Find the optimal assignment of chapters, such that the person doesn’t read too many extra/less pages overall.

      Example 1:
      Input: Number of Days to Finish book = 2
      Number of pages in chapters = {10, 5, 5}
      Output: Day 1: Chapter 1
      Day 2: Chapters 2 and 3

      Example 2:
      Input: Number of Days to Finish book = 3
      Number of pages in chapters = {8, 5, 6, 12}
      Output: Day 1: Chapter 1
      Day 2: Chapters 2 and 3
      Day 3: Chapter 4


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

      Пример 1:
      Вход: Дней для прочтения книги = 2
      Количество страниц в главах = {10, 5, 5}
      Выход: День 1: Глава 1
      День 2: Глава 2, Глава 3

      Пример 2:
      Вход: Дней для прочтения книги = 3
      Количество страниц в главах = {8, 5, 6, 12}
      Выход: День 1: Глава 1
      День 2: Глава 2, Глава 3
      День 3: Глава 4



    Решения


    1. Вопрос 1
      jmdorian верно рассчитал ответ — 45 минут.

    2. Вопрос 2
      100 %. В этом комментарии ответили почему.

    3. Задача 1
      Исходный вариант решения:
      #include <stdio.h>
       
      // Return count of all possible numbers of length n
      // in a given numeric keyboard
      int getCount(char keypad[][3], int n)
      {
          if(keypad == NULL || n <= 0)
              return 0;
          if(n == 1)
              return 10;
       
          // left, up, right, down move from current location
          int row[] = {0, 0, -1, 0, 1};
          int col[] = {0, -1, 0, 1, 0};
       
          // taking n+1 for simplicity - count[i][j] will store
          // number count starting with digit i and length j
          int count[10][n+1];
          int i=0, j=0, k=0, move=0, ro=0, co=0, num = 0;
          int nextNum=0, totalCount = 0;
       
          // count numbers starting with digit i and of lengths 0 and 1
          for (i=0; i<=9; i++)
          {
              count[i][0] = 0;
              count[i][1] = 1;
          }
       
          // Bottom up - Get number count of length 2, 3, 4, ... , n
          for (k=2; k<=n; k++)
          {
              for (i=0; i<4; i++)  // Loop on keypad row
              {
                  for (j=0; j<3; j++)   // Loop on keypad column
                  {
                      // Process for 0 to 9 digits
                      if (keypad[i][j] != '*' && keypad[i][j] != '#')
                      {
                          // Here we are counting the numbers starting with
                          // digit keypad[i][j] and of length k keypad[i][j]
                          // will become 1st digit, and we need to look for
                          // (k-1) more digits
                          num = keypad[i][j] - '0';
                          count[num][k] = 0;
       
                          // move left, up, right, down from current location
                          // and if new location is valid, then get number
                          // count of length (k-1) from that new digit and
                          // add in count we found so far
                          for (move=0; move<5; move++)
                          {
                              ro = i + row[move];
                              co = j + col[move];
                              if (ro >= 0 && ro <= 3 && co >=0 && co <= 2 &&
                                 keypad[ro][co] != '*' && keypad[ro][co] != '#')
                              {
                                  nextNum = keypad[ro][co] - '0';
                                  count[num][k] += count[nextNum][k-1];
                              }
                          }
                      }
                  }
              }
          }
       
          // Get count of all possible numbers of length "n" starting
          // with digit 0, 1, 2, ..., 9
          totalCount = 0;
          for (i=0; i<=9; i++)
              totalCount += count[i][n];
          return totalCount;
      }
       
      // Driver program to test above function
      int main(int argc, char *argv[])
      {
         char keypad[4][3] = {{'1','2','3'},
                              {'4','5','6'},
                              {'7','8','9'},
                              {'*','0','#'}};
         printf("Count for numbers of length %d: %dn", 1, getCount(keypad, 1));
         printf("Count for numbers of length %d: %dn", 2, getCount(keypad, 2));
         printf("Count for numbers of length %d: %dn", 3, getCount(keypad, 3));
         printf("Count for numbers of length %d: %dn", 4, getCount(keypad, 4));
         printf("Count for numbers of length %d: %dn", 5, getCount(keypad, 5));
       
         return 0;
      }


    4. Задача 2
      Вариант решения с хешированием:
      // A hashmap based C++ program to clone a binary tree with random pointers
      #include<iostream>
      #include<map>
      using namespace std;
       
      /* A binary tree node has data, pointer to left child, a pointer to right
         child and a pointer to random node*/
      struct Node
      {
          int key;
          struct Node* left, *right, *random;
      };
       
      /* Helper function that allocates a new Node with the
         given data and NULL left, right and random pointers. */
      Node* newNode(int key)
      {
          Node* temp = new Node;
          temp->key = key;
          temp->random = temp->right = temp->left = NULL;
          return (temp);
      }
       
      /* Given a binary tree, print its Nodes in inorder*/
      void printInorder(Node* node)
      {
          if (node == NULL)
              return;
       
          /* First recur on left sutree */
          printInorder(node->left);
       
          /* then print data of Node and its random */
          cout << "[" << node->key << " ";
          if (node->random == NULL)
              cout << "NULL], ";
          else
              cout << node->random->key << "], ";
       
          /* now recur on right subtree */
          printInorder(node->right);
      }
       
      // This function creates clone by copying key and left and right pointers
      // This function also stores mapping from given tree node to clone.
      Node* copyLeftRightNode(Node* treeNode, map<Node *, Node *> *mymap)
      {
          if (treeNode == NULL)
              return NULL;
          Node* cloneNode = newNode(treeNode->key);
          (*mymap)[treeNode] = cloneNode;
          cloneNode->left  = copyLeftRightNode(treeNode->left, mymap);
          cloneNode->right = copyLeftRightNode(treeNode->right, mymap);
          return cloneNode;
      }
       
      // This function copies random node by using the hashmap built by
      // copyLeftRightNode()
      void copyRandom(Node* treeNode,  Node* cloneNode, map<Node *, Node *> *mymap)
      {
          if (cloneNode == NULL)
              return;
          cloneNode->random =  (*mymap)[treeNode->random];
          copyRandom(treeNode->left, cloneNode->left, mymap);
          copyRandom(treeNode->right, cloneNode->right, mymap);
      }
       
      // This function makes the clone of given tree. It mainly uses
      // copyLeftRightNode() and copyRandom()
      Node* cloneTree(Node* tree)
      {
          if (tree == NULL)
              return NULL;
          map<Node *, Node *> *mymap = new  map<Node *, Node *>;
          Node* newTree = copyLeftRightNode(tree, mymap);
          copyRandom(tree, newTree, mymap);
          return newTree;
      }
       
      /* Driver program to test above functions*/
      int main()
      {
          //Test No 1
          Node *tree = newNode(1);
          tree->left = newNode(2);
          tree->right = newNode(3);
          tree->left->left = newNode(4);
          tree->left->right = newNode(5);
          tree->random = tree->left->right;
          tree->left->left->random = tree;
          tree->left->right->random = tree->right;
       
          //  Test No 2
          //    tree = NULL;
       
          //  Test No 3
          //    tree = newNode(1);
       
          //  Test No 4
          /*    tree = newNode(1);
              tree->left = newNode(2);
              tree->right = newNode(3);
              tree->random = tree->right;
              tree->left->random = tree;
          */
       
          cout << "Inorder traversal of original binary tree is: \n";
          printInorder(tree);
       
          Node *clone = cloneTree(tree);
       
          cout << "\n\nInorder traversal of cloned binary tree is: \n";
          printInorder(clone);
       
          return 0;
      }


    5. Задача 3
      Вариант решения с направленным ацикличным графом:
      
      // C++ DFS solution to schedule chapters for reading in
      // given days
      # include <iostream>
      # include <cstdlib>
      # include <climits>
      # include <cmath>
      using namespace std;
       
      // Define total chapters in the book
      // Number of days user can spend on reading
      # define CHAPTERS 4
      # define DAYS 3
      # define NOLINK -1
       
      // Array to store the final balanced schedule
      int optimal_path[DAYS+1];
       
      // Graph - Node chapter+1 is the sink described in the
      //         above graph
      int DAG[CHAPTERS+1][CHAPTERS+1];
       
      // Updates the optimal assignment with current assignment
      void updateAssignment(int* path, int path_len);
       
      // A DFS based recursive function to store the optimal path
      // in path[] of size path_len.  The variable sum stores sum of
      // of all edges on current path.  k is number of days spent so
      // far.
      void assignChapters(int u, int* path, int path_len, int sum, int k)
      {
          static int min = INT_MAX;
       
          // Ignore the assignment which requires more than required days
          if (k < 0)
              return;
       
          // Current assignment of chapters to days
          path[path_len] = u;
          path_len++;
       
          // Update the optimal assignment if necessary
          if (k == 0 && u == CHAPTERS)
          {
              if (sum < min)
              {
                  updateAssignment(path, path_len);
                  min = sum;
              }
          }
       
          // DFS - Depth First Search for sink
          for (int v = u+1; v <= CHAPTERS; v++)
          {
              sum += DAG[u][v];
              assignChapters(v, path, path_len, sum, k-1);
              sum -= DAG[u][v];
          }
      }
       
      // This function finds and prints optimal read list.  It first creates a
      // graph, then calls assignChapters().
      void minAssignment(int pages[])
      {
          // 1) ............CONSTRUCT GRAPH.................
          // Partial sum array construction S[i] = total pages
          // till ith chapter
          int avg_pages = 0, sum = 0, S[CHAPTERS+1], path[DAYS+1];
          S[0] = 0;
       
          for (int i = 0; i < CHAPTERS; i++)
          {
              sum += pages[i];
              S[i+1] = sum;
          }
       
          // Average pages to be read in a day
          avg_pages = round(sum/DAYS);
       
          /* DAG construction vertices being chapter name &
           * Edge weight being |avg_pages - pages in a chapter|
           * Adjacency matrix representation  */
          for (int i = 0; i <= CHAPTERS; i++)
          {
              for (int j = 0; j <= CHAPTERS; j++)
              {
                  if (j <= i)
                      DAG[i][j] = NOLINK;
                  else
                  {
                      sum = abs(avg_pages - (S[j] - S[i]));
                      DAG[i][j] = sum;
                  }
              }
          }
       
          // 2) ............FIND OPTIMAL PATH................
          assignChapters(0, path, 0, 0, DAYS);
       
          // 3) ..PRINT OPTIMAL READ LIST USING OPTIMAL PATH....
          cout << "Optimal Chapter Assignment :" << endl;
          int ch;
          for (int i = 0; i < DAYS; i++)
          {
              ch = optimal_path[i];
              cout << "Day" << i+1 << ": " << ch << " ";
              ch++;
              while ( (i < DAYS-1 && ch < optimal_path[i+1]) ||
                      (i == DAYS-1 && ch <= CHAPTERS))
              {
                 cout <<  ch << " ";
                 ch++;
              }
              cout << endl;
          }
      }
       
      // This funtion updates optimal_path[]
      void updateAssignment(int* path, int path_len)
      {
          for (int i = 0; i < path_len; i++)
              optimal_path[i] = path[i] + 1;
      }
       
      // Driver program to test the schedule
      int main(void)
      {
          int pages[CHAPTERS] = {7, 5, 6, 12};
       
          // Get read list for given days
          minAssignment(pages);
       
          return 0;
      }
      


    Spice IT Recruitment 69,63
    ИТ специализированное кадровое агентство
    Поделиться публикацией
    Ой, у вас баннер убежал!

    Ну. И что?
    Реклама
    Комментарии 23
    • +3
      2
      100%. Хотя это и кажется на первый взгляд странным, но ответ становится очевидным, если представить, что два человека выехали в один день навстречу друг другу и ехали по одной дороге с разной скоростью. Они обязательно встретятся.
      • 0
        Тут же вроде вопрос в том, когда встретятся. В задаче условие «at the same time on both the days»
        • +1

          Тут вопрос о вероятности, а не о времени.
          Время — любое в интервале 7-12 часов (ибо скорости не постоянные), а вероятность 100%

          • 0
            Не соглашусь. Понятно что вероятность встречи 100%, но в задаче не просто так расписаны все времена, плюс условие задачи вполне четко сформулировано: «в одной и той же точке в одинаковое время».
            • 0

              Именно что не просто так. А для того, чтобы народ повёлся, начал искать глубинный смысл и высчитывать вероятность по безумным формулам.
              Тогда как загадка — на смекалку.

      • +1
        1 вопрос
        45 минут.
        Примем объем ванной за N литров, и выразим скорости прибывания горячей как N/18, холодной как N/15, а убывания как N/10. Тогда итоговая скорость наполнения будет N/18 + N/15 — N/10 = 2N/90. Отсюда время наполнения N/ (2N/90) = 45 минут
        • +1
          Вопрос 1 - классическая задача о бассейне и трубах для 6 класса
          Первый кран заполняет ванну за 15 минут, значит за минуту он выдаёт 1/15 от объёма ванны. Второй кран — 1/18 от объёма, сток за минуту сливает 1/10 объёма.
          В сумме за минуту заполнится 1/15 +1/18 — 1/10 = 1/45, значит вся ванна заполнится за 45 минут.

          Вопрос 2
          Достаточно представить, что не один человек едет в разные дни, а два человека едут одновременно навстречу друг-другу. Очевидно, что в месте встречи они окажутся одновременно.

          В задаче 1 нестыковка — если мы можем нажать только кнопки выше, ниже, левее или правее текущей, то как получаются комбинации 00, 11, 22 и т.д.? Ведь сама текущая кнопка под это определение не подходит.
          • 0
            вопрос 1
            1/(1/15 + 1/18 - 1/10)
            = 1/(1/(3*5) + 1/(2*3*3) - 1/(2*5))
            = (2*3*3*5) / (2*3 + 5 - 3*3)
            = 90 / 2
            = 45
            • 0

              В задаче 2 непонятно — можно нажимать только кнопки в 1-окрестности от заданной?
              Т.е. если задана кнопка 0 и длина 3, то можно получать {'0','8'}*3?


              Если так, то задача тупая. Для каждой кнопки мы знаем основание степени:
              0 — 2
              1 — 3
              2 — 4
              3 — 2
              и т.д.
              И возвести это основание в показатель длины.


              Если же имеется в виду, что можно нажимать эту-и-соседние кнопки, то задача будет о количестве путей заданной длины в графе.
              В этом случае берём матрицу смежности и возводим в N-ную степень в кольце (макс,+)...

              • +1
                Задача 2 про дерево

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


                std::map<node*, node*> copies;
                node* clone(node* original) {
                  if (!original) return NULL;
                  node*& copy = copies[original];
                  if (copy) return copy;
                  copy = new node;
                  // принципиально, что мы сперва создаём и регистрируем копию в таблице,
                  // а уже потом рекурсивно спускаемся (возможно, попадая на самих себя!)
                  node->key = original->key;
                  node->left = clone(original->left);
                  node->right = clone(original->right);
                  node->random = clone(original->random);
                  return node;
                }

                Если жалко, то придётся изгаляться.


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


                void duplicate(node* o) {
                  if (!o) return;
                  node* c = new node(o);
                  o->random = c;
                  duplicate(c->left);
                  duplicate(c->right);
                }
                
                void separate(node* o) {
                  node* c = o->random;
                  c->left = c->left ? c->left->random : NULL;
                  c->right = c->right ? c->right->random : NULL;
                  node* r = c->random;
                  c->random = c->random ? c->random->random : NULL;
                  o->random = r;
                  separate(o->left);
                  separate(o->right);
                }
                
                node* copy(node* root) {
                  if (!root) return NULL;
                  duplicate(root);
                  node* c = root->random;
                  separate(root);
                  return c;
                }

                Вроде бы, не налажал.

                • 0
                  В задаче 1 непонятно — 2 крана на смесителе или на отдельных трубах? Потому как если на смесителе, то подобные расчеты будут не верны. Также не понятно и то, происходит ли спад давления в системе если открыты оба крана?
                  • +1
                    Задача 3:
                    Вычисляем среднее количество страниц которые нужно читать каждый день. Читаем главу, смотрим на количество страниц следующей главы, если прочитав следующую главу читатель отклонится от среднего количества страниц к прочтению больше чем в данный момент, читатель останавливается. В противном случае — продолжает читать.

                    Пример 2: {8, 5, 6, 12} — среднее количество страниц 10,(3)
                    Д1 — Читаем 8 страниц (отклонение 2,(3)), если прочитаем ещё 5 (8 + 5 = 13) получим отклонение 2,(6), что больше, значит нужно остановится.
                    Д2 — Читаем 5 страниц (отклонение 5,(3)), если прочитаем ещё 6 получим отклонение 0,(6), значит продолжаем, если прочитаем ещё 12 получим отклонение больше, значит нужно остановится.
                    Д3 — Читаем оставшееся.

                    Пример 3: {8, 5, 10, 12} — среднее количество страниц 11,(6)
                    Д1 — Читаем 8 страниц (отклонение 3,(6)), если прочитаем ещё 5 (8 + 5 = 13) получим отклонение 1,(4), значит читаем дальше, если прочитаем ещё 10 страниц получим большее отклонение значит останавливаемся.

                    • 0

                      Метод не сработает при {20,1,1,1} и k=3. Все оставшиеся страницы будут прочитаны в 1 день. Нужно наверное корректировать среднее на оставшиеся дни.

                      • +1
                        При {1,1,1,30}, k = 3 и корректировка среднего не поможет, три главы будут прочитаны в первый день, последняя во второй.
                        • 0
                          А это и не нужно. «Finish the book in 'k' days» значит, что через «k» дней книга должна быть прочитана, но отнюдь не значит, что она не может быть прочитана быстрее. Поэтому, если параметр оптимизации — это уменьшение дисперсии количества страниц в день, правильный ответ везде будет «глотать книгу целиком». Вот если там появится параметр «минимизировать ещё и среднее количество страниц в день», тут возможны варианты. И если честно, для {20,1,1,1} правильный ответ все-таки прочесть за день, негоже три страницы оставлять на второй (да и просто дисперсия великовата).
                          • 0
                            Но по условию задачи «A person is determined to finish the book in ‘k’ days». Не "`k` or less". То есть суть именно в том, чтобы правильно разбить массив на k частей, как я понял.
                      • 0
                        Задача 2 — ключи уникальные или нет? А то корректно не выйдет склонировать, если за random разных нод спряталось два разных идентичных поддерева. Хотя если сравнивать указатели, то вариант таблицы «оригинал — копия» как у nickolaym выше, пройдет.
                        • 0
                          Ключи могут быть неуникальными.
                        • 0

                          К задаче 3.
                          Как точно сформулировать критерий оптимальности? Чтобы минимизировать максимальное отклонение от среднего количества страниц, или чтобы минимизировать среднеквадратичное отклонение, к примеру?
                          Кажется, можно придумать набор данных, при котором результаты по этим критериям будут различаться.

                          • 0
                            Думаю, нужно минимизировать максимальное отклонение.
                            • +1

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


                              Концепция решения задачи 3

                              Это задача на динамическое программирование!


                              Пусть у нас N глав по p0, p1, p2, ..., p[N-1] страниц, итого P страниц, и K дней.
                              (Если N <= K, то решение тривиально)


                              В среднем выходит M = P/K страниц в день — это базовая линия.


                              В первый день прочитали 0..N глав (на самом деле, 1..N-K+1 — если требовать не менее 1 главы в день).
                              Это s[k] = 0 + p0 + p1 +… + p[k-1] страниц в сумме.
                              Что дало нам отклонения первого дня d0… dN.
                              Для макса это абсолютное отклонение dk=|M-sk|, для скво — квадрат отклонения dk=(M-sk)^2 — это член суммы для дисперсии.


                              Во второй день ещё прочитали — от первого дня до 0..N главы включительно.
                              s'[i,k] = p[i] +… + p[k-1] — прочитано во второй день
                              d'[i,k] = delta(M, s'[i,k]) — отклонение второго дня.
                              d"[i,k] = union(d[i], d'[i,k]) — отклонение за два дня
                              Для макса — это максимум, для скво — сумма (мы потом должны поделить и искоренить, но не будем торопиться).
                              Итого за два дня мы получаем новые значения d[k] = min(i) d"[i,k] — наилучшие результаты для каждого количества глав.


                              Третий день — аналогично второму.
                              И т.д.


                              Чуть позже напишу на питончике

                              • 0
                                задача 3 - решение на питоне
                                import itertools
                                
                                # выбор целевой функции - и соответствующих операций.
                                # delta - считает отклонение
                                # union - складывает отклонения
                                
                                if 1:
                                    # максимальное отклонение
                                    def delta(M, s):
                                        return abs(M-s)
                                    def union(s1, s2):
                                        return max(s1, s2)
                                else:
                                    # дисперсия (и, соответственно, скво - но нам проще считать дисперсию)
                                    def delta(M, s):
                                        return (M-s)**2
                                    def union(s1, s2):
                                        return (s1 + s2)
                                
                                def paginate(p, K, verbose=True):
                                    '''
                                    разбивает главы на дни
                                    p - количество страниц в каждой главе
                                    K - количество дней
                                    verbose - отладочный вывод
                                    '''
                                    assert p
                                    assert K
                                
                                    # посчитаем бегущие суммы, чтобы быстро находить сумму страниц меж глав i:j
                                    # с этого момента нам страницы не нужны (и это мог быть итератор, а не список)
                                    s = [0] + list(itertools.accumulate(p))
                                    # sum(p[:j]) = s[j]
                                    # sum(p[i:j]) = s[j]-s[i]
                                    def sij(i, j):
                                        return s[j] - s[i]
                                
                                    assert len(s) > K
                                
                                    # количества прочтённых глав, от 0 до N+1
                                    range_N1 = range(len(s))
                                
                                    # среднее количество страниц в день
                                    M = s[-1] / K
                                
                                    # отклонение за один день, меж глав i:j
                                    def dij_daily(i,j):
                                        return delta(M, sij(i,j))
                                
                                    # отклонения предыдущего дня (инициализировано первым днём)
                                    d_prev = [dij_daily(0,j) for j in range_N1]
                                    # наилучшие решения предыдущего дня
                                    # списки количества страниц за каждый день
                                    # (инициализировано первым днём - прочли всё по 0:j'ю главу)
                                    h_prev = [[sij(0,j)] for j in range_N1]
                                
                                    # итоговое отклонение (предыдущий + текущий дни)
                                    def dij_total(i,j):
                                        return union(d_prev[i], dij_daily(i,j))
                                
                                    if verbose:
                                        print('day 0:')
                                        for j in range_N1:
                                            print(f' {j} : {p[0:j]}={h_prev[j]} @ {d_prev[j]}')
                                        print()
                                
                                    # для следующих дней - динамическое программирование
                                    for day in range(1, K):
                                        if verbose:
                                            print(f'day {day}:')
                                
                                        # новые результаты будут здесь
                                        d_next = [None for _ in s]
                                        h_next = [None for _ in s]
                                
                                        # для каждого итогового количества глав, прочтённых к этому дню
                                        for j in range_N1:
                                
                                            # находим лучшее предыдущее количество глав
                                            i = min(range(j), default=0, key=lambda i:dij_total(i,j))
                                
                                            # компоненты наших формул (для отладочного вывода)
                                
                                            # суммы страниц предыдущего дня, этот день, к концу этого дня
                                            hi, hij = h_prev[i], sij(i,j)
                                            hj = hi + [hij]
                                
                                            # отклонение предыдущего дня, этого дня, к концу этого дня
                                            di, dij, dj = d_prev[i], dij_daily(i,j), dij_total(i,j)
                                
                                            # записываем результат.
                                            d_next[j] = dj
                                            h_next[j] = hj
                                
                                            if verbose:
                                                print(f' {i}->{j} : {hi} @ {di:.2f}  + {p[i:j]}={hij} @ {dij:.2f}  =>  {hj} @ {dj:.2f}')
                                
                                        if verbose:
                                            print()
                                
                                        # был день текущий, стал предыдущий
                                        d_prev, h_prev = d_next, h_next
                                
                                    # возвращаем последний список страниц - охватывающий все главы.
                                    return h_prev[-1]
                          • 0
                            задачки типа первой и второй решал с ребенком в 6м или 7м классе…

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

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