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

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

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

Считаем деньги, уравниваем элементы массива и усаживаем людей в баре. Заинтригованы? Встречайте очередную подборку задачек!

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

Начальный капитал

У некого человека в кармане лежит сумма денег между $90 и $95. Этот человек посещает несколько храмов. Как только он входит в храм, количество денег у него удваивается, а на выходе он жертвует $100 в каждом храме. Когда он выходит из последнего храма, его карман остается пустым. Вопрос: сколько денег было у этого человека изначально и сколько храмов он посетил?

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

One person has some money in his pocket, total sum is between $90 and $95. He visits some number of temple on the way. As soon as he enters a temple, his money gets double and he offers $100 in each temple thus his pocket gets empty after he returns from the last temple. Now the question is how much money he had initially and how much temples did he visit?

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

Начнем считать с последнего храма:

  • После посещения храма (1) у человека осталось $0, следовательно, у него было (0+100)/2 = 50$ перед посещением храма.
  • Перед посещением храма (2) у него было (50+100)/2 = 75.
  • Перед посещением храма (3) у него было (75+100)/2 = 87,5.
  • Перед посещением храма (4) у него было (87,5+100)/2 = 93,75.
  • Перед посещением храма (5) у него было (93,75+100)/2 = 96,875, что превышает исходные условия.

Ответ: У человека было $93.75, и он посетил 4 храма.

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

Let’s try start counting from the last temple:

  • After last temple (1) visit he is left with 0, thus => (0+100)/2=50, he had 50 before entering the temple.
  • Before previous (2) temple visit, he has (50+100)/2 = 75.
  • Before previous (3) temple visit, he has (75+100)/2 = 87,5.
  • Before previous (4) temple visit, he has (87,5+100)/2 = 93,75.
  • Before previous (5) temple visit, he has (93,75+100)/2 = 96,875 — the sum exceeds initial conditions.

Answer: The person initially had $93.75 and he visited 4 temples.

Равенство элементов массива

Дан массив положительных целых чисел arr[]. Разрешены следующие операции:

  1. Выбрать 2 индекса, элемент массива с первым индексом увеличить на 1, элемент со вторым индексом — уменьшить на 1. Стоимость операции = a.
  2. Выбрать любой индекс, элемент с этим индексом увеличить на 1. Стоимость операции = b.

Задача: найти минимальную стоимость операций, которые позволят сделать все элементы массива равными.

Примеры:

Вход: n = 4, a = 2, b = 3

arr[] = { 3, 4, 2, 2 }

Выход : 5

Выполним операцию 2 над 3-им элементом (нумерация с 0). Стоимость операции — 2. Выполним операцию 1 над элементом 1 (уменьшение) и элементом 2 (увеличение). Стоимость этой операции — 3.

Вход : n = 3, a = 2, b = 1

arr[] = { 5, 5, 5 }

Выход : 0

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

Given an array arr[] of n positive integers. There are two operations allowed:

  1. Pick any two indexes, increase value at one index by 1 and decrease value at another index by 1. It will cost a.
  2. Pick any index and increase its value by 1. It will cost b.

The task is to find the minimum cost to make all the elements equal in the array.

Examples:

Input : n = 4, a = 2, b = 3

arr[] = { 3, 4, 2, 2 }

Output : 5

Perform operation 2 on 3rd index (0 based indexing). It will cost 2. Perform operation 1 on index 1 (decrease) and index 2 (increase). It will cost 3.

Input : n = 3, a = 2, b = 1

arr[] = { 5, 5, 5 }

Output : 0

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

Учтем, что в финальном массиве нет значений больше, чем максимальное значение исходного массива, потому что увеличивать все элементы не имеет смысла. Кроме того, значения будут больше минимального значения в исходном массиве. Проверим последовательно все возможные значения элементов финального массива (которые должны быть равны) и посчитаем, сколько операций второго типа должно быть выполнено. Для значения элемента i (одного из возможных значений элемента финального массива) число операций составит (n * i – s), где s — сумма всех элементов исходного массива. Число операций первого типа, необходимых, чтобы приравнять элементы к i, можно вычислить следующим образом:

			for (int j = 0; j < n; j++)
  op1 += max(0, a[j] - i)

