Задача 5: Финансовая реформа
Однажды после олимпиады по экономике Мише приснился очень красочный и необычный сон. Мальчик оказался министром финансов Берляндии. Осознав свою значимость, он тут же решил произвести в стране реформу. Раньше в Берляндии использовались банкноты с номиналами 1, 10, 100 и 1000 бурлей. Мише данная система показалась крайне банальной, поэтому он решил придумать что-то свое.
Мальчик выбрал два целых числа x и y (x ≤ y) и заявил, что теперь в Берляндии будут использоваться только банкноты с номиналами x, x + 1, x + 2, ..., y бурлей. Вскоре реформа была принята и вступила в силу, однако населению страны это совсем не понравилось. Недовольства начались из-за того, что теперь, используя новые банкноты, можно было набрать далеко не любую сумму.
Например, если Мишей были выбраны числа x = 5 и y = 7, то невозможно набрать суммы 1, 2, 3 и 4 бурлей. Также не получится набрать суммы 8 и 9 бурлей. Если же выбрать числа x = y = 2, то невозможно будет набрать любую нечетную сумму.
Миша, находясь на грани увольнения, решил успокоить население Берляндии и предъявить такое минимальное число N, что при помощи новых банкнот возможно набрать любую сумму, начиная с N. Таким образом, должно быть возможно набрать суммы N бурлей, N + 1 бурлей, N + 2 бурлей, и так далее. Помогите Мише найти искомое число N и избежать увольнения.
Входные данные
В первой строке входных данных записано целое число x — минимальный номинал новых банкнот.
Во второй строке записано целое число y (1 ≤ x ≤ y ≤ 2×109) — максимальный номинал новых банкнот.
Выходные данные
Выведите одно натуральное число N — минимальное число, такое, что при помощи банкнот с номиналами x, x + 1, x + 2, ..., y можно набрать любую сумму, начиная с N бурлей.
Если такого числа не существует, в качестве ответа выведите −1.
Обратите внимание, что ответ может получиться достаточно большим, поэтому следует использовать 64-битный тип данных, например long long в C/C++, long в Java и C#, int64 в Pascal.
Ответы
Ответ:
Объяснение:
Предлагаю рассмотреть несколько примеров, чтобы найти закономерность и далее провести анализ.
Пример 1:
x = 1, y = 3
В данном случае все натуральные числа можно получить, так как x = 1 и тем самым можно получить любую сумму.
Пример 2:
x = 1, y = 2
В данном случае не получится набрать суммы 3 и 4 бурлей, так как y = 2 и нет банкноты номиналом 3.
Пример 3:
x = 5, y = 7
В данном случае нельзя получить суммы от 1 до 4, а также 8 и 9 бурлей.
По приведенным примерам можно заметить, что если разница между y и x больше или равна 2, то можно набрать любую сумму. В противном случае, если разница равна 1, то нельзя набрать все нечетные суммы.
Таким образом, решение можно представить в виде алгоритма:
1. Считать x и y.
2. Проверить, если разница между y и x больше или равна 2, то вывести x.
3. Если разница между y и x равна 1, то проверить, является ли x нечетным числом.
- Если да, то вывести -1.
- Если нет, то вывести x - 1.