1. Идея

Нужно среди всех гирь выбрать такую массу a_i, для которой расстояние до эталона X, то есть |a_i - X|, минимально.

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

Самый прямой способ — пройти по всем гирям и хранить текущий лучший ответ:

• какая масса сейчас считается лучшей;
• при просмотре новой гири сравнивать её с текущей лучшей.

Это обычный линейный перебор с аккуратным сравнением по двум критериям:

1. сначала по расстоянию до X;
2. при равенстве — по самой массе.

2. Наблюдения

1. Сортировка не нужна.
   Нам не требуется выводить все подходящие гири или искать что-то сложное — достаточно найти минимум по понятному правилу.

2. Для каждой гири важны только два значения:

   • |a_i - X|
   • сама масса a_i

3. Сравнение двух кандидатов выглядит так:

   • лучше тот, у кого меньше |a_i - X|;
   • если расстояния равны, лучше тот, у кого меньше масса.

4. Так как n может быть до 2 * 10^5, линейный проход подходит отлично.

3. Алгоритм

1. Считать n и X.
2. Считать все массы.
3. Взять первую массу как текущий лучший ответ best.
4. Для каждой следующей массы cur:
   • посчитать d1 = |cur - X|;
   • посчитать d2 = |best - X|;
   • если d1 < d2, то заменить best = cur;
   • если d1 == d2 и cur < best, тоже заменить best = cur.
5. Вывести best.

4. Почему это работает

Докажем, что после обработки всех гирь в best действительно хранится правильный ответ.

После просмотра первой гири best выбран верно среди одной рассмотренной гири.

Предположим, что после просмотра первых k гирь переменная best содержит лучшую из них по правилу задачи:

• минимальное расстояние до X,
• при равенстве расстояний — минимальную массу.

Теперь рассматриваем гирю номер k + 1 с массой cur.

Есть два варианта:

1. cur лучше текущего best:

   • либо |cur - X| < |best - X|,
   • либо расстояния равны, но cur < best.

   Тогда по условию именно cur должен стать лучшим среди первых k + 1 гирь, и алгоритм делает best = cur.

2. cur не лучше текущего best.

   Тогда лучший элемент среди первых k + 1 гирь не меняется, и алгоритм оставляет best без изменений.

Значит, после каждого шага best корректен для всех уже просмотренных гирь. Следовательно, после обработки всех n гирь в best находится искомая масса.

5. Сложность

• Время: O(n), потому что каждая гиря обрабатывается один раз.
• Память:
  • в C++ решении: O(1), так как можно читать числа по одному;
  • в Python решении из эталона: O(n), так как весь массив читается в список.

6. Код на C++17

#include <iostream>
#include <vector>
#include <cstdlib>

using namespace std;

int main() {
    int n;
    long long X;
    cin >> n >> X;

    long long best;
    cin >> best;

    for (int i = 1; i < n; i++) {
        long long a;
        cin >> a;

        long long d1 = llabs(a - X);
        long long d2 = llabs(best - X);

        if (d1 < d2 || (d1 == d2 && a < best)) {
            best = a;
        }
    }

    cout << best << '\n';
    return 0;
}

7. Код на Python 3

n, X = map(int, input().split())
a = list(map(int, input().split()))

best = a[0]

for i in range(1, n):
    cur = a[i]
    d1 = abs(cur - X)
    d2 = abs(best - X)
    if d1 < d2 or (d1 == d2 and cur < best):
        best = cur

print(best)