Квест новый квест, в котором участники должны выбраться с территории проведения, представляет собой прямоугольник из n × m комнат. каждая комната имеет четыре двери, ведущие в соседние комнаты, из комнат на краю прямоугольника двери ведут наружу, через эти двери можно покинуть территорию проведения квеста. в начале квеста в каждой комнате находится по человеку, а все двери заперты. после начала квеста организаторы дистанционно открывают в каждой комнате запирающий механизм одной из четырёх дверей. теперь человек, находящийся в этой комнате, может открыть эту дверь и перейти в соседнюю комнату, через другие три двери выйти из этой комнаты нельзя. при этом может оказаться так, что дверь, соединяющая две комнаты, будет отпираться только с одной стороны, тогда пройти через эту дверь можно только с той стороны, с которой она будет открываться, проходить через дверь в обратном направлении нельзя, если в соседней комнате будет отперта не эта дверь, а какая-то другая. если комната находится на краю территории и из этой комнаты открыта дверь наружу, то, пройдя через эту дверь, участник навсегда покидает территорию квеста. после начала квеста и отпирания дверей участники начинают перемещаться между комнатами. каждый участник перемещается в соседнюю открытую комнату и продолжает перемещаться до тех пор, пока не покинет территорию квеста. однако возможна ситуация, когда некоторые участники будут бесконечно перемещаться между комнатами и никогда не выйдут наружу. разработчки квеста попросили вас составить такой план отпирания дверей, при котором ровно k человек смогут выбраться наружу с территории квеста. желательно на c++
Тогда первоначальное число должно быть записано как
а после удвоения его запись примет вид
Запишем сумму цифр исходного числа p1:
Теперь запишем сумму удвоенного числа p2:
По условию эти две суммы равны и мы составляем уравнение:
Полученное уравнение решается на множестве двоичных чисел.
Поскольку исходное число двузначное, по крайней мере в старшем разряде оно содержит цифру, отличную от нуля. Следовательно, b3 не может равняться нулю и остается только положить b3=1. Тогда уравнение (1) примет следующий вид:
Учитывая, что каждый бит может принимать значения только 0 и 1, мы должны найти такие комбинации бит, которые дадут в сумме 7=4+2+1, потому что у нас в уравнении только такие коэффициенты. Сгруппируем члены в (2):
Полученная система уравнений будет иметь 7 вариантов решений (вариант a2=a1=a0=0 исключается в силу необходимости наличия цифры в старшем разряде), которым в старшем разряде будут соответствовать цифры от 001(2) до 111(2) или от 1(10) до 7(10).
ответ: 7
Замечание: Из (3) можно легко найти числа, которые соответствуют заданным условиям: 30, 45, 60, 75, 90, 105, 120 (все в десятичной системе счисления). В 16-ричной системе они запишутся как 1E, 2D, 3C, 4B, 5A, 69,