oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

samenim Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

samenim.html

Problem Description

Mr. Panda and Rar the Cat have been playing the very common game of Nim. The game of Nim works as follows. The game starts with N piles of stones and in the two players play alternately. In every move, a player will select a pile of stones and take any number of stones they want from that pile. The player who takes the last stone wins.

After playing many games, the intelligent Mr. Panda and Rar the Cat have figured out what the winning conditions are and the winning strategies for each player so the game becomes very boring. Hence, they decide to vary the game. They add an additional rule that after every move, there must be at least 2 piles with the same number of stones, possibly 0. The first player who does not have a valid move will lose. After playing and investigating many rounds, they hypothesised that if the first player had a "pass" that he can use within the first floor(sqrt(N)) moves, the first player will always win. They decide to have you play the game with them to prove this hypothesis.

Implementation

Your will be playing as the first player and will be playing with a computer program in alternate moves. Your code must implement the following 2 functions

void init(int N, int A[]): Initialisation function with the initial state given. N is the number of piles and A[0],A[1]...A[N-1] represent the number of stones in piles 1,2,...,N respectively. It is guaranteed that in the initial state, there will be 2 piles that have the same number of stones.

pair <int,int> move(int N, int A[])It is your turn and the state is provided as described above. Make a move by returning a pair<int,int> whose first number is the pile you want to remove from, in the range 1,2,...,N, the second number is the number of stones. If you want to pass, return (0,0) and no stones will be removed

It is guaranteed that your opponent will always make a valid move and takes negligible time to make the move. If you make an invalid move such as returning a pile number out of range, taking more stones than there are in the pile, passing after making floor(sqrt(N)) moves or passing more than once, you automatically lose. The game will automatically end when one of the players makes the last valid move. You will only get marks for a subtask if you win all the games and it is guaranteed that you can always win if you play optimally. You may use the template samenim.cpp provided if you wish. If not, please remember to include the library "samenim.h" in your code.

Subtasks

Subtask 1(7%): 2 ≤ N ≤ 5, the total number of stones will not exceed 10

Subtask 2(19%): 2 ≤ N ≤ 10, the total number of stones will not exceed 20

Subtask 3(31%): 2 ≤ N ≤ 100, the total number of stones will not exceed 200

Subtask 4(43%): 2 ≤ N ≤ 1000, the total number of stones will not exceed 10000

Subtask 5(0%): Sample Test Case

Sample Test Case

The sample test case involves 3 piles of stones with 1,2,1 stones in each pile respectively. A possible game could go like this.

Player 1: pass

Player 2: [1,1,1]

Player 1: [1,1,0]

Player 2: [0,1,0]

Player 1: [0,0,0]

In this case, player 1 wins the game.

Tags

Game Theory

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
17101s32MBMinimum
219101s32MBMinimum
331101s32MBMinimum
443101s32MBMinimum
5011s32MBMinimum

Attachments

Attachment Filesize Last Updated
samenim.h86B19 Dec 2013, 13:03:48
ans.cpp158B19 Dec 2013, 12:53:17

Judge Compile Command

g++-8 grader.cpp ans.cpp -o samenim -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.