Решение задачи Игра 23 с Codeforces

Без пояснения   Просмотров: 88


«Игра 23» — вот во что сейчас играет Поликарп. Изначально у него есть целое число n и его цель преобразовать его в целое число m. За один ход он может умножить n на 2 или умножить n на 3. Он может совершать любое количество ходов.

Выведите количество ходов, сколько необходимо Поликарпу, чтобы получить из числа n число m. Выведите -1, если это невозможно сделать.

Легко доказать, что любой способ преобразования из числа n в число m содержит одинаковое количество ходов (т.е. количество ходов не зависит от способа преобразования).

Код

#include <iostream>
using namespace std;

int main() {
	int n, m, ans = 0;
	cin >> n >> m;
	
	while(n < m) {
		if(m%(n*2) == 0) 
			n*=2;
		else n*=3;
		ans++;
	}
	
	cout << (n == m ? ans : -1);
}

         

Администратор Photo Автор: Администратор




Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться