DCEPC504 - The Indian Connection
Rajesh Kuthrapali has a weird family structure. Every male member gives birth to a male child first and then a female child whereas every female member gives birth to a female child first and then to a male child. Rajesh analyses this pattern and wants to know what will be the Kth child in his Nth generation. Help him.
- Every member has exactly 2 children.
- The generation starts with a male member(Rajesh).
- In the figure given below:
M-------- 1st generation
M F ------- 2nd generation
/ \ / \
M F F M
3rd child of 3rd generation
First line specifies T, the number of test cases.
Next T lines each gives 2 numbers, N and K.
Output 1 line for each test case giving the gender of the Kth child in in Nth generation.
Print “Male” for male “Female” for female (quotes only for clarification).
1 <= T <=100
1 <= N <=10000
1 <= K <= min(10^15, 2^(n-1))
Input: 4 1 1 2 1 2 2 4 5 Output: Male Male Female Female
Applied binary search,didn't expect to get Accepted.
I made my own power function(binary exponentiation) and got TLE then I used c++ standar pow() and got accepted ... thanks to @Shashank Garg
Apply recurrence relation
thue morse series
no recursion ... loop only :)
accepted ...after 1 WA.
O(1); but an extra WA for initially using the wrong builtin.
Simple recursion! :)
Mapppppppps :p AC in one go :P
|Added by:||dce coders|
|Cluster:||Cube (Intel G860)|
|Languages:||ASM32-GCC MAWK BC C-CLANG C C++ 4.3.2 CPP CPP14 CPP14-CLANG COBOL COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH GOSU GRV JAVA JS-MONKEY KTLN NIM NODEJS OBJC OBJC-CLANG OCT PICO PROLOG PYPY PY_NBC R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA VB.NET|