F. Бунхан

хугацааны хязгаарлалт 1 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Берландын хаан 4-р Берл саяхан таалал төгсчээ. Талийгаач хааны байгуулсан гавьяаг хүндэтгэн шинэ хаан 5-р Берл нийслэл хотын төв талбайд бунхан босгохоор шийджээ.

Бунхан нь $2n$ ширхэг блокоор баригдах бөгөөд блок бүр нь куб хэлбэртэй байна. Блок бүр $1 × 1$ метр квадрат суурьтай байх бөгөөд эдгээр блокнуудын яг $2$ ширхэг нь $1$ метр өндөртэй, мөн яг $2$ ширхэг нь $2$ метр өндөртэй гэх мэтчилэн яг $2$ ширхэг нь $n$ метр өндөртэй байх юм.

Блокууд нь мөрийн дагуу хоорондоо зай байхгүйгээр байрлах ба мэдээж хэрэг дурын дарааллаар байрласан блокууд нь бунхан хэлбэртэй болж чадахгүй. Бунхан хэлбэртэй байхын тулд бунханы нэг төгсгөлөөс нөгөөх хүртэл нь явах үед блокуудын өндөр нь эхлээд үл буурах (нэмэгдэж байх эсвэл хэвэндээ байх) ба дараа нь үл ихсэх (буурах эсвэл хэвэндээ байх) гэсэн дараалалтай байх юм. Үл буурах эсвэл үл ихсэх дарааллуудын аль нэг нь байхгүй байж болно. Өөрөөр хэлбэл дан үл буурах эсвэл дан үл ихсэх дараалал байж болно. Жишээлбэл дараах блокуудын дараалал нь энэ нөхцөлийг хангаж байгаа юм:

  • $[1, 2, 2, 3, 4, 4, 3, 1]$
  • $[1, 1]$
  • $[2, 2, 1, 1]$
  • $[1, 2, 3, 3, 2, 1]$

Гэнэт ерөнхий архитектураас дахин $k$ ширхэг нөхцөл тавигдав. Нөхцөл бүр нь "$h[x_{i}]$ тэмдэгт$_{i}$ $h[y_{i}]$" гэсэн хэлбэртэй байх ба энд $h[t]$-ээр $t$-р блокын өндрийг тэмдэглэв. Мөн тэмдэгт$_{i}$ нь дараах таван янзын аль нэг нь байна:

  • "=" (тэнцүү)
  • "<" (бага)
  • ">" (их)
  • "<=" (бага буюу тэнцүү)
  • ">=" (их буюу тэнцүү)

Түүнчлэн эдгээр $k$ ширхэг нэмэлт нөхцөлийг өгөхдөө хос дугаарууд болох $x_{i}$, $y_{i}$ ($1 ≤ x_{i}, y_{i} ≤ 2n$) болон тэмдэгт болох тэмдэг$_{i}$ ашиглан өгнө.

Тэгвэл бунханы хэлбэрийн талаарх ерөнхий нөхцөл болон нэмэлт $k$ ширхэг нөхцлүүдийг хангасан байхаар блокуудыг байрлуулах нийт боломжийн тоог олно уу?

Оролт

Эхний мөрөнд хос блокын тоо $n$ ба нэмэлт нөхцлийн тоо $k$ бүхэл тоонууд өгөгдөнө. ($1 ≤ n ≤ 35$, $0 ≤ k ≤ 100$)

Дараачийн $k$ мөрөнд нэмэлт нөхцлүүдийг өгөх ба мөр болгон "$x_{i}$ тэмдэгт$_{i}$ $y_{i}$" ($1 ≤ x_{i}, y_{i} ≤ 2n$) хэлбэртэй байна.

Гаралт

Бунханы хэлбэрийн нийт боломжийн тоог хэвлэнэ.

Орчуулсан: Баатархүү

Жишээ тэстүүд

Оролт
3 0
Гаралт
9
Оролт
3 1
2 > 3
Гаралт
1
Оролт
4 1
3 = 6
Гаралт
3
Сэтгэгдлүүдийг ачааллаж байна...