// Liam Keliher, 2023 // // Solution for problem "Triptych" (triptych) // // Use DP to compute, for each triple (a,b,c) satisfying 1 <= a+b+c <= W, // the number of sequences containing a A's, b B's, and c C's with the // property that no two consecutive letters are the same, except possibly BB. // // Then use the same data to subtract the number of palindromes. // Note that an even-length palindrome must have BB in the middle. // // For explanation of memo table contents, see comment before recurse() method. import java.io.*; import java.util.*; public class TriptychKeliher { static final int A = 0; static final int B1 = 1; static final int B2 = 2; static final int C = 3; static long[][][][] memo; static final int EMPTY = -1; //--------------------------------------------------------------- public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] tokens = br.readLine().split(" "); int W = Integer.parseInt(tokens[0]); int D = Integer.parseInt(tokens[1]); // Initialize memo table memo = new long[W + 1][W + 1][W + 1][4]; for (int a = 0; a <= W; a++) { for (int b = 0; b <= W; b++) { for (int c = 0; c <= W; c++) { Arrays.fill(memo[a][b][c], EMPTY); } // for c } // for b } // for a long answer = 0; for (int a = 0; a <= W; a++) { int bMin = Math.max(0, a - D); int bMax = Math.min(W, a + D); bMax = Math.min(bMax, W - a); // ensure a + b <= W for (int b = bMin; b <= bMax; b++) { int c = W - a - b; if (Math.abs(a - c) <= D && Math.abs(b - c) <= D) { answer += recurse(a, b, c, A) + recurse(a, b, c, B1) + recurse(a, b, c, B2) + recurse(a, b, c, C); } // if } // for b } // for a // Remove palindromes that have already been counted: // - odd-length palindromes // - even-length palindromes with BB in the middle long numPalindromes = 0; int wHalf = W/2; int dHalf = (D + 1)/2; for (int aHalf = 0; aHalf <= wHalf; aHalf++) { int bMin = Math.max(0, aHalf - dHalf); int bMax = Math.min(wHalf, aHalf + dHalf); bMax = Math.min(bMax, wHalf - aHalf); // ensure aHalf + bHalf <= wHalf for (int bHalf = bMin; bHalf <= bMax; bHalf++) { int cHalf = wHalf - aHalf - bHalf; int a = 2*aHalf; int b = 2*bHalf; int c = 2*cHalf; if (W % 2 == 0) { // W is even if (Math.abs(a - b) <= D && Math.abs(a - c) <= D && Math.abs(b - c) <= D) { numPalindromes += recurse(aHalf, bHalf, cHalf, B1); } // if } // if else { // W is odd // Put A in middle position a++; if (Math.abs(a - c) <= D && Math.abs(a - b) <= D && Math.abs(b - c) <= D) { numPalindromes += recurse(aHalf + 1, bHalf, cHalf, A); } // if a--; // Put B in middle position b++; if (Math.abs(a - c) <= D && Math.abs(a - b) <= D && Math.abs(b - c) <= D) { numPalindromes += recurse(aHalf, bHalf + 1, cHalf, B1); // cannot be B2 } // if b--; // Put C in middle position c++; if (Math.abs(a - c) <= D && Math.abs(a - b) <= D && Math.abs(b - c) <= D) { numPalindromes += recurse(aHalf, bHalf, cHalf + 1, C); } // if c--; } // else } // for bHalf } // for aHalf answer -= numPalindromes; System.out.println(answer); } // main(String[]) //--------------------------------------------------------------- // Return the number of sequences containing numA A's, numB B's, and numC C's // in which there are no repeated consecutive letters, except perhaps BB, and // which end with A, B, BB, or C, as specified by last (see class constants). static long recurse(int numA, int numB, int numC, int last) { if (memo[numA][numB][numC][last] != EMPTY) { return memo[numA][numB][numC][last]; } // if long result = 0; int total = numA + numB + numC; // NOTE: it will never be the case that total == 0 if (total == 1) { if ((last == A && numA == 1) || (last == B1 && numB == 1) || (last == C && numC == 1)) { result = 1; } // if } // if else { // total >= 2 if (last == A && numA > 0) { result = recurse(numA - 1, numB, numC, B1) + recurse(numA - 1, numB, numC, B2) + recurse(numA - 1, numB, numC, C); } // if else if (last == B1 && numB > 0) { result = recurse(numA, numB - 1, numC, A) + recurse(numA, numB - 1, numC, C); } // else if else if (last == B2 && numB > 0) { result = recurse(numA, numB - 1, numC, B1); } // else if else if (last == C && numC > 0) { result = recurse(numA, numB, numC - 1, A) + recurse(numA, numB, numC - 1, B1) + recurse(numA, numB, numC - 1, B2); } // else if } // else memo[numA][numB][numC][last] = result; return result; } // recurse(int,int,int,int) //--------------------------------------------------------------- } // class TriptychKeliher