Question

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

Answer 1

Ответ:

# ruby v3.2

@cache = {}

def has_decomposition?(x, y, n)

   return @cache[n] if @cache.has_key?(n)

   if n < x

       @cache[n] = false

       return false

   elsif n.between?(x, y)

       @cache[n] = true

       return true

   else

       for i in x..y

           next if !has_decomposition?(x, y, n - i)

           @cache[n] = true

           return true

       end

       @cache[n] = false

       return false

   end

end

def getN(x, y)

   return -1 if x == y && x > 1

   for n in x..(2*10**9)

       found = true

       for i in n..(2*n-1)

           next if has_decomposition?(x, y, i)

           found = false

           break

       end

       return n if found

   end

   return -1

end

x = gets().to_i

y = gets().to_i

p getN(x, y)

Answer 2

Чтобы решить эту задачу, нужно найти минимальное число N такое, что с использованием банкнот с номиналами от x до y можно набрать любую сумму, начиная с N бурлей. Мы можем решить эту задачу с помощью жадного алгоритма.

Введем переменную total, которая будет представлять сумму, которую мы можем набрать. На первом шаге установим total в x, так как мы обязаны иметь возможность набрать x бурлей.

Затем будем поочередно добавлять к total следующий возможный номинал банкноты (x, x+1, ..., y) и обновлять total до максимального значения, которое мы можем набрать с использованием текущего номинала.

Продолжим этот процесс, пока не дойдем до ситуации, когда total становится больше или равно y. Если total стало больше y, то это означает, что мы можем набрать любую сумму, начиная с N = x бурлей. Если мы дошли до ситуации, когда total становится равно y, то увеличим y на 1 и повторим процесс.

Вот пример кода на Python:

def find_min_N(x, y):
    total = x
    N = x

while total < y:
        y += 1
        total += y

return N if total >= y else -1

# Ввод данных
x = int(input())
y = int(input())

# Вызов функции и вывод результата
result = find_min_N(x, y)
print(result)

Этот код считывает x и y, затем вызывает функцию find_min_N и выводит результат. Если результат равен -1, то ответа не существует. В противном случае, результат будет минимальным числом N, удовлетворяющим условиям задачи.