Машина состояний простыми словами

23 Август 2019 - Время чтения: 55 минуты

В программировании часто используется машина состояний, она же конечный автомат. Что это такое? Это распространённый принцип построения алгоритмов, который позволяет упростить их понимание и, соответственно, повысить их надёжность. Многие программы, от компиляторов языков программирования до компьютерных игр, представляют собой, по сути, машины состояний или их комбинацию. Давайте рассмотрим несколько примеров.

Читать далее

Максимальное произведение трёх чисел

22 Август 2019 - Время чтения: 22 минуты

Условие задачи: Дан массив вещественных чисел, размер не менее трёх элементов. Найти максимально возможное произведение любых трёх чисел в нём. Например, в массиве [1, 2, -4, 3] это 1 * 2 * 3 = 6, а в массиве [1, -2, -4, 3] это -2 * -4 * 3 = 24.

Читать далее

Два принтера

21 Август 2019 - Время чтения: 26 минуты

Условие задачи: В офисе стоят два принтера, первый печатает страницу за A секунд, второй - за B секунд. Найти минимальное время, за которое эти принтеры напечатают N страниц, причём N может достигать миллиарда.

Как это часто бывает, на первый взгляд задача тривиальна. Если одна страница печатается A секунд, значит принтер печатает 1/A страниц в секунду. Второй, соответственно, 1/B страниц в секунду. В сумме 1/A + 1/B страниц в секунду. N страниц будут напечатаны за N / (1/A + 1/B) секунд. Правильно? Неправильно! В чём же ошибка?

В том, что нас не интересует средняя скорость принтера, например 1/10 страницы в секунду, если он печатает одну страницу 10 секунд. Нас интересует количество страниц, отпечатанных полностью. Допустим, этот принтер, который печатает одну страницу 10 секунд, будет работать 19 секунд. Сколько он успеет напечатать? Одну страницу! А формула предполагает, что он напечатает "почти две" страницы, и соответственно результат получится неверным.

Поэтому я предлагаю воспользоваться обратной формулой: рассчитать количество страниц, которые будут напечатаны за определённое время. Это можно подсчитать абсолютно точно: N = t/A + t/B, где t - это время.

Очевидно, что с возрастанием количества страниц, которые нужно напечатать, время будет тоже возрастать, или по крайней мере не убывать. То есть задача сводится к поиску значения неубывающей функции. Можно применить обычный бинарный поиск, надо только выбрать минимальное и максимальное возможное время, чтобы знать, в каком промежутке искать. Можно, конечно, бесхитростно положить:

tmin = 1

tmax = N * min(A, B).

Но хотелось бы выбрать границы как-нибудь так, чтобы они были как можно более узкими. Допустим, первый принтер печатает страницу 3 секунды, а второй - 5. Очевидно, что за 15 секунд первый принтер напечатает 5 страниц, а второй - 3. В сумме 8. Если число страниц делится на 8 нацело, то можно точно рассчитать время по формуле:

tmin = N * A * B / (A + B)

Это та же самая формула, только преобразованной по правилам математики, чтобы считать в целых числах. Она даст верный ответ, если N делится на A + B нацело. А если нет? Давайте подумаем. Можно представить работу принтеров так: за каждый цикл из A * B секунд они печатают A + B страниц. Найдём минимальное и максимальное количество циклов. Очевидно, минимальное количество циклов равно N / (A + B). А максимальное отличается на единицу. Останется только найти точное время внутри цикла с помощью бинарного поиска.


Исходный код на Python
n, a, b = map(int, input().split())
cycles, remain = divmod(n, a + b)
tmin = cycles * a * b
 
if remain != 0:
    tmin += min(a, b)
    tmax = (cycles + 1) * a * b
    while tmin < tmax:
        t = (tmin + tmax) // 2
        if t // a + t // b < n:
            tmin = t + 1
        else:
            tmax = t
 
print(tmin)

Исходный код на C#
using System;
using System.Linq;
 
