329. Black-and-White Triangle

Time limit per test: 0.25 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard

An equilateral triangle with side N can be split into N2 unit triangles as shown on picture (a):

Each unit triangle can be colored with two colors in four different ways (numbered from 1 to 4), shown on picture (b). A colored equilateral triangle with side N can then be assembled from colored unit triangles in many different ways. A colored equilateral triangle is correct if the neighboring sides of adjacent unit triangles have the same color. Such triangles form beautiful pictures like picture (c).

You are to find the number of different correct colored equilateral triangles that can be assembled from a given set of unit triangles. You're allowed to rotate unit triangles arbitrarily, however, the position of the big triangle is fixed (i.e., the colorings that are rotations of each other are considered different).

The first line of input contains an integer N, 1 ≤ N ≤ 5. The second line of input contains four non-negative integers n1, n2, n3, and n4, denoting the amounts of available unit triangles of kinds 1, 2, 3 and 4 respectively (as shown on picture (b)). It is always true that n1 + n2 + n3 + n4 = N2.

Output the sought number of correct colored equilateral triangles.

sample input
sample output
0 1 0 3

sample input
sample output
1 1 1 1

Online Contester Team © 2002 - 2010. All rights reserved.