class Solution:
    def solve(self , n , k , str1 , str2 ):
        # write code here
        same = 0
        diff = 0
        for i in range(len(str1)):
            if str1[i] == str2[i]:
                same += 1
            else:
                diff += 1
        res = Interval(max(0,k-diff),min(k,same)+min(diff,n-k))
        return res

class Solution:
    def rotate(self,s):
        n = len(s)
        new_s = [['0'] * n for _ in range(n)]
        for i in range(n):
            for j in range(n):
                new_s[i][j] = s[n-1-j][i]
        return new_s
    def helper(self,s1,s2):
        tmp = ''
        n = len(s1)
        for i in range(n):
            for j in range(n):
                if s1[i][j] == '0':
                    tmp = tmp + s2[i][j]
        return tmp
    def rotatePassword(self, s1, s2):
        # write code here
        n = len(s1)
        new_s1 = []
        new_s2 = []
        for i in range(n):
            tmp_s1 = []
            tmp_s2 = []
            for j in range(n):
                tmp_s1.append(s1[i][j])
                tmp_s2.append(s2[i][j])
            new_s1.append(tmp_s1)
            new_s2.append(tmp_s2)
        s1,s2 = new_s1,new_s2
        for i in range(len(s1)):
            print(s1[i])
        res = ''
        for _ in range(4):
            res = res + self.helper(s1,s2)
            s1 = self.rotate(s1)
        return res

class Solution:
    def calcProb(self, n):
        # write code here
        self.d = [-1] * (n + 1)
        def helper(n):
            if self.d[n] != -1:
                return self.d[n]
            if n <= 3:
                self.d[n] = 1
            elif n == 4:
                self.d[n] = 0.5
            elif n > 4:
                case1 = helper(n - 1)/2.0+helper(n-2)/2.0
                case2 = helper(n - 2)/2.0+helper(n-3)/2.0
                case3 = helper(n - 3)/2.0+helper(n-4)/2.0
                self.d[n] = 1 - min(case1, case2, case3)
            return self.d[n]
        helper(n)
        return float(self.d[n])