Птички на проводе

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

Условие задачи: Дана строка, возможно очень большой длины, в которой символ _ ("знак подчёркивания") символизирует провод, а любой другой - птичку на нём. Допустим, на провод хочет сесть ещё одна птица, причём так, чтобы быть как можно дальше от ближайшего соседа. Найти максимально возможное расстояние до ближайшей птицы. Гарантируется, что на проводе есть хотя бы одна птица и хотя бы одно пустое место.

Несколько примеров вывода программы, с иллюстрацией того, как этот провод мог бы выглядеть после того, как на него сядет новая птица (программа эту строку выводить не обязана, это просто для наглядности).

a_____a → 3 ↔ a__A__a
_____a_ → 5 ↔ A____a_
a__aa__ → 2 ↔ a__aa_A
_aaaaaa → 1 ↔ Aaaaaaa

Решение: Очевидно, нам нужно найти максимальное расстояние между двумя птицами, и поделить пополам, округляя вверх. Однако расстояния от начала строки и до первой птицы, а также от последней птицы и до конца строки должны обрабатываться особо. Эти расстояния делить пополам не надо, потому что расстояние до края провода не считается.


Программа на языке C99
#include <stdio.h>
 
unsigned max(const unsigned a, const unsigned b)
{
    return a > b ? a : b;
}
 
int main(void)
{
    unsigned dist_bird = 0;
    int ch;
    while ((ch = getchar()) == '_') {
        ++dist_bird;
    }
    unsigned wire_len = 0;
    while (ch != EOF && ch != '\n') {
        if (ch == '_') {
            ++wire_len;
        } else {
            dist_bird = max(dist_bird, (wire_len + 1) / 2);
            wire_len = 0;
        }
        ch = getchar();
    }
    printf("%u\n", max(dist_bird, wire_len));
    return 0;
}

Строка может быть большой длины, поэтому лучше не сохранять её в памяти, тем более что для решения задачи вполне достаточно анализировать символ за символом.

Currently there are no comments, so be the first!

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

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

Категории