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

Огурцы, богатства, бочки — подборка задач для программистов

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

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

Огурцы под жарким солнцем

Ранним утром бакалейщик выставил 100 килограмм огурцов на улицу перед своим магазином. Огурцы на 99 % состоят из воды. День был жарким и часть воды из огурцов испарилась. В конце дня огурцы состояли из воды на 98 %. Сколько килограммов эти огурцы весили в конце дня (если бакалейщик не продал ни одного огурца)?

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

In the morning a green-grocer puts 100 kg cucumbers outside in front of his shop. These cucumbers consists for 99% out of water. Because it is a warm day some water will evaporate. As a result, at the end of the day the cucumbers consist for 98% out of water. How many kg’s of these cucumbers are left at the end of the day (if the greengrocer has not sold a single cucumber)?

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

Если 100 килограмм огурцов на 99 % состоят из воды, следовательно, 1 килограмм огурцов состоит из другого материала. В конце дня часть воды испарилась, а оставшаяся вода составляет 98 % от веса огурцов. Этот 1 килограмм другого материала, который не испарился, теперь составляет 2 % от общего веса. Следовательно, в конце дня у бакалейщика осталось только 50 килограмм огурцов.

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

100 kg cucumbers consists for 99% out of water. From this statement it follows that 1 kg of the cucumbers consists of other material. At the end of the day part of the water is evaporated and the cucumbers consists for 98% out of water. Then this 1 kg other material which did not evaporate is 2 % of the total weight. Hence at the end of the day, the green-grocer has only 50 kg of cucumbers left.

Города и богатства

Дано n городов: x1, x2, …… xn — у каждого своё богатство T[i] и цвет C[i]. Вы можете выбрать между посещением города или его пропуском. Разрешено только движение вперёд. При посещении города вы получаете следующую сумму денег:

  • A*T[i], если цвет города совпадает с цветом ранее посещённого города;
  • B*T[i], если это первый посещённый город такого цвета, или цвет отличается от цвета предыдущего города.

Значения T[i], A и B могут быть отрицательными, в то время как C[i] может быть от 1 до n.

Задача: Необходимо составить алгоритм получения максимально возможной прибыли.

Примеры:

Вход: A = -5, B = 7
Богатство = {4, 8, 2, 9}
Цвет = {2, 2, 6, 2}
Выход: 133
Посетить города 1, 2 и 3. Прибыль = 8 * 7 + 2 * 7 + 9 * 7 = 133.

Вход: A = 5, B = -7
Богатство = {4, 8, 2, 9}
Цвет = {2, 2, 6, 2}
Выход: 57
Посетить города 1, 2, 4. Прибыль = (-7) * 4 + 8 * 5 + 9 * 5 = 57.

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

Given n cities: x1, x2, …… xn: each associated with T[i] (treasure) and C[i] (color). You can choose to visit a city or skip it. Only moving in the forward direction is allowed.When you visit a city you receive the following amount:

  • A*T[i] if the color of visited city is the same as color of previously visited city;
  • B*T[i] if this is the first city visited or if the color of the visited city is different from the color of the previously visited city.

The values of T[i], A and B can be negative while C[i] ranges from 1 to n.

We have to compute the maximum profit possible.

Examples:

Input : A = -5, B = 7
Treasure = {4, 8, 2, 9}
color = {2, 2, 6, 2}
Output : 133
Visit city 1, 2 and 3. Profit = 8 * 7 + 2 * 7 + 9 * 7 = 133

Input : A = 5, B = -7
Treasure = {4, 8, 2, 9}
color = {2, 2, 6, 2}
Output: 57
Visit city 1, 2, 4. Profit = (-7) * 4 + 8 * 5 + 9 * 5 = 57

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

Применим подход динамического программирования для решения этой задачи.

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

We can use Dynamic Programming for the following implementation.

Код
			// Подход, использующий меморизацию для нахождения максимально
// возможной прибыли.
#include <bits/stdc++.h>
using namespace std;
  
const int MAX = 1001;
  
int dp[MAX][MAX];
  
// k - текущий индекс, col - предыдущий цвет.
int MaxProfit(int treasure[], int color[], int n,
              int k, int col, int A, int B)
{
    if (k == n) // base case
        return dp[k][col] = 0;
  
    if (dp[k][col] != -1)
        return dp[k][col];
  
    int sum = 0;
  
    // У нас 2 варианта:
    // посетить город или пропустить его.
  
    if (col == color[k]) // проверка, совпадает ли цвет с цветом предыдущего города
        sum += max(A * treasure[k] + 
               MaxProfit(treasure, color, n, k + 1, 
                                     color[k], A, B),  
               MaxProfit(treasure, color, n, k + 1, 
                                        col, A, B));
    else
        sum += max(B * treasure[k] + 
                MaxProfit(treasure, color, n, k + 1, 
                                   color[k], A, B), 
                MaxProfit(treasure, color, n, k + 1, 
                                        col, A, B));
  
    // Вернуть максимальный из двух вариантов
    return dp[k][col] = sum;
}
  
int main()
{
    int A = -5, B = 7;
    int treasure[] = { 4, 8, 2, 9 };
    int color[] = { 2, 2, 6, 2 };
    int n = sizeof(color) / sizeof(color[0]);
    memset(dp, -1, sizeof(dp));
    cout << MaxProfit(treasure, color, n, 0, 0, A, B);
    return 0;
}
		

Заполненность бочки

Два рабочих на заводе спорят о том, сколько пива находится в бочке. Один оптимистично считает, бочка заполнена больше, чем наполовину, а другой заявляет, что пива в ней меньше половины. Как они могут проверить, кто из них прав, без использования измерительных приборов?

Примечание: крышку бочки можно снять.

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

Two workers in a brewery are trying to settle an argument over how much beer is inside a barrel. One worker thinks the barrel is more than half full while the other says it’s less than half full. How can they settle the argument without using any measuring tools?

Note: the top of the barrel can be easily removed.

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

Один из способов решить спор заключается в том, чтобы наклонить бочку так, чтобы содержимое было вровень с нижним краем отверстия (как раз перед тем, как жидкость прольётся).

Если стало видно дно бочки, то содержимого в бочке меньше половины (левое изображение). Если же дна не видно, то бочка заполнена больше, чем наполовину (правое изображение).

Другое решение — медленно перевести бочку (с крышкой) в горизонтальное положение и уложить её на землю. Затем медленно вернуть бочку в вертикальное положение. Потом следует снять крышку и посмотреть на мокрую отметку, оставленную содержимым на этой крышке. Если отметка преодолела диаметр крышки значит, бочка заполнена более, чем наполовину.

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

One simple way of solving the dispute is for the workers to tip the barrel until the beer is level with the lowest part of the top (just before it would spill).

If they can see the bottom of the barrel, then it’s less than half full (left image). On the other hand, if they cannot see the bottom, then the barrel is more than half full (right image).

Another solution, is to slowly tip the barrel (with the cover on) and lay it flat on the ground. Then slowly return the barrel to the upright position. Remove the cover and look at the watermark left by the beer on its underside. If the watermark extends beyond the diameter of the cover, the barrel is more than half full.

 

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