Avoider

Time limit1sMemory limit256 MB

Summary

Count self-avoiding walks of each length from a to b in the first quadrant starting east from the origin and print the sum.

Level: Medium7 of 10
Topics: Backtracking, DFS, Brute force
Solved: No attempts yet

Problem

Use only the points of the plane that have integer coordinates. A walk starts at the origin $(0, 0)$ and its first step goes to $(1, 0)$ . Every later step goes to one of the four integer points next to the current point, up, down, left, or right. The walk may stand only on points whose coordinates are both nonnegative, and it may never step on a point it has already visited.

Fix the number of steps $n$ and count the walks of that kind. The first step counts toward $n$ . For $n$ equal to 2, 3, and 4 the counts are 2, 5, and 12.

Walks for n equal to 2, 3, and 4

You are given two integers $a$ and $b$ . Compute the number of walks for each of $n = a, a+1, \ldots, b$ and print the sum.

Input

The first line contains two integers $a$ and $b$ separated by a space. $(0 < a < b < 29)$

Output

Print, on one line, the sum of the walk counts for $n = a, a+1, \ldots, b$ . The sum can exceed the range of a 32-bit integer.

Examples2

Example 1
Input
```
2 4
```
Expected output
```
19
```
Example 2
Input
```
27 28
```
Expected output
```
96850643983
```