A Bowling GameProblem code: G1 |
All submissions for this problem are available.
Mary and Johnny are playing a game with bowling pins. There is a row of N bowling pins. Mary and Johnny alternatively take their turn to bowl. They are such skillful bowling players that at each player's turn, any of them can take out any row of adjacent bowling pins, provided that the number of pins taken out is no more than K. It is important to notice that all the pins taken out must be adjacent. It is impossible to knock down pins separated by a greater distance. Whoever knocks out the last bowling pin wins the game.
You have just come down to watch Mary and Johnny playing the game. Some pins are already removed and now it is Mary's turn. With a good knowledge of mathematical games, you know that it is possible to compute in advance whether Mary or Johnny will win the game, provided that the winner always plays the perfect strategy. So why not impress your two friends by telling them who will win? If Mary could win the game, show her a winning move. Since Mary always wants to win the game as fast as possible, if there are more than one possible winning moves, show her the move that has the most number of pins taken out. If there are still several solutions, show her the move in which the pins taken out are as near to the left as possible.
Input
The first line contains t, the number of test cases (about 15). Then t test cases follow. Each test case has the following form:
- The first line contains two numbers N and K (1 <= N <= 2000, 1<= K <= 20)
- The second lines contains N characters 0 or 1 representing the row of N bowling pins. A character 0 means the bowling pin at the corresponding position is already taken out whereas a character 1 means the bowling pin is still in its position.
Each test case is separated by a blank line.
Output
For each of the test case, print either the string "Mary wins" or "Johnny wins" depending on who will win the game. If Mary could win the game, in the next line print N characters 0 or 1 representing the row of N bowling pins after Mary's move. Use the same format as that of the input data.
Remember to print a blank line after the output for each test case.
Example
Input: 3 3 2 111 8 3 10110111 8 4 11111111 Output: Mary wins 101 Johnny wins Mary wins 11000011
Output details
Case 1: Mary knocks down the middle pin. Regardless of which pin Johnny takes out in the next move, Mary always takes out the remaining pin and wins the game.
Case 2: Mary will lose the game regardless of which move she plays. For example if she takes out the rightmost pin, it is easy to verify that Johnny will always win if he then takes out the leftmost pin.
Case 3: There is more than one move that allows Mary to win the game. The four middle pins make the most number of pins that Mary can take out.
| Date: | 2009-08-15 |
| Time limit: | 2s |
| Source limit: | 50000 |
| Languages: | C C99 strict C++ PAS gpc PAS fpc JAVA NICE JAR C# C#2 NEM ST ASM D FORT ADA BASH PERL PYTH RUBY LUA ICON PIKE PHP SCM guile SCM qobi LISP sbcl LISP clisp SCALA HASK CAML CLPS PRLG WSPC BF ICK TEXT |
Comments
SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:
Fetching successful submissions
In sample testcase, t = 2.
In sample testcase, t = 2. Why are there 3 testcases?
This is fixed.
This is fixed.
How do I read input and right
How do I read input and right output for this problem in C#.
We can't help you with such
We can't help you with such queries while the contest is on.
In the output, the blank line
In the output, the blank line is after each testcase or between testcases?
You need to print a blank
You need to print a blank line after the output for each test case.
Is there a restriction
Is there a restriction that, every player should knock out at least one pin, every time?
I think this must be assumed to solve the problem, right?
There is no such restriction
There is no such restriction in the problem statement.
Admin, if you do not put the
Admin, if you do not put the restriction that, at least one pin should be knocked, the user might pass-on a losing situation to the other person, by knocking off nothing. And, this can continue till forever.
If i have understood
If i have understood correctly either player can knock down UPTO K adjacent pins right i.e they can take out 1..K pin as per their choice best suited for the game ?
AJ
"There is no such
"There is no such restriction in the problem statement."
Then for example the first game would never finish if Mary knocks down the middle pin, then Johnny do nothing, and in the next round if Mary knocks down a pin then Johnny wins, so she is also do nothing. And this continues.
Sorry for the goof-up. At
Sorry for the goof-up. At every turn Mary or Johnny has to knock down atleast one pin.
@Udaya Bhanu I guess it is
@Udaya Bhanu
I guess it is assumed as there is nothing mentioned about skipping turn. The other thing is that they are expert bowlers , that is mentioned so if they play they will take out atleast one pin.
i would like to know what is
i would like to know what is k here?
There's an image below the
There's an image below the question text which is not being displayed. (it shows an X)
From the page source, this image is
@Jeetendra No, even if Mary
@Jeetendra No, even if Mary knocks out the last 3 pins, she doesn't win.
@kartik 'k' is the maximum number of pins that can be knocked out as explained in the problem statement.
@Aiman Will check out the image issue.
in second case-10110111 if
in second case-10110111
if mary knocks last 3 pins, it becomes-
10110000
if john knocks the next two pins-
10000000
now mary can knock remaining and win the game.
why wont mary win if she
@ Zeeshan, Prashanth..... If
When is last date to submit
When is last date to submit ?
The contest ends on the 11th
The contest ends on the 11th of September at 15:00 hrs.
ya,i got it ani,i missed it
ya,i got it ani,i missed it out while reading the program,thank you
@codeChef, not able to
@codeChef,
not able to download my own code by clicking plain text after I view my solution, can you please fix it sometime?
@codechef admin : for case
@codechef admin :
for case 3: marry's move should be: 10000111
since it is mentioned in the problem that in case of several solution show her the move in which the pins taken out are as near to the left as possible. ..pls clarify this.
No, in that case Mary will
No, in that case Mary will not win.
Hi I'd like to know what
Hi
I'd like to know what kind of runtime error my code experiences (latest id 88855) . I see Runtime error (SIGSEGV) almost as soon as I submit. I see Runtime Error (Other), which I assume is too much memory (?) on the 'my submissions' page. The email I receive says NZEC. I'd really like to know which of the three it is.
Thanks!
It's the first one. You are
It's the first one. You are getting a segfault.
if the input is 6
if the input is
6 3
111111
can marry takes 2 pins from the most left and the state becomes 001111?
Yes, but that need not be the
Yes, but that need not be the winning move.
WHY ARE THERE ONLY PIIN NOT
WHY ARE THERE ONLY PIIN NOT IN THE LAST ROW