A Numbers GameProblem code: ICODER1 |
All submissions for this problem are available.
Two kids John and Matthew are playing a game involving a grid of numbers where John must guess the number chosen by Matthew. The numbers are arranged in a grid. Now, inorder to predict the correct number, John asks Matthew to tell him the column number of the grid where his number lies. John then, keeping the same grid size, starts re-arranging the grid row-wise and keeps repeating the process of asking and arranging till he gets to the number. For example:
If the initial grid of numbers was:
9 1 5
2 3 6
7 17 10
13 20 4
8 11 15
18 21 12
14 16 19
Assuming that Matthew chose '15', which corresponds to the third column, implying that the number could be in the set { 5, 6, 10, 4, 15, 12, 19 }. To narrow down his result to one number, John arranges the numbers row-wise:
9 2 7
13 8 18
14 1 3
17 20 11
21 16 5
6 10 4
15 12 19
He again asks Matthew about the column his number corresponds to, i.e. the first column this time, this allows John to narrow down his result further to the set { 6, 15 }. He continues this column asking and row-wise arranging till he gets to the number.
Given rows and columns, what must be the number of column-asking that would assure that John is able to guess the number assuming that the initial position of the number was not known. Incase an answer is not possible print -1.
Notes
- You must consider the worst position of the number i.e. the position which would require maximum number of steps.
Constraints
- Consider that the grid consists of all distinct numbers.
Input
1. Number of test cases = 'T' ( 1 <= T <= 1000 ). T lines follow, one line for each test case.
2. Each line( representing the size of the grid ) would contain rows = 'R' followed by columns = 'C' ( 1 <= R <= 105, 1 <= C <= 105 ).
Output
1. Return the column-asking required, in order to get to the number, on a new line.
Example
Input: 2 7 3 8 10 Output: 3 2
| Author: | csirubix |
| Date Added: | 20-03-2010 |
| Time Limit: | 1 sec |
| Source Limit: | 50000 Bytes |
| Languages: | ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, ERL, F#, FORT, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TEXT, WSPC |
Comments
SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:
Fetching successful submissions
Could not find any info about
Could not find any info about this contest on google.
Can anybody tell??
I was just testing the
I was just testing the problems, my submission doesn't count. You can post your queries here...
Please tell the details
Please tell the details about this contest....
CSI-Mumbai Chapter event IT
CSI-Mumbai Chapter event
IT is being organised by Thadomal Shahani Engineering college
It is a part of the International Student Convention iDeate '10
where to register for this
where to register for this contest??
you can directly take part,
you can directly take part, no need to register
no need...if u win...we will
no need...if u win...we will take ur details from here itself
its hving any cash prize??
its hving any cash prize??
yes for first and second
yes for first and second place...cant reveal now
The contest has been extended
The contest has been extended up to 6 p.m.
grid has to be dynamically
grid has to be dynamically created or static as per my wish in any order?
Well... based on rows and
Well... based on rows and columns you have to find the column asking. Its quite clear, please read carefully.
are m asking k the nos in the
are m asking k the nos in the grid..how do i generate them..or do i take them from user?.
is there a trick to get to the solution or ll have to code:P
I know what you are asking...
I know what you are asking... its obvious that if there was something extra required to be done I would have mentioned it!
There may be a case where
There may be a case where there wont be any column asking required !
too tough :(
too tough :(
hey may be you should try
hey may be you should try more, read the problem carefully and break it into some cases. You may get it eventually...
beyond the given input what
beyond the given input what other test cases are used?
The contest has been extended
The contest has been extended up to 8 p.m.
Sorry I didn't understand you
Sorry I didn't understand you question
your*
your*
bye bye
bye bye
is there bound checking?
is there bound checking?
why am i getting wrong answer
why am i getting wrong answer when i have right answer?
ur program must be failing
ur program must be failing for some test case
tell me the test case rather
tell me the test case rather than the 2 given?
Input: 19 4 Output: 4
Input:
19 4
Output:
4
can the admin tell me for
can the admin tell me for which cases the o/p is failing for my recent submisiion?
I am really sorry, even we
I am really sorry, even we cant see your solutions at the moment. I may help you after the contest... Let me know your email address for that. But as of now, try to break down your cases and read the comments of this section as well...
ok for 20 10 ans is 10 or 11?
ok for 20 10 ans is 10 or 11? just tell me this?
Sorry I can't tell you the
Sorry I can't tell you the answer. I don't think I should be telling you this also, but both are incorrect...
Hi I dont have any kids...can
Hi I dont have any kids...can I still take part
I think john and mathew are
I think john and mathew are more interested in snakes and ladders rathar than this no. game....can I write a program for that......