JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
LongLongNim problem | Reply
It can be seen that whether a position is winning or losing depends only on the last k positions, where k is the maximum number of coins we can take away. While there are only 2^k possible values for the sequences of the length k, our sequence will become periodic....

Question: so if we find the 1>>k positions, use mode(%) operator can we find the rest of the results?
Re: LongLongNim problem (response to post by java2007fan) | Reply
I understood the recursive function to solve the SRM 330: LongLongNim . but it can only be used to solve the inputs upto 999(MaxN) I tried to memorize some values , but it didn't work out for test cases with MAxN =1000000000 This is my code for the recursive method.

	public boolean isWinning(int pos,int []moves){
		
		for(int i=0;i<moves.length;i++)
			if(pos-moves[i]>=0&&!isWinning(pos-moves[i],moves)) 
				return true;
		return false;
	}
 
 
	public int numberOfWins(int pos,int [] moves){
		int cnt=0;
		for(int i=1;i<=pos;i++)
			if(!isWinning(i,arr))
				cnt++;
		return cnt;
	}


Please help me.
Re: LongLongNim problem (response to post by java2007fan) | Reply
You may need to read my article about impartial games problems, i think it will help you alot solving such types of problems.

http://se7so.blogspot.com/2012/10/impartial-games-problems.html

Thanks,
Hussein
RSS