Soluție HackerRank pentru Introduction to Nim Game. Include cerința formatată, exemple, explicația pașilor și cod sursă.

  • Problemă: Introduction to Nim Game

Cerinta completa

Nim is the most famous two-player algorithm game. The basic rules for this game are as follows:

  • The game starts with a number of piles of stones. The number of stones in each pile may not be equal.
  • The players alternately pick up or more stones from pile
  • The player to remove the last stone wins.

For example, there are piles of stones having stones in them. Play may proceed as follows:

Player  Takes           Leaving
                        pile=[3,2,4]
1       2 from pile[1]  pile=[3,4]
2       2 from pile[1]  pile=[3,2]
1       1 from pile[0]  pile=[2,2]
2       1 from pile[0]  pile=[1,2]
1       1 from pile[1]  pile=[1,1]
2       1 from pile[0]  pile=[0,1]
1       1 from pile[1]  WIN

Given the value of and the number of stones in each pile, determine the game’s winner if both players play optimally.

Function Desctription

Complete the nimGame function in the editor below. It should return a string, either First or Second.

nimGame has the following parameter(s):

  • pile: an integer array that represents the number of stones in each pile

Input Format

The first line contains an integer, , denoting the number of games they play.

Each of the next pairs of lines is as follows:

  1. The first line contains an integer , the number of piles.
  2. The next line contains space-separated integers , the number of stones in each pile.

Constraints

  • Player 1 always goes first.

Output Format

For each game, print the name of the winner on a new line (i.e., either First or Second).

Sample Input

2
2
1 1
3
2 1 4

Sample Output

Second
First

Explanation

In the first case, there are piles of stones. Player has to remove one pile on the first move. Player removes the second for a win.

In the second case, there are piles of stones. If player removes any one pile, player can remove all but one of another pile and force a win. If player removes less than a pile, in any case, player can force a win as well, given optimal play.

Limbajul de programare folosit: java8

Cod:


// https://en.wikipedia.org/wiki/Nim#Proof_of_the_winning_formula

import java.util.Arrays;
import java.util.Scanner;

public class Solution {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int g = sc.nextInt();
		for (int tc = 0; tc < g; tc++) {
			int n = sc.nextInt();
			int[] piles = new int[n];
			for (int i = 0; i < piles.length; i++) {
				piles[i] = sc.nextInt();
			}

			System.out.println(solve(piles));
		}

		sc.close();
	}

	static String solve(int[] piles) {
		return Arrays.stream(piles).reduce((result, pile) -> result ^ pile).getAsInt() != 0 ? "First" : "Second";
	}
}

Scor obtinut: 1.0

Submission ID: 464603628

Link challenge: https://www.hackerrank.com/challenges/nim-game-1/problem

Introduction to Nim Game