Minimum score possible for a player by selecting one or two consecutive array elements from given binary array | Stores the minimum score for each states as map < pair < pos , myturn > , ans > ; Function to find the minimum score after choosing element from array ; Return the stored state ; Base Case ; Player A 's turn ; Find the minimum score ; Store the current state ; Return the result ; Player B 's turn ; Find minimum score ; Store the current state ; Return the result ; Function that finds the minimum penality after choosing element from the given binary array ; Starting position of choosing element from array ; 0 denotes player A turn 1 denotes player B turn ; Function Call ; Print the answer for player A and B ; Minimum penalty ; Calculate sum of all arr elements ; Print the minimum score ; Driver Code
m = dict ( ) NEW_LINE def findMinimum ( a , n , pos , myturn ) : NEW_LINE INDENT if ( pos , myturn ) in m : NEW_LINE INDENT return m [ ( pos , myturn ) ] ; NEW_LINE DEDENT if ( pos >= n - 1 ) : NEW_LINE INDENT return 0 ; NEW_LINE DEDENT if ( not myturn ) : NEW_LINE INDENT ans = min ( findMinimum ( a , n , pos + 1 , not myturn ) + a [ pos ] , findMinimum ( a , n , pos + 2 , not myturn ) + a [ pos ] + a [ pos + 1 ] ) ; NEW_LINE m [ ( pos , myturn ) ] = ans ; NEW_LINE return ans ; NEW_LINE DEDENT if ( myturn ) : NEW_LINE INDENT ans = min ( findMinimum ( a , n , pos + 1 , not myturn ) , findMinimum ( a , n , pos + 2 , not myturn ) ) ; NEW_LINE m [ ( pos , myturn ) ] = ans ; NEW_LINE return ans ; NEW_LINE DEDENT return 0 ; NEW_LINE DEDENT def countPenality ( arr , N ) : NEW_LINE INDENT pos = 0 ; NEW_LINE turn = False ; NEW_LINE return findMinimum ( arr , N , pos , turn ) + 1 ; NEW_LINE DEDENT def printAnswer ( arr , N ) : NEW_LINE INDENT a = countPenality ( arr , N ) ; NEW_LINE sum = 0 ; NEW_LINE for i in range ( N ) : NEW_LINE INDENT sum += arr [ i ] ; NEW_LINE DEDENT print ( a ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 1 , 0 , 1 , 1 , 0 , 1 , 1 , 1 ] NEW_LINE N = len ( arr ) NEW_LINE printAnswer ( arr , N ) ; NEW_LINE DEDENT