Balls and Holes

View as PDF

Submit solution

Points: 0.90 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

This is an interactive problem.

Alice and Bob are playing a game. There are ~n~ empty holes in a row, numbered from ~1~ to ~n~ from left to right. Initially, each of the last ~k~ holes has a ball in it. Alice goes first, and they take turns making moves as follows:

  • Choose a ball that has at least one empty hole to its left.

  • Move this ball to any empty hole to its left. Note that you can move the ball past other balls.

The first player to move all the balls to the first ~k~ holes wins. Knowing that both players play optimally, you need to play as one of the two players and win the game.


The first line contains an integer ~t~ (~1 \le t \le 50~) — the number of test cases.

Each of the next ~t~ lines contains two integers ~n~ and ~k~ (~1 \le k < n \le 1000~, ~1 \le k \le 50~) — the number of holes and the number of balls for each test case.

You should begin the interaction for each test case after reading ~n~ and ~k~.

The sum of ~n~ over all test cases does not exceed ~1000~.


To start the interaction, print Alice or Bob on a line corresponding to the person you want to play as.

Consider moving a ball from hole ~x~ to hole ~y~. This move is considered invalid if one of the following occurs:

  • ~x > n~ or ~x \le y~ or ~y \le 0~.
  • Hole ~x~ is empty.
  • Hole ~y~ already has a ball.

When it's your turn, print your move in the form of "move ~x\ y~".

When it's the judge's turn, read in the judge's move in the form of "~cmd\ x\ y~".

  • ~cmd=~ move: The judge makes the move ~(x, y)~.
  • ~cmd=~ end: The game ends.

    • ~x=y=-1~: The judge cannot make a valid move and you win. In this case, your program should move on to the next test case or stop immediately if all test cases have been processed.
    • Otherwise: The judge makes the final move ~(x, y)~ and wins. In this case, your program should stop immediately.
  • If ~cmd=~ invalid: In the previous turn, you made an invalid move. You should stop your program immediately.

After printing the player you are playing as or a move, do not forget to output the end of line and flush the standard output, or you may receive a Time limit exceeded verdict. To do this, you can use:

  • fflush(stdout) or cout.flush() in C++;
  • System.out.flush() in Java;
  • flush(output) in Pascal;
  • stdout.flush() in Python;
  • see the documentation for other languages.


Subtask Score Constraints
1 750 ~k\le 2~
2 750 ~n\le 20~
3 1250 No additional constraints
Total 2750

Sample interaction

Standard input Standard output Explanation The state of the balls
1 There is only one test case
5 2 In the first test case, ~n = 5~, ~k = 2~ _ _ _ * *
Alice The participant chooses to play as Alice _ _ _ * *
move 5 3 Alice moves a ball from position ~5~ to ~3~ _ _ * * _
move 3 2 Bob moves a ball from position ~3~ to ~2~ _ * _ * _
move 4 1 Alice moves a ball from position ~4~ to ~1~ * * _ _ _
end -1 -1 Bob concedes defeat * * _ _ _


Please read the guidelines before commenting.

There are no comments at the moment.