После вычисления количества операций для каждого i проверяем, меньше ли это количество ans = (n * i – s) * b + op1 * a — предыдущего значения ans. Если меньше — записываем в ans новое количество.

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

Observe, the final array will not have elements greater than the maximum element of the given array because there is no sense to increase all the elements. Also, they will greater than the minimal element in the original array. Now, iterate over all the possible value of the final array element which needs to be equal and check how many operations of second type must be performed. For elements to be i (which is one of the possible value of final array element) that number is (n * i – s), where s is the sum of all numbers in the array. The number of operation of the first type for element to be i in the final array can be find by:

			for (int j = 0; j < n; j++)
  op1 += max(0, a[j] - i)

At the end of each iteration simply check whether the new value ans = (n * i – s) * b + op1 * a is less than previous value of ans. If it is less, update the final ans.

Код
			using System;
 
class GFG {
     
    // Получаем минимальную стоимость операций
    static int minCost(int n, int [] arr,
                            int a, int b)
    {
        int sum = 0, ans = int.MaxValue;
        int maxval = 0;
     
        // Вычисляем максимальный элемент и сумму элементов массива
        for (int i = 0; i < n; i++) {
            sum += arr[i];
            maxval = Math.Max(maxval, arr[i]);
        }
     
        // Для каждого возможного значения элемента
        for (int i = 1; i <= maxval; i++) {
            int op1 = 0;
     
            // Находим количество операций
            for (int j = 0; j < n; j++)
                op1 += Math.Max(0, arr[j] - i);
     
            // Находим минимальную стоимость
            if (sum <= n * i)
                ans = Math.Min(ans, (n * i - sum)
                                  * b + op1 * a);
        }
     
        return ans;
    }
     
    // Стартер
    public static void Main()
    {
        int n = 4, a = 2, b = 3;
        int []arr= { 3, 4, 2, 2 };
     
        Console.Write(minCost(n, arr, a, b));
    }
}

Бар для асоциальных людей

В одном баре стоит 25 стульев, выстроенных в линию. Посетители этого бара не любят общаться, и когда кто-то приходит, он всегда старается сесть как можно дальше от присутствующих. Если же мест без соседства с кем-либо не осталось, он разворачивается и уходит. Владелец бара хочет, чтобы посетителей было как можно больше. Первому пришедшему посетителю бармен может указать место, на которое нужно сесть, последующие же выберут себе мест сами. Предположим, что места пронумерованы от 1 до 25. Какое место следует занять первым?

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

There is a bar with 25 seats arranged in a line. The people there are anti-social so when they walk in the bar, they always try to find a seat farthest away from others. If one person walks in and find there is no seat are adjacent to nobody, that person will walk away. The bar owner wants as many people as possible. The owner can tell the first customer where to sit. all the other customers will pick the farthest possible seat from others. Assume that seats are numbered 1 to 25. Which seat should be occupied first?

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

Первый посетитель должен занять стул 9 или 17 (неважно, на какой именно, поскольку ряд симметричен). Предположим, что 9. Следующий посетитель тогда выберет 25, как самый дальний от 9. Следующие 2 человека выберут 1 и 17. Ещё трое займут места 5, 13 и 21. Оставшиеся шесть сядут на 3, 7, 11, 15, 19 и 23. Максимум будет размещено 13 человек, и никто не будет сидеть рядом. Если же первым местом будет не 9 или 17 — посетителей будет меньше 13.

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

The first person must take either stool 9 or 17 (because of symmetry, it doesn’t matter which). Assume they pick seat 9. The next person will pick seat 25, since it is the furthest from seat 9. The next two people will take Seats one and 17. The next three will occupy 5, 13, and 21. The next six will occupy 3, 7, 11, 15, 19, and 23. This seats the maximum of 13 people, and no one is sitting next to another person. If a seat other than 9 or 17 is chosen first, the total bar patrons will be less than 13.

Следите за новыми постами
Следите за новыми постами по любимым темам
7К открытий7К показов
Также рекомендуем
Обложка поста 7 легендарных уравнений на JavaScript
7 легендарных уравнений на JavaScript
Математика и компьютерные науки идут рука об руку. Подобрали 7 математических формул разного уровня сложности для проверки — сможете ли вы их реализовать? И на всякий случай снабдили статью нашими решениями.