class Program
{
    public static void Main()
    {
        long[] nab = Console.ReadLine().Split().Select(Int64.Parse).ToArray();
        long n = nab[0];
        long a = nab[1];
        long b = nab[2];
        long remain;
        long cycles = Math.DivRem(n, a + b, out remain);
        long tmin = cycles * a * b;
        if (remain != 0)
        {
            tmin += Math.Min(a, b);
            long tmax = (cycles + 1) * a * b;
            while (tmin < tmax)
            {
                long t = (tmin + tmax) / 2;
                if (t / a + t / b < n)
                {
                    tmin = t + 1;
                }
                else
                {
                    tmax = t;
                }
            }
        }
        Console.WriteLine(tmin);
    }
}

Исходный код на C++
#include <algorithm>
#include <cstdlib>
#include <iostream>
 
using namespace std;
 
int main()
{
    long long n, a, b;
    cin >> n >> a >> b;
    lldiv_t cycles = lldiv(n, a + b);
    long long tmin = cycles.quot * a * b;
    if (cycles.rem != 0) {
        tmin += min(a, b);
        long long tmax = (cycles.quot + 1) * a * b;
        while (tmin < tmax) {
            long long t = (tmin + tmax) / 2;
            if (t / a + t / b < n) {
                tmin = t + 1;
            } else {
                tmax = t;
            }
        }
    }
    cout << tmin << endl;
    return 0;
}

Исходный код на C99
#include <stdio.h>
 
typedef struct {
    long long quot;
    long long rem;
} lldiv_t;
 
lldiv_t lldiv(long long a, long long b) {
    lldiv_t d;
    d.quot = a / b;
    d.rem = a % b;
    return d;
}
 
int main(void)
{
    long long n, a, b;
    scanf("%lld%lld%lld", &n, &a, &b);
    lldiv_t cycles = lldiv(n, a + b);
    long long tmin = cycles.quot * a * b;
    if (cycles.rem != 0) {
        tmin += a < b ? a : b;
        long long tmax = (cycles.quot + 1) * a * b;
        while (tmin < tmax) {
            long long t = (tmin + tmax) / 2;
            if (t / a + t / b < n) {
                tmin = t + 1;
            } else {
                tmax = t;
            }
        }
    }
    printf("%lld\n", tmin);
    return 0;
}

Единственный вопрос, который может возникнуть: зачем мы добавляем к tmin минимальное из чисел A и B, а не единицу? Если времени нам не хватило, значит ненапечатанной осталась по крайней мере одна страница. Логично предположить, что если произошло именно так, то эта единственная страница будет напечатана на самом быстром принтере. На это уйдёт A или B секунд, смотря какое число меньше. Чуть-чуть сужаем поиск.

Кроме того, я написал свою реализацию функции lldiv на языке C. Можно было бы без этого обойтись, и просто посчитать делитель и остаток. Но я решил сделать так, как сделал, для единообразия решений. А функции lldiv в языке C может и не оказаться. В моём компиляторе её, например, нет. Хотя в стандарте C99 она присутствует.


Отсортировать буквы внутри слова

21 Август 2019 - Время чтения: 16 минуты

Задача: Дана строка из слов, разделённых пробелами. В каждом слове отсортировать буквы внутри слова, исключая первую и последнюю. Например, из строки "hello world" должно получиться "hello wlord".

Читать далее

Найти высоту горы

21 Август 2019 - Время чтения: 16 минуты

Условие задачи: Дан массив, в котором числа сначала возрастают, а потом убывают. Найти максимальный элемент в таком массиве эффективным способом. Известно, что в массиве не менее трёх элементов.

Читать далее

Выдающаяся чётность

15 Август 2019 - Время чтения: 16 минуты

Условие задачи: Дан массив целых чисел. Все числа, кроме одного, имеют одну и ту же чётность. Например, только одно число чётное, а все остальные нечётные. Или наоборот. Определить, какое число встречается один раз, чётное или нечётное. Минимальная длина массива - 3 элемента. Массив может быть очень большим, поэтому желательно найти решение, которое не потребует анализа все элементов.

Читать далее

Категории

    Коротко обо мне

    Меня зовут Вадим Тукаев, я репетитор по информатике и программированию. Вы можете сконтактировать со мной по почте vadimtukaev@gmail.com или по скайпу pol6energetik. Рассмотрю и другие предложения о сотрудничестве, включая, но не ограничиваясь, написание заказного ПО для Windows/Linux.