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

Question 1

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

Answer

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)?

Question 2

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

Answer

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

Question 3

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

Answer

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.

Question 4

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

Answer

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

Question 5

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

Answer

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

Question 6

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

Answer

We can use Dynamic Programming for the following implementation.

Question 7

Код

Answer

			// Подход, использующий меморизацию для нахождения максимально
// возможной прибыли.
#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;
}

Question 8

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

Answer

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.

Question 9

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

Answer

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

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

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

Question 10

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

Answer

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.

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

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

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

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