We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
importoperatorfromfunctoolsimportreducedefxor(nums):returnreduce(operator.xor,nums,0)deflowZero(v):"""position of the lowest 0"""p=0whileTrue:m=1<<pifv&m==0:returnpp+=1defhighOne(v):"""position of the highest 1"""p=0high=Nonewhilev!=0:m=1<<pifv&m!=0:high=pv&=~mp+=1returnhighdefzeroAt(v,p):"""true if v has 0 at position p"""returnv&(1<<p)==0defdiffToFlip(v,p):"""how much to add to flip the bit at p and clear below it"""t=1<<pr=(v+t)&~(t-1)returnr-vdeflowPosWithMoreThanOneZero(nums):"""lowest position where more than one number has 0"""p=0whileTrue:m=1<<pn=sum(1ifv&m==0else0forvinnums)ifn>1:returnpp+=1defpairs(n):return((i,j)foriinrange(0,n-1)forjinrange(i+1,n))"""pile fixers"""deffixPiles(piles):"""add minimum number of counters to piles to make them a staple nim position"""highOneP=highOne(xor(piles))ifhighOneP==None:#thepilesareinawinningpositionr=pileselifany(zeroAt(v,highOneP)forvinpiles):r=fixPilesWithZeroAtHigh(piles)else:r=fixPilesWithoutZeroAtHigh(piles,highOneP)returnrdeffixPilesWithZeroAtHigh(piles):"""fix piles that have a pile with zero at the high 1-bit position"""piles=list(piles)whileTrue:highOneP=highOne(xor(piles))"""see if the piles are fixed to a winning position"""ifhighOneP==None:returnpiles"""choose a pile with 0 at the high 1 position with min to add to flip that 0"""candidates=[(i,diffToFlip(v,highOneP))fori,vinenumerate(piles)ifzeroAt(v,highOneP)]winner=min(candidates,key=operator.itemgetter(1))"""add to the winning pile"""i,add=winnerpiles[i]+=addreturnpilesdeffixPilesWithoutZeroAtHigh(piles,highOneP):"""fix piles that do not have a pile with zero at the high 1-bit position""""""high piles are piles' bits above highOneP"""highPiles=[v>>(highOneP+1)forvinpiles]"""decorate each high pile the position of the first 0, same as the numberoftrailingones"""highPilesZ=[(v,lowZero(v))forvinhighPiles]"""find pairs with matching trailing ones;eachmatchisa3-tupleoftwopileindicesandthepositionofthezero"""matches=[(i,j,highOneP+1+highPilesZ[i][1])fori,jinpairs(len(piles))ifhighPilesZ[i][1]==highPilesZ[j][1]]"""if there are pairs with matching trailing ones find the lowest position withatleasttwozeros;eachpairofpilesinthissetisamatchingpair"""ifnotmatches:zeroP=lowPosWithMoreThanOneZero(highPiles)lowzs=[ifori,vinenumerate(highPiles)ifzeroAt(v,zeroP)]nz=len(lowzs)baseZeroP=highOneP+1+zeroPmatches=[(lowzs[i],lowzs[j],baseZeroP)fori,jinpairs(nz)]"""for each pair add to flip the matching zeros and fix resulting piles with thezero-at-high-1fixer;thenchoosethebestresultoutofallpairs"""results=(fixPilesTwoZeros(piles,zeroP,i,j)fori,j,zeroPinmatches)returnmin(results,key=sum)deffixPilesTwoZeros(piles,zeroP,i,j):"""given a set of piles where piles i, j have zeros at zeroP add to each pile to flip that zero andthenfixthepiles"""iAdd=diffToFlip(piles[i],zeroP)jAdd=diffToFlip(piles[j],zeroP)piles=list(piles)piles[i]+=iAddpiles[j]+=jAddreturnfixPilesWithZeroAtHigh(piles)defsolve(piles):fixedPiles=fixPiles(piles)returnsum(fixedPiles)-sum(piles),fixedPilesdefreadLine():returninput()defreadInt():returnint(readLine())defreadInts():returntuple(int(token)fortokeninreadLine().split())defreadIntList():returnlist(readInts())defmain():nt=readInt()for_inrange(nt):_n=readInt()piles=readIntList()answer,_fixedPiles=solve(piles)print(answer)main()
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Unfair Game
You are viewing a single comment's thread. Return to all comments →
Python 3 solution