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

Question 1

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

Answer

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.

Question 2

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

Answer

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

Банки 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

Question 3

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

Answer

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

Question 4

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

Answer

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.

Question 5

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

Answer

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

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

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

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

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

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

Question 6

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

Answer

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.

Question 7

Код

Answer

			// Программа 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));
    }
}

Question 8

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

Answer

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.

Question 9

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

Answer

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

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

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

Question 10

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

Answer

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.

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

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

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

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