Varian and Mateo are alchemists trying to outdo each other. Varian has created a magical device that converts lead into gold, and it works as follows. It has two receptacles. In the first, he places lead bars, in the second, he places one gold bar, and after muttering a magical incantation, the amazing device replicates whatever is in receptacle 2 as many times as there are lead bars in receptacle 1. Unfortunately though, there is a price to all this magic, and one of the lead bars in receptacle 1 gets consumed (see figure below). Varian doesn't mind too much though, because his device is built robustly, and he can just use it again with all the gold he already has in receptable 2, and the lead bars in receptacle 1. Mateo has only recently completed his apprenticeship and wants to prove that he is just as good as Varian, so upon seeing Varian's demonstration, claims that he can do just as well. Mateo is actually quite brilliant and succeeds at making a device that resembles Varian's both in appearance and behaviour. Moreover, he has made an improvement, and his machine does not consume the 1 lead bar that Varian's does (see figure below). Unfortunately though, it turns out that Mateo's machine has a limited number of uses before it explodes in a massive ball of flame. (There really is no "free lunch"). Both Varian and Mateo start with a single gold bar, but different numbers of lead bars. Varian invokes his device as many times as he can until he runs out of lead bars. Mateo is very careful not to destroy his machine, so he uses it sparingly, but he still wants to outdo Varian. Given the number of lead bars that each starts with, can you determine the minimum number of times Mateo will need to invoke his device in order to end with more gold bars than Varian? Input Format One line containing two integers and to denote the number of lead bars that Varian and Mateo start with respectively. Constraints pay close attention to the constraints in the uploaded photo please Output Format A single line containing the minimum number of steps Mateo needs to exceed Varian's gold. Sample Input 0 2 3 Sample Output 0 1 Explanation 0 Varian starts with 2 lead bars, so he gets to invoke his device twice. After the first time, he will have 1 lead bar left and 2 gold bars. After the second invocation, he gets 2 gold bars for each lead bar, but he has only 1 left, so he ends up with 2 gold bars in total (and no lead bars). Mateo starts with 3 lead bars, so after just a single invocation, he will have 3 gold bars, which is more than Varian was able to produce, so Mateo stops after only 1 invocation of his device. Sample Input 1 4 3 Sample Output 1 3 Explanation 1 Varian starts with 4 lead bars, and after the first invocation he has 3 lead bars and 4 (= 1 + 1 + 1 + 1) gold bars. After the second invocation, he has 2 lead bars and 12 (= 4 + 4 + 4) gold bars; after the third, he has 1 lead and 24 (= 12 + 12) gold bars, so he ends up with 24 gold bars by the time he runs out of lead bars. Mateo starts with 3 lead bars, so after the first invocation of his device, he will have 3 gold bars. He still has his 3 lead bars though, so after the second invocation, he has 9 (= 3 + 3 + 3) gold bars; but he still has not exceeded Varian's 24 gold bars yet, so he would need to continue to invoke his device. After one more time, he would then have 9 + 9 + 9 = 27 gold bars, which would exceed Varian's total. So, Mateo would need 3 invocations of his device, and we output 3 as the answer. here is the starting code use logs instead of factorials as recursive calls for factorial is too slow #!/bin/python3 import sys
Varian and Mateo are alchemists trying to outdo each other. Varian has created a magical device that converts lead into gold, and it works as follows. It has two receptacles. In the first, he places lead bars, in the second, he places one gold bar, and after muttering a magical incantation, the amazing device replicates whatever is in receptacle 2 as many times as there are lead bars in receptacle 1. Unfortunately though, there is a price to all this magic, and one of the lead bars in receptacle 1 gets consumed (see figure below). Varian doesn't mind too much though, because his device is built robustly, and he can just use it again with all the gold he already has in receptable 2, and the lead bars in receptacle 1.
Mateo has only recently completed his apprenticeship and wants to prove that he is just as good as Varian, so upon seeing Varian's demonstration, claims that he can do just as well. Mateo is actually quite brilliant and succeeds at making a device that resembles Varian's both in appearance and behaviour. Moreover, he has made an improvement, and his machine does not consume the 1 lead bar that Varian's does (see figure below). Unfortunately though, it turns out that Mateo's machine has a limited number of uses before it explodes in a massive ball of flame. (There really is no "free lunch").
Both Varian and Mateo start with a single gold bar, but different numbers of lead bars. Varian invokes his device as many times as he can until he runs out of lead bars. Mateo is very careful not to destroy his machine, so he uses it sparingly, but he still wants to outdo Varian.
Given the number of lead bars that each starts with, can you determine the minimum number of times Mateo will need to invoke his device in order to end with more gold bars than Varian?
Input Format
One line containing two integers and to denote the number of lead bars that Varian and Mateo start with respectively.
Constraints
pay close attention to the constraints in the uploaded photo please
Output Format
A single line containing the minimum number of steps Mateo needs to exceed Varian's gold.
Sample Input 0
Sample Output 0
Explanation 0
Varian starts with 2 lead bars, so he gets to invoke his device twice. After the first time, he will have 1 lead bar left and 2 gold bars. After the second invocation, he gets 2 gold bars for each lead bar, but he has only 1 left, so he ends up with 2 gold bars in total (and no lead bars).
Mateo starts with 3 lead bars, so after just a single invocation, he will have 3 gold bars, which is more than Varian was able to produce, so Mateo stops after only 1 invocation of his device.
Sample Input 1
Sample Output 1
Explanation 1
Varian starts with 4 lead bars, and after the first invocation he has 3 lead bars and 4 (= 1 + 1 + 1 + 1) gold bars. After the second invocation, he has 2 lead bars and 12 (= 4 + 4 + 4) gold bars; after the third, he has 1 lead and 24 (= 12 + 12) gold bars, so he ends up with 24 gold bars by the time he runs out of lead bars.
Mateo starts with 3 lead bars, so after the first invocation of his device, he will have 3 gold bars. He still has his 3 lead bars though, so after the second invocation, he has 9 (= 3 + 3 + 3) gold bars; but he still has not exceeded Varian's 24 gold bars yet, so he would need to continue to invoke his device. After one more time, he would then have 9 + 9 + 9 = 27 gold bars, which would exceed Varian's total.
So, Mateo would need 3 invocations of his device, and we output 3 as the answer. here is the starting code use logs instead of factorials as recursive calls for factorial is too slow
#!/bin/python3
import sys
def countInvocations(v, m):
# Complete this function
if __name__ == "__main__":
v, m = input().strip().split(' ')
v, m = [int(v), int(m)]
count = countInvocations(v, m)
print(count)
Step by step
Solved in 3 steps with 1 images
