1542. Задача ? 1 ? 2 ? … ? n = k

Имеется формула ? 1 ? 2 ? … ? n = k. Вместо знаков ‘?’ ставятся ‘+’ или ‘-‘ так, чтобы получить верное равенство. Для заданного k найти минимальное n, для которого существует указанная формула. Например, для k = 12 ответом будет n = 7, так как -1 + 2 + 3 + 4 + 5 + 6 – 7 = 12.

Вход. Первая строка содержит количество тестов, за которой следует пустая строка. Каждая следующая строка содержит целое число k (0 £ |k| £ 10⁹). Входные тесты разделены пустой строкой.

Выход. Для каждого теста вывести минимальное n (1 £ n), для которого существует формула, из которой можно получить k. Вывод результатов для последовательных тестов разделять пустой строкой.

Пример входа	Пример выхода
2 12 -3646397	7 2701

РЕШЕНИЕ

математика

Анализ алгоритма

Положим k = |k|, после чего k станет положительным. Ищем минимальное n, для которого 1 + 2 + … + n ³ k. Решим уравнение (1 + n) * n / 2 = k относительно n. После преобразований получим: n² + n – 2k = 0, дискриминант D = 1 + 8k. Положительный корень уравнения, округленный вверх, равен

n₁ =

Ответом задачи будет такое n Î {n₁, n₁ + 1, n₁ + 2}, для которого четность суммы S = 1 + 2 + … + n и четность k совпадают. Отдельно следует обработать случай k = 0: поскольку если 1 + 2 – 3 = 0, то ответом будет 3.

Если в сумме S = 1 + 2 + … + n перед любым из слагаемых поставить минус, четность суммы при этом не изменится.

Пример

При k = 12 наименьшим n, для которого 1 + 2 + … + n ³ 12, будет n = 5. Сумма чисел от 1 до 5 нечетна, как и сумма от 1 до 6. Сумма чисел от 1 до 7 равна (1 + 7) * 7 / 2 = 28 и ее четность совпадает с четностью 12. Из 28 следует вычесть 16, чтобы получить 12. Выбираем слагаемые, сумма которых равна 16 / 2 = 8, и ставим знак минус перед ними. Например, искомыми выражениями могут быть:

-1 + 2 + 3 + 4 + 5 + 6 – 7 = 12,

1 + 2 – 3 + 4 – 5 + 6 + 7 = 12,

1 – 2 + 3 + 4 + 5 – 6 + 7 = 12

Реализация алгоритма

Читаем количество тестов tests.

scanf("%d",&tests);

while(tests--)

{

Для каждого теста читаем значение k и находим его модуль.

scanf("%d",&k); k = abs(k);

Отдельно обрабатываем случай k = 0.

if (k == 0)

{

printf("3\n");

continue;

}

Находим положительный корень n квадратного уравнения, приведенного выше. Увеличиваем n на 1 до тех пор, пока сумма 1 + 2 + … + n = и значение k не будут иметь одинаковую четность.

n = (int)(ceil((-1 + sqrt(1 + 8 * k)) / 2));

while(((1 + n) * n / 2 - k) % 2 == 1) n++;

Для текущего теста выводим результат.

printf("%d\n",n);

}