[Codeforces Round #Pi] Mausoleum

9
18
2015

King of Berland Berl IV has recently died. Hail Berl V! As a sign of the highest achievements of the deceased king the new king decided to build a mausoleum with Berl IV's body on the main square of the capital.

The mausoleum will be constructed from 2n blocks, each of them has the shape of a cuboid. Each block has the bottom base of a 1 × 1meter square. Among the blocks, exactly two of them have the height of one meter, exactly two have the height of two meters, ..., exactly two have the height of n meters.

The blocks are arranged in a row without spacing one after the other. Of course, not every arrangement of blocks has the form of a mausoleum. In order to make the given arrangement in the form of the mausoleum, it is necessary that when you pass along the mausoleum, from one end to the other, the heights of the blocks first were non-decreasing (i.e., increasing or remained the same), and then — non-increasing (decrease or remained unchanged). It is possible that any of these two areas will be omitted. For example, the following sequences of block height meet this requirement:

[1, 2, 2, 3, 4, 4, 3, 1];
[1, 1];
[2, 2, 1, 1];
[1, 2, 3, 3, 2, 1].

Suddenly, k more requirements appeared. Each of the requirements has the form: "h[xi] signi h[yi]", where h[t] is the height of the t-th block, and a signi is one of the five possible signs: '=' (equals), '<' (less than), '>' (more than), '<=' (less than or equals), '>=' (more than or equals). Thus, each of the k additional requirements is given by a pair of indexes xi, yi (1 ≤ xi, yi ≤ 2n) and sign signi.

Find the number of possible ways to rearrange the blocks so that both the requirement about the shape of the mausoleum (see paragraph 3) and the k additional requirements were met.

Input

The first line of the input contains integers n and k (1 ≤ n ≤ 35, 0 ≤ k ≤ 100) — the number of pairs of blocks and the number of additional requirements.

Next k lines contain listed additional requirements, one per line in the format "xi signi yi" (1 ≤ xi, yi ≤ 2n), and the sign is on of the list of the five possible signs.

Output

Print the sought number of ways.

							Sample test(s)

									input
3 0

									output
9

									input
3 1
2 > 3

									output
1

									input
4 1
3 = 6

									output
3

题目大意：1~n每个数各用两次，构成一个先非降再非升的序列h（长度为2n）。有若干个限制条件$x_i\, sign_i\, y_i,\, sign_i\in\{<,>,\le ,\ge ,=\}$，表示构成的序列必须满足$h_{x_i}\, sign_i\, h_{y_i}$。求符合条件的序列的数量。

先考虑没有限制条件时序列怎么生成。

假设n=3，开始时序列是这样：

------

然后放入两个1，有三种放法，都放左边，都放右边，一个左边一个右边。

1----1

11----

----11

然后放两个2，这里以前面的第一种情况为例。

12--21

122--1

1--221

最后在剩下的两个空格放3。

显然，总数可以通过递推求得：

$f\left( i,j\right) =f\left( i+1,j-1\right) +f\left( i+2,j\right) +f\left( i,j-2\right)$。

现在考虑限制条件，如果在一个位置i上放数字时，这个位置上有$h_i<h_j$的限制条件，那么位置j必须还没有放过数字。其他的限制也差不多，只要在递推时判断一下就行了。

代码在此。

Category: 题解 | Tags: 递推 Codeforces | Read Count: 336

Stalker's Blog

I am here in the shadows.