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

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

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

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

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

Отмеряем 1-40 литров молока

У вас есть бидон, полный молока на продажу, и 4 банки. Какого объема должны быть эти банки, чтобы вы смогли отмерить любой объем молока от 1 до 40 литров, при том что каждая банка может быть использована только 1 раз?

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

There is a drum full of milk, people come for buying milk in the range of 1-40 litres. You can have only 4 cans to draw milk out of drum. What should be the measurement of these four cans so that you can measure any amount of milk in the range of 1-40 litres.

Note that the cans cannot be used more than once.

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

Рассудим логически:

  • Банки 1 и 3 л могут дать любой объем от 1 до 4 л (1, 3 – 1, 3, 3 + 1).
  • Если добавить 9 л, получится отмерить любой объем от 5 до 13 (9 – (от 1 до 4), 9 + (от 1 до 4)).
  • Если добавить 27 — можно будет отмерить любой объем от 14 до 40 л (27 – (от 1 до 13), 27 + (от 1 до 13)).

Проверяем:

1 = 1
2 = 3 – 1
3 = 3
4 = 3 + 1
5 = 9 – 3 – 1
6 = 9 – 3
7 = 9 – 3 + 1
8 = 9 – 1
9 = 9
10 = 9 + 1
11 = 9 + 3 – 1
12 = 9 + 3
13 = 9 + 3 + 1
14 = 27 – 9 – 3 – 1
15 = 27 – 9 – 3
16 = 27 – 9 – 3 + 1
18 = 27 – 9 – 1
18 = 27 – 9
19 = 27 – 9 + 1
20 = 27 – 9 + 3 – 1
21 = 27 – 9 + 3
22 = 27 – 9 + 3 + 1
23 = 27 – 3 – 1
24 = 27 – 3
25 = 27 – 3 + 1
26 = 27 – 1
27 = 27
28 = 27 + 1
29 = 27 + 3 – 1
30 = 27 + 3
31 = 27 + 3 + 1
32 = 27 + 9 – 3 – 1
33 = 27 + 9 – 3
34 = 27 + 9 – 3 + 1
35 = 27 + 9 – 1
36 = 27 + 9
37 = 27 + 9 + 1
38 = 27 + 9 + 3 – 1
39 = 27 + 9 + 3
40 = 27 + 9 + 3 + 1

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

Logically:

  • 1,3 can get anything from 1 to 4 (1, 3-1, 3, 3+1).
  • Put in the 9 and you can get anything from 5 to 13 (9-(1 to 4), 9+(1 to 4)).
  • Put in the 27 and you can get anything from 14 to 40 (27 – (1 to 13), 27 + (1 to 13)).

Check it out:

1 = 1
2 = 3-1
3 = 3
4 = 3+1
5 = 9-3-1
6 = 9-3
7 = 9-3+1
8 = 9-1
9 = 9
10 = 9+1
11 = 9+3-1
12 = 9+3
13 = 9+3+1
14 = 27-9-3-1
15 = 27-9-3
16 = 27-9-3+1
18 = 27-9-1
18 = 27-9
19 = 27-9+1
20 = 27-9+3-1
21 = 27-9+3
22 = 27-9+3+1
23 = 27-3-1
24 = 27-3
25 = 27-3+1
26 = 27-1
27 = 27
28 = 27+1
29 = 27+3-1
30 = 27+3
31 = 27+3+1
32 = 27+9-3-1
33 = 27+9-3
34 = 27+9-3+1
35 = 27+9-1
36 = 27+9
37 = 27+9+1
38 = 27+9+3-1
39 = 27+9+3
40 = 27+9+3+1

Максимальная высота треугольника из монет

Дано N монет, которые нужно расположить в форме треугольника так, чтобы в первой линии была 1 монета, во второй — 2 и так далее. Необходимо вычислить максимальную высоту треугольника, который возможно сформировать из этих N монет.

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

We have N coins which need to arrange in form of a triangle, i.e. first row will have 1 coin, second row will have 2 coins and so on, we need to tell maximum height which we can achieve by using these N coins.

