B. Тэмдэгт мөртэй тоглох

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

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

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

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

$n × n$ хэмжээтэй Латин цагаан толгойн жижиг үсгээс бүрдэх $T$ хүснэгт өгөгджээ. Хэрвээ энэ хөлгөөр явахдаа $s$ тэмдэгт мөрийг үүсгэж чаддаг бол уг тэмдэгт мөрийг сайн тэмдэгт мөр гэж нэрлэе. Энэ нь өөрөөр хэлвэл хүснэгтийн зүүн дээд мөрнөөс эхлээд баруун, эсвэл доош чиглэлд шилжиж $s$-г үүсгэнэ гэсэн үг. Дараах байдлаар үйлдлийг тодорхойлно:

Хүснэгтийн мөр нь дээрээс доош $1$-с $n$-р, багана нь баруунаас зүүн тийш $1$-с $n$ хүртэл дугаарлагдсан. $T$ хүснэгтийн ($r,c$) нүд нь $r$-р мөрний $c$-р багана байна. Уг нүдийг $T_{r,c}$ гэж тэмдэглэе.

$k$ урттай зам нь [($r_1, c_1$), ($r_2, c_2$), ..., ($r_k, c_k$)] хэлбэртэй байна. Дараах замуудыг зөв гэж үзнэ. Үүнд:

  • $1$ урттай зам буюу [($1, 1$)]
  • $m$ урттай [($r_1, c_1$), ... , ($r_m, c_m$)] зам нь зөв бол [($r_1, c_1$), ... , ($r_m, c_m$), ($r_{m+1}, c_m$)] ба [($r_1, c_1$), ... , ($r_m, c_m$), ($r_m, c_{m+1}$)] замууд нь $m + 1$ урттай зөв замууд болно.

[($r_1, c_1$), ($r_2, c_2$), ... , ($r_k, c_k$)] нь $T_{r_1, c_1} + T_{r_2, c_2} + ... + T_{r_k, c_k}$ тэмдэгт мөрийг үүсгэнэ.

Хоёр тоглогч анх хоосон тэмдэгт мөртэй, хоёр тоглогч ээлжлэн тэмдэгт мөрийнхөө хойно шинэ үсэг залгана. Үүний дараа үүссэн тэмдэгт мөр нь заавал сайн байх ёстой. Тоглоом $2*n-1$ үеийн дараа дуусна. Тоглоом дараах нөхцлөөр дүгнэгдэнэ:

  1. Үүссэн тэмдэгт мөр нь дотроо $b$-с олон $a$ агуулж байвал $1$-р хүн
  2. Үүссэн тэмдэгт мөр нь дотроо $a$-с олон $b$ агуулж байвал $2$-р хүн
  3. Үүссэн тэмдэгт мөр нь тэнцүү тооны $a$, $b$ үсэг агуулж байвал тэнцэнэ

Таны даалгавар бол хоёр тоглогч хамгийн сайн стратегиар тоглосон үед тоглоомын үр дүнг гаргах юм.

Оролт

Оролтын эхний мөрөнд $n$ ($1 < n < 20$).

Дараагийн $n$ мөр бүрт $T$ хүснэгтийг илтгэх $n$ тэмдэгт тус тус өгөгдөнө.

Гаралт

Хэрвээ эхний хүн ялах бол "FIRST", хоёрдугаар хүн ялах бол "SECOND", тэнцэх бол "DRAW" гэж хэвлэнэ.

Орчуулсан: zoloogg

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

Оролт
2
ab
cd
Гаралт
DRAW
Оролт
2
xa
ay
Гаралт
FIRST
Оролт
3
aab
bcb
bac
Гаралт
DRAW

Тэмдэглэл

Consider the first sample:

Good strings are strings: a$, ab$, ac$, abd$, acd$.

The first player moves first and adds letter a$ to the string, as there is only one good string of length $1$. Then the second player can add b$ or c$ and the game will end with strings abd$ or acd$, correspondingly. In the first case it will be a draw (the string has one a$ and one b$), in the second case the first player wins. Naturally, in this case the second player prefers to choose letter b$ and end the game with a draw.

Consider the second sample:

Good strings are: x$, xa$, xay$.

We can see that the game will end with string xay$ and the first player wins.

Сэтгэгдлүүдийг ачааллаж байна...