E  Guess the Number

All submissions for this problem are available.
Chef has a sorted array $A$ of size $N$ consisting of $distinct$ elements which you $\text{donâ€™t know}.$ You will be provided with an integer $X$. You have to check whether $X$ exists in Chef's array or not. If it exists, find out at which index it exists. You can ask just $\text{one}$ type of query as follows $:$ You can ask atmost $q$ such queries. If you ask a question for an index say $m$, then Chef returns the sum of $K$ elements of his array starting from index $m$, where $\text{K =}$ $2^i$ and $i$ is the maximum value of $integer$ such that $m$ is perfectly divisible by $K$. For Example, if $m = 13$ then $K$ is $1$, if $m = 8$ then $K$ is $8$, if $m = 12$ then $K$ is $4$. So, if say $m$ is 12, i.e. $K$ is 4, Chef will return sum of A[12] + A[13] + A[14] + A[15].  $NOTE$  If you will ask for index greater than $N$ then Chef will return $0$.  $NOTE$  As for any query Chef will return sum of array elements from $m$ to $m+K1$. So if $m+K1$ gets larger than $N$ then Chef will return sum upto last element of the array. $\text{For eg : }$ If size of array is 26 and $K$ for $\text{m = 16}$ is $16$, so $m + K  1$ is $31$. Chef will return sum of A[16 : 26]. ###Interaction:  First, you should read a line containing a single integer $T$ denoting the number of test cases. The description of interaction for $T$ test cases follows  For every test case, you have to read two space separated integers $\text{N and X}$, for $\text{subtask 2, N is unknown}$ so when $\text{N is 1}$ consider you don't know $N$.  For each test case, you should start by asking questions as follows  To ask a question, print a line containing two space separated integer $1$ and $m$.  Then, you must read a line containing a single integer.  When you think you know index of $X$ in Chef's array, print a line containing two space separated integers $2$ and index of $X$.  If $X$ is not present in Chef's array, print a line containing two space separated integers $2$ and $1$.  Then, you must read a line containing a single string $Yes$ or $No$. If this string is $Yes$, you should continue solving the remaining test cases, otherwise your answer was incorrect and you should immediately terminate your program to receive the $\text{Wrong Answer}$ verdict.  Don't forget to flush the output after printing each line! ###Constraints  $1 \leq T \leq 10$  $1 \leq N \leq 10^6$  $1 \leq X \leq 10^6$  $1 \leq A[i] \leq 10^6$ ###Subtasks  30 points : $\text{N is known}$.  $1 \leq N \leq 10^3$  You can ask at most max(44, N) queries. That is, $q = max(44, N).$  30 points : $\text{N is known}$  $1 \leq N \leq 10^5$  $q = 44$  65 points : $\text{N is unknown (N = 1)}$  $1 \leq N \leq 10^6$  $q = 44$ ###Example: You Grader 1 7 8 1 3 8 2 3 YesAuthor:  raushan303 
Editorial  https://discuss.codechef.com/problems/GTN 
Tags  bit22019, raushan303 
Date Added:  1082019 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, SQL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 