Codeforces Round #804 (Div. 2)
4 өдрийн дараа |
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$ үеийн дараа дуусна. Тоглоом дараах нөхцлөөр дүгнэгдэнэ:
- Үүссэн тэмдэгт мөр нь дотроо $b$-с олон $a$ агуулж байвал $1$-р хүн
- Үүссэн тэмдэгт мөр нь дотроо $a$-с олон $b$ агуулж байвал $2$-р хүн
- Үүссэн тэмдэгт мөр нь тэнцүү тооны $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.