Плавание, башня и тролли — 3 задачки для разминки мозга

Question 1

Оригинал задачи на английском языке

Answer

A sailboat wents 1 kilometer in 2 minutes with the wind and returned in 3 minutes against the wind. How fast could the boat sail this distance if there was no wind?

Question 2

Решение задачи на русском языке

Answer

Большинство из нас могли бы рассуждать так – парусник проходит по ветру дистанцию за 2 минуты и за 3 минуты против ветра, значит, скорость ветра можно отбросить, тогда средняя скорость парусника должна быть 2 км за 2+3 минут, т.е. ⅖ км/мин. Далее мы обнаружим, что этот ответ не верен – ведь ветер помогал паруснику всего лишь 2 минуты, а препятствовал — 3 минуты.

Если лодка проплыла км за 2 минуты при попутном ветре, очевидно, что за три минуты лодка бы проплыла 1.5 км и 1 км за 3 минуты обратно.
Поэтому в расчет скорость нужно брать 2.5 км за 6 минут, поскольку в этом случае ветер и помогал и препятствовал лодке одинаковое время, следовательно скорость лодки в штиль будет (2.5)/6 = 5/12 км/мин.

Question 3

Решение задачи на английском языке

Answer

Most of us will proceed like that if a boat goes a distance in 2 minutes with the wind, and returns against the wind in 3 minutes, that 2 and 3 equal 5, should give a correct average, so that time taken should be two and half minutes. We find this answer to be incorrect if we look further, because the wind has helped him for only 2 minutes, while it has worked adversely for 3 minutes.

If boat could ride a km in 2 minutes with the wind, it is clear that it could go a 1.5 km in 3 minutes, and 1 km in 3 minutes against the wind.

Therefore 2.5 kms in 6 minutes gives his actual speed, because the wind helped the boat just as much as has retarded it, so his actual speed for a single kilometer without any wind would be (2.5)/6 = 5/12 km/min.

Question 4

Оригинал задачи на английском языке

Answer

A set of n types of rectangular 3-dimensional boxes is given. The ith box has height hi, width wi and depth di (all real numbers). You need to create a tower of boxes which is as tall as possible, but you can only put a box on top of another box if the dimensions of the 2-D base of the upper box are each strictly smaller than those of the 2-D base of the lower box. You can rotate a box so that any side functions as its base. You can also use multiple instances of the same type of box.

Examples:

Input : { {4, 6, 7}, {1, 2, 3}, {4, 5, 6}, {10, 12, 32} }

Output: The maximum possible height of tower is 60.

Question 5

Решение задачи на русском языке

Answer

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

Превращается в:

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

Адаптированный рекуррент: D [i] = максимальная высота, которую мы можем получить, если последняя башня должна быть i.

D [1] = h (1);

D [i] = h (i) + max (D [j] | j < i, мы можем положить блок i сверху блока j)

Ответ — максимальный элемент D.

Question 6

Решение задачи на английском языке

Answer

You can solve this using the dynamic programming longest increasing subsequence algorithm. Accounting for the rotations is easy enough: for every box all you have to check is what happens if you use its height as the length of the base and its width as the height and what happens if you use it in the natural way. For example:

Becomes something like:

So for each block you actually have 3 blocks representing its possible rotations. Adjust your blocks array according to this, then sort by decreasing base area and just apply the DP LIS algorithm to the get the maximum height.

The adapted recurrence is: D[i] = maximum height we can obtain if the last tower must be i.

D[1] = h(1);

D[i] = h(i) + max(D[j] | j < i, we can put block i on top of block j)

Answer is the max element of D.

Question 7

Answer

			#include<stdio.h>
#include<stdlib.h>
 
/* Сущность - ящик*/
struct Box
{
  // h --> высота, w --> ширина, d --> длина
  int h, w, d;  
};
 
// функция - выбор минимального из двух int
int min (int x, int y)
{ return (x < y)? x : y; }
 
// функция - выбор максимального из двух int
int max (int x, int y)
{ return (x > y)? x : y; }
 
/* функция для сортировки оснований ящиков
int compare (const void *a, const void * b)
{
    return ( (*(Box *)b).d * (*(Box *)b).w ) -
           ( (*(Box *)a).d * (*(Box *)a).w );
}
 
/* Вычисляет максимальную высоту башни из ящиков*/
int maxStackHeight( Box arr[], int n )
{
   /* Создаем массив всех возможных оснований ящиков с учетом поворотов
Например, {1, 2, 3} даст нам  {{1, 2, 3}, {2, 1, 3}, {3, 1, 2}} */
   Box rot[3*n];
   int index = 0;
   for (int i = 0; i < n; i++)
   {
      // Оригинал
      rot[index].h = arr[i].h;
      rot[index].d = max(arr[i].d, arr[i].w);
      rot[index].w = min(arr[i].d, arr[i].w);
      index++;
 
      // Первый поворот
      rot[index].h = arr[i].w;
      rot[index].d = max(arr[i].h, arr[i].d);
      rot[index].w = min(arr[i].h, arr[i].d);
      index++;
 
      // Второй поворот
      rot[index].h = arr[i].d;
      rot[index].d = max(arr[i].h, arr[i].w);
      rot[index].w = min(arr[i].h, arr[i].w);
      index++;
   }
 
   // Количество ящиков теперь 3n
   n = 3*n;
 
   /* Сортируем получившийся массив */
   qsort (rot, n, sizeof(rot[0]), compare);
 
   /* Инициализируем msh
      msh[i] --> Максимальная возможная высота башни с ящиком i на вершине*/
   int msh[n];
   for (int i = 0; i < n; i++ )
      msh[i] = rot[i].h;
 
   for (int i = 1; i < n; i++ )
      for (int j = 0; j < i; j++ )
         if ( rot[i].w < rot[j].w &&
              rot[i].d < rot[j].d &&
              msh[i] < msh[j] + rot[i].h
            )
         {
              msh[i] = msh[j] + rot[i].h;
         }
 
 
   /* Берем максимальное из возможных значений msh */
   int max = -1;
   for ( int i = 0; i < n; i++ )
      if ( max < msh[i] )
         max = msh[i];
 
   return max;
}
 

int main()
{
  Box arr[] = { {4, 6, 7}, {1, 2, 3}, {4, 5, 6}, {10, 12, 32} };
  int n = sizeof(arr)/sizeof(arr[0]);
 
  printf("The maximum possible height of stack is %d\n",
         maxStackHeight (arr, n) );
 
  return 0;
}

Answer

You returning from long journey and you are on your final way to your home placing at the end of the valley. You have some money with you that you brought from the journey. Between you and your house, you have to cross 5 bridges, and as it goes in the land of make believe, there is a troll under every bridge! Each troll, quite rightly, insists that you pay a troll toll. Before you can cross their bridge, you have to give them half of the kronas you are carrying, but as they are kind trolls, they each give you back one krona.

How many kronas do you have to take with you to make sure that you arrive at your home with exactly 2 kronas? You should avoid unnecessary money waste.