Unfair Game
Problem Statement :
You are playing a game of Nim with a friend. The rules are are follows: 1) Initially, there are N piles of stones. Two players play alternately. 2) In each turn, a player can choose one non empty pile and remove any number of stones from it. At least one stone must be removed. 3) The player who picks the last stone from the last non empty pile wins the game. It is currently your friend's turn. You suddenly realize that if your friend was to play optimally in that position, you would lose the game. So while he is not looking, you decide to cheat and add some (possibly 0) stones to each pile. You want the resultant position to be such that your friend has no guaranteed winning strategy, even if plays optimally. You cannot create a new pile of stones. You can only add stones, and not remove stones from a pile. What is the least number of stones you need to add? Input Format The first line contains the number of cases T. T cases follow. Each case contains the number N on the first line followed by N numbers on the second line. The ith number denotes si, the number of stones in the ith pile currently. Constraints 1 <= T <= 20 2 <= N <= 15 1 <= si < 1000000000 (10^9) Output Format Output T lines, containing the answer for each case. If the current position is already losing for your friend, output 0.
Solution :
Solution in C :
In C++ :
#include<map>
#include<ctime>
#include<cmath>
#include<queue>
#include<vector>
#include<cstdio>
#include<string>
#include<cstring>
#include<cassert>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
int d[16];
LL dp[35][1 << 15];
const LL Inf = 30000000000LL;
inline void CheckMin(LL& a, LL b) {
if(a > b) a = b;
};
int dd[16];
int main() {
int T, n;
cin >> T;
while(T--) {
cin >> n;
for(int i = 0; i < n; i++)
cin >> d[i];
int tot = 1 << n;
for(int i = 0; i <= 32; i++)
for(int j = 0; j < tot; j++)
dp[i][j] = Inf;
dp[31][0] = 0;
for(int i = 30; i >= 0; i--) {
int one = 0;
for(int j = 0; j < n; j++)
if(d[j] & (1 << i)) one++;
if(dp[i + 1][0] < Inf) {
for(int j = 0; j < tot; j++) {
int ok = 1;
LL val = 0;
int ct = 0;
for(int k = 0; k < n; k++) {
if(!(j & (1 << k))) continue;
if(d[k] & (1 << i)) {
ok = 0;
break;
}
ct++;
val += (1 << i) - d[k] % (1 << i);
}
if(!ok || (one + ct) % 2 || val >= Inf) continue;
CheckMin(dp[i][j], dp[i + 1][0] + val);
}
}
for(int j = 1; j < tot; j++) {
if(dp[i + 1][j] >= Inf) continue;
int ct = 0;
for(int k = 0; k < n; k++) {
if(!(j & (1 << k)) && (d[k] & (1 << i))) ct++;
}
if(ct % 2) {
CheckMin(dp[i][j], dp[i + 1][j] + (1 << i));
for(int k = 0; k < n; k++) {
if(!(j & (1 << k)) && ((d[k] & (1 << i)) == 0)) {
int ns = j | (1 << k);
int cost = (1LL << i) - d[k] % (1 << i);
CheckMin(dp[i][ns], dp[i + 1][j] + cost);
}
}
} else {
CheckMin(dp[i][j], dp[i + 1][j]);
}
}
}
LL ret = Inf;
for(int i = 0; i < tot; i++) {
if(ret > dp[0][i]) ret = dp[0][i];
}
cout << ret << endl;
}
system("pause");
return 0;
}
In Java :
import java.util.Arrays;
import java.util.Scanner;
/*
* To change this template, choose Tools | Templates and open the template in
* the editor.
*/
/**
*
* @author muoi
*/
public class Solution {
public static long MAX_BIT = 32;
public static long n;
static long a[] = new long[100];
static long b[] = new long[100];
static long c[] = new long[100];
static long dd[] = new long[100];
static long bitCheck(long a, long b) {
return ((a) & (1l << (b)));
}
static long bitSet(long a, long b) {
return ((1l << (b)));
}
static long check() {
long res = 0l;
Arrays.fill(c, 0);
long sl = 0;
for (long bb = MAX_BIT; bb >= 0; --bb) {
sl = 0;
Arrays.fill(dd, 0l);
for (int i = 0; i < n; ++i) {
if (bitCheck(a[i], bb) != 0l) {
if (c[i] <= a[i]) {
sl++;
c[i] |= bitSet(c[i], bb);
dd[i] = 1;
if (sl > b[(int)bb]) {
return -1;
}
}
}
}
for (long ii = 0; ii < b[(int)bb] - sl; ++ii) {
long mn = Long.MAX_VALUE;
long pos = 0;
for (long j = 0; j < n; ++j) {
if (dd[(int)j] == 0) {
long temp = c[(int)j];
temp |= bitSet(temp, bb);
if (temp - a[(int)j] < mn) {
mn = temp - a[(int)j];
pos = j;
}
}
}
dd[(int)pos] = 1l;
c[(int)pos] |= bitSet(c[(int)pos], bb);
}
}
for (long i = 0; i < n; ++i) {
res += (c[(int)i] - a[(int)i]);
}
return res;
}
static void process() {
if (n % 2 == 0) {
Arrays.fill(b, n);
} else {
Arrays.fill(b, n - 1);
}
long mn = Integer.MAX_VALUE;
for (long bb = MAX_BIT; bb >= 0; --bb) {
while (true) {
long temp = check();
if (temp != -1) {
if (b[(int)bb] > 0) {
b[(int)bb] -= 2;
} else {
break;
}
} else {
b[(int)bb] += 2;
break;
}
}
long temp = check();
if (temp != -1) {
if (temp < mn) {
mn = temp;
}
}
}
System.out.println(mn);
}
public static void main(String args[]) {
long ntest;
Scanner scanner = new Scanner(System.in);
ntest = scanner.nextLong();
for (; ntest-- > 0;) {
n = scanner.nextLong();
for (long i = 0; i < n; ++i) {
a[(int)i] = scanner.nextLong();
}
process();
}
}
}
In C :
#include<stdio.h>
typedef long long i64;
int main()
{
int T;
scanf("%d", &T);
for (; T > 0; T--)
{
int n, i, j;
i64 result = 0;
int tmp, max, ind;
i64 s[16];
scanf("%d", &n);
for (i = 0; n > i; i++)
{
scanf("%d", s + i);
result += *(s + i);
}
while (1)
{
int bitcount[64]={0};
for (i = 31; i >= 0; i--)
{
int i0 = 0, i1;
for (j = 0; j < i; j++)
{
i0 <<= 1;
i0 += 1;
}
i1 = i0;
i1 <<= 1;
i1 += 1;
tmp = 0;
for (j = 0; j < n; j++)
{
tmp += ((s[j] >> i) & 1);
}
bitcount[i]=tmp;
if (tmp % 2 == 1 && tmp < n)
{
j = 0;
max = 0;
while (j < n)
{
if (((s[j] >> (i)) & 1) < 1 && (max <= (s[j] & i0)))
{
max = (s[j] & i0);
ind = j;
}
j++;
}
j = ind;
s[j] >>= i;
s[j] += 1;
s[j] <<= i;
break;
}
if (tmp%2==1&&tmp == n)
{
int k=0;
j = 0;
max = 0;
k=i+1;
while(bitcount[k]==n-1)k++;
i1=0;
for (j = 0; j < k; j++)
{
i1 <<= 1;
i1 += 1;
}
j=0;
while (j < n)
{
if (((s[j] >> (k)) & 1) < 1
&& (max <= (s[j] & i1)))
{
max = (s[j] & i1);
ind = j;
}
j++;
}
j = ind;
s[j] >>= (k);
s[j] += 1;
s[j] <<= (k);
break;
}
}
if (i < 0)
break;
}
for (i = 0; i < n; i++)
result -= s[i];
printf("%lld\n", -result);
}
return 0;
}
In Python3 :
#!/bin/python3
import os
import sys
#
# Complete the unfairGame function below.
#
def unfairGame(s):
nimSum = 0
for i in s:
nimSum ^= int(i)
if(nimSum == 0):
return 0
# if(nimSum == 1):
# modlist = [x % 2 for x in s]
# if min(modlist) == 0:
# s[modlist.index(0)] += 1
# else:
# s[0] += 1
# return 1 + unfairGame(s)
print(s)
divider = 2 ** (len(bin(nimSum)) - 3)
print(divider)
modlist = [x % divider if x % (2 * divider) < divider else -1 for x in s]
print(modlist)
if max(modlist) < 0:
s[s.index(max(s))] += divider
return divider + unfairGame(s)
increaseNumber = max(modlist)
increase = divider - increaseNumber
print(increase)
s[modlist.index(increaseNumber)] += increase
print(s)
print()
return increase + unfairGame(s)
if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')
t = int(input())
nums =[1, 10, 10, 15, 27, 4, 9, 12, 26, 9, 14, 3, 25, 23, 3, 10, 3, 5, 13, 18]
for i in nums:
print(i)
for t_itr in range(t):
s_count = int(input())
s = list(map(int, input().rstrip().split()))
s.sort()
result = unfairGame(s)
fptr.write(str(result) + '\n')
fptr.close()
View More Similar Problems
Insert a Node at the head of a Linked List
Given a pointer to the head of a linked list, insert a new node before the head. The next value in the new node should point to head and the data value should be replaced with a given value. Return a reference to the new head of the list. The head pointer given may be null meaning that the initial list is empty. Function Description: Complete the function insertNodeAtHead in the editor below
View Solution →Insert a node at a specific position in a linked list
Given the pointer to the head node of a linked list and an integer to insert at a certain position, create a new node with the given integer as its data attribute, insert this node at the desired position and return the head node. A position of 0 indicates head, a position of 1 indicates one node away from the head and so on. The head pointer given may be null meaning that the initial list is e
View Solution →Delete a Node
Delete the node at a given position in a linked list and return a reference to the head node. The head is at position 0. The list may be empty after you delete the node. In that case, return a null value. Example: list=0->1->2->3 position=2 After removing the node at position 2, list'= 0->1->-3. Function Description: Complete the deleteNode function in the editor below. deleteNo
View Solution →Print in Reverse
Given a pointer to the head of a singly-linked list, print each data value from the reversed list. If the given list is empty, do not print anything. Example head* refers to the linked list with data values 1->2->3->Null Print the following: 3 2 1 Function Description: Complete the reversePrint function in the editor below. reversePrint has the following parameters: Sing
View Solution →Reverse a linked list
Given the pointer to the head node of a linked list, change the next pointers of the nodes so that their order is reversed. The head pointer given may be null meaning that the initial list is empty. Example: head references the list 1->2->3->Null. Manipulate the next pointers of each node in place and return head, now referencing the head of the list 3->2->1->Null. Function Descriptio
View Solution →Compare two linked lists
You’re given the pointer to the head nodes of two linked lists. Compare the data in the nodes of the linked lists to check if they are equal. If all data attributes are equal and the lists are the same length, return 1. Otherwise, return 0. Example: list1=1->2->3->Null list2=1->2->3->4->Null The two lists have equal data attributes for the first 3 nodes. list2 is longer, though, so the lis
View Solution →