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.
Note:
- 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
Input
First line specifies T, the number of test cases.
Next T lines each gives 2 numbers, N and K.
Output
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).
Constraints
1 <= T <=100
1 <= N <=10000
1 <= K <= min(10^15, 2^(n-1))
Example
Input: 4 1 1 2 1 2 2 4 5 Output: Male Male Female Female
hide comments
vineetjai:
2021-10-01 16:10:26
recursion or loop both works but don't try to do 1<<n because 1 <= N <=10000. |
|
black_shroud:
2020-04-21 12:16:07
log(n) sol
|
|
maratha:
2019-07-29 09:26:59
Applied binary search,didn't expect to get Accepted.
|
|
manjeet_:
2018-08-08 16:51:59
I made my own power function(binary exponentiation) and got TLE then I used c++ standar pow() and got accepted ... thanks to @Shashank Garg |
|
mag1x_:
2018-06-14 19:07:47
https://en.wikipedia.org/wiki/Thue%E2%80%93Morse_sequence
|
|
ajayc1007:
2018-06-11 13:13:37
Apply recurrence relation
|
|
hunnychauhan:
2017-07-11 20:58:36
thue morse series
|
|
ashishranjan28:
2017-05-20 13:32:21
no recursion ... loop only :) |
|
code96maker:
2017-04-02 20:25:07
accepted ...after 1 WA.
|
|
cake_is_a_lie:
2017-03-02 05:37:54
O(1); but an extra WA for initially using the wrong builtin. |
Added by: | dce coders |
Date: | 2012-04-18 |
Time limit: | 1.726s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | ASM32-GCC MAWK BC C-CLANG C NCSHARP C++ 4.3.2 CPP CPP14 CPP14-CLANG COBOL COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH GOSU GRV JAVA JS-MONKEY JULIA KTLN NIM NODEJS OBJC OBJC-CLANG OCT PICO PROLOG PYPY PYPY3 PY_NBC R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA VB.NET |
Resource: | Own Problem |