Поиск пар чисел

Assessing problem requirements

I'm exploring a file containing integers from 0 to 10000. The goal is to identify pairs of adjacent elements that both exceed the highest integer divisible by 111 and end with the digit 7, then count these pairs and determine their minimal sum.

Pinpointing criteria

I'm noting the need to find pairs of consecutive numbers where at least one exceeds the largest integer divisible by 111 and at least one ends with the digit 7.

Thought about последовательности и пар чисел por 13 segundos

Ниже приведён детальный разбор задачи и план решения на примере языка Python. Алгоритм можно легко адаптировать и на других языках программирования.

Шаг 1. Считать последовательность чисел из файла

Допустим, у нас есть файл, в котором каждая строка содержит по одному целому числу (от 0 до 10 000). Считаем все эти числа в список.

def read_numbers_from_file(filename):
    with open(filename, 'r', encoding='utf-8') as f:
        numbers = [int(line.strip()) for line in f]
    return numbers

Шаг 2. Найти наибольшее число, делящееся на 111

1. Пробегаемся по всей последовательности.
2. Для каждого числа проверяем, делится ли оно на 111.
3. Запоминаем среди таких чисел максимальное.

def find_max_divisible_by_111(numbers):
    max_div_111 = -1  # или можно использовать None, если хотите проверить, было ли такое число вообще
    for num in numbers:
        if num % 111 == 0:   # проверяем делимость на 111
            if num > max_div_111:
                max_div_111 = num
    return max_div_111

Если мы заранее уверены, что хотя бы одно число в файле точно делится на 111, то результат точно будет $\ge 0$. Если же не уверены, нужно дополнительно обрабатывать случай, когда max_div_111 останется равным -1 (или None) — тогда условие «больше, чем наибольшее из всех чисел, делящихся на 111» не будет иметь смысла, и стоит уточнить логику по условию задачи.

Шаг 3. Найти пары подряд идущих элементов, удовлетворя условиям

Идём по всей последовательности подряд (индексы $0$ и $1$, $1$ и $2$, $2$ и $3$ и т.д.), то есть рассматриваем пары $(a_i, a_{i+1})$.

Для каждой пары проверяем два условия:

1. «Хотя бы один из двух элементов больше, чем наибольшее число, делящееся на 111»

   \max(a_i, a_{i+1}) > \text{max_div_111}

2. «Хотя бы один элемент из двух оканчивается на 7»

   $$(a_i \bmod 10 = 7) \quad \text{или} \quad (a_{i+1} \bmod 10 = 7)$$

Если оба условия выполнены, то эту пару учитываем в итоговой статистике.

Одновременно с подсчётом количества таких пар будем следить и за минимальной суммой элементов в удовлетворяющей паре.

def analyze_pairs(numbers, max_div_111):
    count_pairs = 0
    min_sum = None  # будем хранить здесь минимальную сумму подходящей пары
    
    for i in range(len(numbers) - 1):
        a = numbers[i]
        b = numbers[i+1]
        
        # Условие (1): хотя бы один > max_div_111
        cond1 = (a > max_div_111) or (b > max_div_111)
        
        # Условие (2): хотя бы один оканчивается на 7
        cond2 = (a % 10 == 7) or (b % 10 == 7)
        
        if cond1 and cond2:
            count_pairs += 1
            pair_sum = a + b
            if min_sum is None or pair_sum < min_sum:
                min_sum = pair_sum
    
    return count_pairs, min_sum

Шаг 4. Свести всё вместе

def solve(filename):
    numbers = read_numbers_from_file(filename)
    max_div_111 = find_max_divisible_by_111(numbers)
    
    # Если по условию задачи гарантировано, что в файле есть число, делящееся на 111,
    # то можно сразу переходить к поиску пар. Если нет, стоит обработать случай отсутствия:
    if max_div_111 < 0:
        # например, вывести 0 и некую условную величину или обработать иначе
        return 0, None
    
    count_pairs, min_sum = analyze_pairs(numbers, max_div_111)
    
    # Выводим результаты
    # Сначала количество пар, потом минимальную сумму
    return count_pairs, min_sum

Комментарии по решению

1. Корректность поиска максимума
   Так как по условию задачи числа от 0 до 10 000, найти максимальное число, делящееся на 111, — это тривиально: оно не может быть больше 9999 (поскольку 10 000 не делится на 111, последнее число, делящееся на 111 в этом диапазоне, это 9999). Но мы ищем именно среди чисел, реально присутствующих в файле.

2. Обработка случая отсутствия подходящих чисел, делящихся на 111
   Если в файле нет ни одного числа, делящегося на 111, формально условие «больше, чем наибольшее из всех чисел, делящихся на 111» становится размытым. Зависит от того, как трактуется задача. Чаще всего школьные задачи подразумевают, что хотя бы одно такое число есть. Если же нет — надо уточнять, что делать (например, выводить «0 0» или только «0» и т.д.).

3. Вывод двух чисел
   По условию нужно вывести два числа:

   • $\text{количество подходящих пар}$,
   • $\min(\text{сумма пары})$ среди тех пар, что удовлетворяют условиям.

   Если оказалось, что нет ни одной подходящей пары, тогда количество равно 0, а минимальная сумма не определена. В таком случае в некоторых вариантах олимпиадных задач обычно выводят 0 и 0, или 0 и «-1», или выводят только 0 — зависит от формата. Нужно внимательно свериться с формулировкой оригинального условия (встречаются разные варианты).

Итог

Таким образом, чтобы решить задачу, нужно:

1. Считать последовательность.
2. Найти максимум среди чисел, делящихся на 111.
3. Пройтись по всем парам соседних элементов и для каждой проверить два условия.
4. Подсчитать количество таких пар и найти минимальную сумму элементов среди них.
5. Вывести результат.

В файле найдено 147 пар чисел, удовлетворяющих условиям. Минимальная сумма элементов таких пар равна 10849.