9637. Дино и снежные здания

Дино едет путешествовать в Китай (тогда еще не был распространен Коронавирус) и видит там здания в количестве 10⁹. Высота первого здания 1, второго здания 1 + 2, третьего 1 + 2 + 3 и т. д. Высота последнего здания 1 + 2 + 3 + ... + 10⁹ (все высоты даны в метрах).

Дино после проведенного дня заснул и наутро увидел интересный вид: ночью пошел снег и высота всех зданий одинаково увеличилась! Дино хочет знать сколько метров снега выпало. Для этого он подошел к двум соседним зданиям (например к 3-му и 4-му) и измерил их новые высоты. Определите сколько метров снега выпало, если высоты этих зданий равны соответственно a и b метров.

Вход. В одной строке заданы целые числа a и b (a ≤ b). Известно, что правильный ответ всегда существует, а высота выпавшего снега не более 10⁹ метров.

Выход. Выведите высоту выпавшего снега.

Пример входа	Пример выхода
11 16	1

РЕШЕНИЕ

математика

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

Пусть Дино провел измерения высоты снега у зданий с высотами 1 + … + i и 1 + … + i + (i + 1). Пусть x – высота выпавшего снега. Тогда

a = 1 + … + i + x = (1 + i) * i / 2 + x = (i + i²) / 2 + x,

b = 1 + … + i + (i + 1) + x = (2 + i) * (i + 1) / 2 + x = (2 + 3i + i²) / 2 + x

Имеем: b – a = (2i + 2) / 2 = i + 1, откуда i = b – a – 1. Высота выпавшего снега x равна a – (i + i²) / 2.

Пример

В задаче a = 11, b = 16. Тогда i = 16 – 11 – 1 = 4. Высота выпавшего снега равна 11 – (4 + 4²) / 2 = 11 – 10 = 1.

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

Читаем входные данные.

scanf("%lld %lld", &a, &b);

Вычисляем значение i и высоту выпавшего снега x.

i = b - a - 1;

x = a - i * (i + 1) / 2;

Выводим ответ.

printf("%lld\n", x);