Examples:
Input : N = 7
Output : 3
Maximum height will be 3, putting 1, 2 and then 3 coins. It is not possible to use 1 coin left.

Input : N = 12
Output : 4
Maximum height will be 4, putting 1, 2, 3 and 4 coins, it is not possible to make height as 5, because that will require 15 coins.

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

Задачу можно решить найдя связь между количество монет и высотой треугольника. Предположим, что высота треугольника — H, тогда количество монет для формирования треугольника меньше или равно N:

Сумма монет для высоты H <= N:

H*(H + 1)/2 <= N
H*H + H – 2*N <= 0

Теперь с использованием квадратичной формулы (игнорируя отрицательный корень) получим:

максимальная высота H может быть (-1 + √(1 + 8N)) / 2

Найти квадратный корень из (1+8N) можно используя Вавилонский метод.

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

This problem can be solved by finding a relation between height of the triangle and number of coins. Let maximum height is H, then total sum of coin should be less than N,

Sum of coins for height H <= N

H*(H + 1)/2 <= N
H*H + H – 2*N <= 0

Now by Quadratic formula (ignoring negative root):

Maximum H can be (-1 + √(1 + 8N)) / 2

Now we just need to find the square root of (1 + 8N) for which we can use Babylonian method of finding square root.

Код
			// Программа C# для нахождения максимальной высоты треугольника из монет
using System;
 
class GFG
{
    /* Вычисляем корень из n*/
    static float squareRoot(float n)
    {
        /* Используем n в первоначальном приближении */
        float x = n;
        float y = 1;
 
        // e обозначает уровень точности
        float e = 0.000001f;
        while (x - y > e)
        {
            x = (x + y) / 2;
            y = n / x;
        }
        return x;
    }
     
    static int findMaximumHeight(int N)
    {
 
        // Вычисляем формулу с квадратным корнем
        int n = 1 + 8*N;
        int maxH = (int)(-1 + squareRoot(n)) / 2;
 
        return maxH;
    }
 
    /* Запуск расчетов */
    public static void Main()
    {
        int N = 12;
        Console.Write(findMaximumHeight(N));
    }
}
		

Шестицветные кубы

У вас есть обычный шестигранный куб и краски шести разных цветов. Вам нужно окрасить каждую сторону куба в свой цвет. Сколько различный вариаций окраски вы сможете сделать?

Примечание Если 2 куба можно повернуть так, чтобы у них совпали по цветам все грани, — окраски считаются одинаковыми.

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

You have a normal six sided cube.

I give you six different colors that you can paint each side of the cube with ( one color to each side ).

How many different cubes can you make?

NOTE: Different means that the cubes can not be rotated so that they look the same. This is important! If you give me two cubes and I can rotate them so that they appear identical in color, they are the same cube.

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

Если бы позиция куба была фиксированной, тогда было бы 6 вариантов для первой грани, 5 — для следующей и т. д. Всего 6! или 720 вариантов. Но положение куба не фиксировано, следовательно, любой из этих 720 кубов может быть повернут так, чтобы расцветка совпала с другим кубом.

Количество возможных положений куба — 24. Проверим это: выберем сторону куба. Повернем ее в одну из шести возможных сторон. Куб все еще может вращаться вокруг оси, проходящей через эту грань. Выберем грань, перпендикулярную зафиксированной, и расположим ее в одном из 4 возможных направлений. Теперь куб зафиксирован полностью.

6 * 4 = 24 (количество возможных положений куба)
720 / 24 = 30 (количество возможных вариантов расцветки с учетом вращения).

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

If the orientation of the cube was fixed, then it would be simply 6 possibilities for the first face, 5 for the next, and so on. In other words 6 factorial, or 720.

But the orientation is not fixed, so any of those 720 cubes which could be rotated to match one of the others is considered the same as those others.

The number of ways you can orient a cube is 24, because:

Pick a cube face. Assign it to one of the 6 directions that it can point. The cube can still rotate freely along the axis of that first face, so pick one of the 4 faces that are perpendicular to the first. Assign it to one of the 4 directions that it can face. And with that, the cube is fully constrained.

6 * 4 is 24.
720 / 24 = 30.

 

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