Loading...
Major Emrul & A Dream War
Time: 1 s
Memory: 125 MB
Our beloved Emrul bhai is stuck in a nightmare. To get back to his consciousness, he needs your help!

In the dream, he is a major (Salute to him) and in charge of a great war. In all wars, we need to see/know the movements of our enemy, right? To do that, He has K drones to investigate an enemy tower with N levels, each numbered from 1 to N.

The tower has a defence mechanism at a certain level D, where 0 <= D <= N, such that any drone flying above level D will be disabled by an energy shield, while drones scanning at or below level D will remain unharmed.
In each operation, you can send a drone to scan any level X (where 1 <= X <= N). If a drone encounters the energy shield, it becomes disabled and is no longer operational. If it doesn't encounter the shield, it can return for more reconnaissance missions.

Your task is to find the exact minimum number of operations required for Emrul bhai to identify level D with certainty? It might not be always possible to find a required number of operations. Let’s see if you can wake him up from this nightmare, so that he can come back to us.
Input
You will be given two integers -  K (Number of drones) and N (number of levels or floors the enemy tower has).
Constraint
0 <= K <= 100
1 <= N <= 10^4
Output
You need to output one integer number, the minimum number of operations required to identify the required level or floor with certainty. If it is impossible, you need to print "Sorry, Emrul Bhai :(" without quotes.
Examples
Input
Output
1 2
2
Input
Output
3 14
4
Notes
Explanation Of First Case
Emrul bhai starts by sending a drone to scan level 1. 
  1. If it encounters the energy shield and gets disabled, we know that D = 0.
  2. Otherwise, he sends the drone to scan level 2. If it encounters the shield and gets disabled, we know that D = 1.If the drone doesn't encounter the shield, then we know D = 2.
Hence, Emrul bhai needs a minimum of 2 drone operations to identify the exact level D with certainty.


Explanation Of Second Case
Emrul bhai starts by sending a drone to scan level 1. 
  1. If it encounters the energy shield and gets disabled, we know that D = 0.
  2. If the drone at level 1 doesn't encounter the shield, he then sends another drone to scan level 4. If it encounters the shield and gets disabled, we know that D = 2 or 3.
  3. If the drone at level 4 doesn't encounter the shield, he sends a third drone to scan level 9. If it encounters the shield and gets disabled, we know that D = 5 or 6 or 7 or 8.
  4. If the drone at level 9 doesn't encounter the shield, he sends a fourth drone to scan level 14. If it encounters the shield and gets disabled, we know that D = 10 or 11 or 12 or 13.
If the drone at level 14 doesn't encounter the shield, then we know D = 14.
Hence, Emrul bhai needs a minimum of 4 drone operations to identify the exact level D with certainty in this scenario.
 
Problem Info
Problem ID 196
Time Limit 1000 ms
Memory Limit 128000 KB
Moderators farhan_meb , abujafar492 , Alom_Shanto
Statistics
Submit
You need to Login or Registration for submit your solution