Old Programmer
4144 subscribers

Пример олимпиадной задачи по программированию

646 full reads
986 story viewsUnique page visitors
646 read the story to the endThat's 66% of the total page views
1 minute — average reading time

Все ссылки на статьи и ролики моего канала Old Programmer расположенные по темам тут. А здесь все мои ресурсы по рекурсивному и олимпиадному программированию

Еще одна задача из моего архива олимпиадного программирования. Олимпиада прошла совсем не давно и некоторые задачи, которые в ней предлагались, я опубликую.

Задача "Ассемблер"

Фабула

Вы хотели бы научиться программировать на ассемблере? У вас есть шанс. Ассемблер не похож на обычные языки программирования. Он оперирует не переменными, а ячейками памяти и регистрами. Регистры, это тоже ячейки памяти, но эта память находится в самом процессоре. Она не большая, но очень быстрая. Конечно в одной задаче мы не сможем изучить весь ассемблер, но с двумя командами я вас познакомлю.

И так есть два регистра RAX и RBX. И есть две команды MOV и ADD. Первая команда копирует число из одного регистра в другой: MOV RBX, RAX (из RAX в RBX), вторая осуществляет операцию сложения: ADD RAX, RBX - складываются два числа, а результат помещается в RAX.

Задание

И так у вас есть две команды MOV RBX, RAX и ADD RAX, RBX. Команды MOV RAX, RBX и ADD RBX, RAX использовать нельзя. Пусть в регистре RAX лежит число N, в регистре RBX лежит ноль. Необходимо с помощью только указанных команд получить в RAX число M. Ваша задача найти минимальное количество таких команд.

Входные данные

На входе даны два числа N и M. (N>=0, N<=10^9; M>=0, M<=10^9).

Выходные данные

Одно число — минимальное количество указанных операций, которые нужно произвести, чтобы получить в RAX нужное число. Если это не возможно, то выводится -1.

Примеры

Пример олимпиадной задачи по программированию

Решение

Может показаться что возможно рекурсивное решение. Т.е. на самом деле рекурсивное решение, конечно, возможно, но время выполнения резко возрастает с увеличением разницы между числами.

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

  • Второе число должно делится на первое
  • Минимальное количество команд равно сумме простых множителей частного от деления второго числа на первое. В случае пары 1 8, 8 = 2 * 2 * 2. Сумма двоек и дает 6. Для пары 2 18 имеем, 18/2 = 9, 9 = 3 * 3, количество команд равно 3 + 3 = 6.

Результат решения представлен в olmp4000.c.

До следующих встреч. Подписываемся на мой канал Old Programmer, здесь много материалов по разным вопросам программирования.

Фрагмент программы olmp4000.c
Фрагмент программы olmp4000.c