Game on Stick
All submissions for this problem are available.
Read problems statements in mandarin chinese, russian and vietnamese as well.
One free afternoon, Chef found an old board game in his kitchen. He decided to invite his friends Miron and Slava to come play it with him.
The board is a rectangular grid of size 2 × N. Initially, Miron and Slava each put their chips at a location (x1,y1 ) and (x2,y2 ) respectively. The game then proceeds as follows :
- Each player moves their chip in turns.
- In each turn, a player can move his chip to an adjacent cell that has not been visited by the other player before.
- Two cells are adjacent if they share a side
- A player can also skip his turn
- The cell that is initially occupied by a particular player's chip is considered visited by him
The outcome of the game is decided as follows :
- If a player manages to visit strictly more than half the total number of cells (i.e. visited at least N+1 cells), he immediately wins and the other player loses.
- if the game continued for more than 10100 turns without any player declared a winner yet then it becomes a draw.
Given that both players move optimally and Miron starts first, can you help Chef predict the winner of the game?
The first line contains a single integer T, the number of test cases. Each test case is described by a single line containing five space-separated integers N, x1, y1, x2, y2.
For each test case, output a single line with string Miron, Slava or Draw, denoting the answer to the problem.
- 1 ≤ T ≤ 105
- 1 ≤ N ≤ 1018
- 1 ≤ x1, x2 ≤ 2
- 1 ≤ y1, y2 ≤ N
- Cells (x1, y1) and (x2, y2) are different.
Input: 4 5 1 1 2 3 1 1 1 2 1 3 1 1 2 3 4 1 2 1 4 Output: Slava Draw Draw Miron
|Tags||cook85, game, medium, melnik|
|Time Limit:||2 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, kotlin, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.