You are not logged in. Please login at www.codechef.com to post your questions!

×

JAGAM Editorial

PROBLEM LINK:

Practice
Contest

Author: Aleksa Plavsic
Tester: Hussain Kara Fallah
Editorialist: Hussain Kara Fallah

PROBLEM

Vanja and Miksi are playing a game on N integer numbers. There is a counter S which is equal to 0 at the beginning. At each turn, each player picks a number from the array and either subtract it or add it to S. You are given also 2 numbers Z1, Z2. Whenever the counter is equal to one of them the player who played the last move wins. At least one turn should be played.

Assuming both players are playing optimally you have to determine the winner. In some cases, none of the players can win the game and if they are playing optimally it may last for more than 1010 turns. In such case, you need to tell that the game ends in a tie. Vanja starts the game.

DIFFICULTY

EASY

EXPLANATION

If our array contains any of these values {Z1, Z2, -Z1, -Z2}, then the first player can win by 1 move.

Let's introduce the term dead end. Whenever a player has his turn and he is not able to win in 1 move and no matter what number he chooses the other player can pick a number and make S equal to Z1 or Z2, then our player is in a dead end.

We need to check if Vanja's first move is a dead end. In case it's, then Miksi is the winner. Otherwise, we are sure that the game will last for more than 2 turns.

In such case (more than 2 rounds), we can prove that the game ends in a tie. No matter which player is taking the turn (since each player knows the numbers given and Z1, Z2), he can determine whether he is in a dead end or not. In case he is, he can just play exactly the opposite of the move the last player did and avoid losing the game (and since the previous player couldn't win at his previous turn, the game lasts forever).

AUTHOR'S AND TESTER'S SOLUTIONS:

Author's solution can be found here.

Tester's/Editorialist's solution can be found here.

asked 27 Aug '18, 05:38

deadwing97's gravatar image

3★deadwing97
1181234
accept rate: 0%

edited 09 Sep '18, 16:04

admin's gravatar image

0★admin ♦♦
19.8k350498541

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×968
×140
×32

question asked: 27 Aug '18, 05:38

question was seen: 917 times

last updated: 09 Sep '18, 16:04