Написать пост

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

Аватар Андрей Приб

Порой нужно отвлечься от программирования и заняться чем-нибудь ещё. Например, разминкой мозга с помощью решения задачек.

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

Плавание против ветра

Парусник проходит 1 километр за 2 минуты с попутным ветром и возвращается за 3 минуты против встречного. Насколько быстро будет плыть лодка эту дистанцию в штиль?

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

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?

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

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

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

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

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.

Башня из коробок

Дан набор n типов прямоугольных трехмерных ящиков. У i-того ящика высота hi, ширина wi и длина di (действительные числа). Вам необходимо построить башню максимальной высоты из ящиков, с учётом того, что ящик можно поставить на другой ящик только в том случае, если каждое из двух измерений основания верхнего ящика меньше соответствующих измерений нижнего ящика. Вы можете поворачивать ящики, так что любая сторона может выступать основанием.Также разрешено использовать любое количество ящиков одного типа.

Пример:

Вход: { {4, 6, 7}, {1, 2, 3}, {4, 5, 6}, {10, 12, 32} }

Выход: Максимальная высота башни — 60.

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

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.

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

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

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

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

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

D [1] = h (1);

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

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

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

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.

Решение на языке С++
			#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;
}
		

Мосты и тролли

Вы возвращаетесь из долгого путешествия и сейчас на завершающем этапе – на пути к дому, расположенному в конце долины. У вас с собой некоторое количество денег, которые вы привезли из путешествия. Между вами и вашим домом вам придётся пересечь 5 мостов, и, поскольку дело обстоит в выдуманной стране, под каждым мостом живёт тролль! Каждый тролль справедливо будет требовать плату за проход. Прежде чем пересечь мост, вам придётся отдать половину всех наличных крон, но поскольку тролли добрые — каждый даст сдачей одну крону.

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

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

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.

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

2 кроны.

На каждом мосту вы будете отдавать половину всех денег, и получать одну крону обратно. Что позволит оставаться с 2-мя кронами после каждого моста.

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

2 kronas.

At each bridge you are required to give half of your money, and you receive one krona back. Which leaves you with 2 kronas after every bridge.

Следите за новыми постами
Следите за новыми постами по любимым темам
8К открытий8К показов