D. Чөтгөрийн сүм ба хөдөлдөг чулуунууд

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

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

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

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

Чухал: Урьдчилсан тестэд бүх боломжит тест агуулагдсан, иймд та энэ бодлогод дайралт хийж чадахгүй. Хэрвээ та урьдчилсан тестийг давсан бол систем тестийг ч мөн давна.

Та бол аялагч ба одоо чөтгөрийн сүмд аялаж байна. Хоёр мангасыг устгасаны дараа та бүхлээрээ ханаар хүрээлэгдсэн $n × n$ хүснэгт бүхий хавтангуудаас бүрдсэн квадрат өрөөнд ирсэн. Өрөөний төгсгөлд чөтгөрийн шидийн хүчээр цоожлогдсон хаалга байна. Хаалган дээр дараах зааврууд бичигдсэн байв:

Чулууны мөргөлдөх чимээ хаалгыг сэрээх болно!

Ахмад аялагчийн хувьд та энэ юуг илэрхийлж байгааг дор нь ойлгосон. Хаалганы цаана байгаа өрөөнд хязгааргүй тооны шидэт чулуу байна. Тэнд дөрвөн төрлийн чулуу байгаа:

  • '$^$': энэ чулуу нь дээшээ хөдөлнө;
  • '$<$': энэ чулуу зүүн тийшээ хөдөлнө;
  • '$>$': энэ чулуу баруун тийш хөдөлнө;
  • '$v$': энэ чулуу нь доошоо хөдөлнө.

Хаалгыг нээхийн тулд та эхлээд зарим хавтангуудыг сонгож чулуунуудыг байрлуулах хэрэгтэй (нэг хавтан дээр хамгийн ихдээ нэг л чулуу байна). Тэгээд та байрлуулсан чулуунуудаасаа нэгийг нь сонгож идэвхжүүлнэ. Идэвхжүүлсэн чулуу нь өөр чулуу эсвэл өрөөний хана мөргөх хүртлээ өөрийн чиглэлийн дагуу хөдөлнө (хэрвээ чулууны явах чиглэлд ямар нэг зүйл хааж байвал чулуу хөдлөхгүй). Ингээд чулуу идэвхгүй болно. Хэрвээ чулуу ханыг мөргөх эсвэл чулуу идэвхжээд аль хэдийн $10^{7}$ үйлдэл хийчихээд байгаа бол чулууны хөдөлгөөн зогсоно. Бусад тохиолдолд мөргөсөн чулуу идэвхжих ба энэ үйл явц давтагдана.

Хэрвээ чулуу хана эсвэл өөр чулуу мөргөхөөсөө өмнө ядаж нэг нүд хөдөлсөн л бол мөргөлдөхдөө чимээ гаргана. Хаалга ядаж $x$ удаа чимээ гарахад нэг удаа онгойно. Чулуунуудын хувьд $x$ удаа чимээ гарсны дараа үргэлжлүүлэн хөдлөж болно.

Дараах зурагт хөдөлдөг чулуунуудын боломжит дөрвөн нөхцөлийг харуулсан байна.

  • Ядаж нэг нүд хөдөлсөн тэгээд өөр чулуу мөргөсөн. Чимээ гаргасан, мөргөсөн чулуу идэвхжсэн.
  • Ядаж нэг нүд хөдөлсөн тэгээд хана мөргөсөн (өөрөөр өрөөний ирмэгийг мөргөсөн). Чимээ гаргасан, хөдөлгөөн дууссан.
  • Замыг нь чулуу тагласан учир хөдлөхгүй. Замыг нь хааж байгаа чулуу идэвхжсэн боловч чимээ гарахгүй.
  • Замд нь хана байгаа учир хөдлөхгүй. Чимээ гаргахгүй ба хөдөлгөөн дуусна.

Хөрш өрөөнд төрөл бүрийн чулуунаас хязгааргүй тоогоор байгаа гэж үз. Та юу хийхээ мэдэж байгаа: чулуунуудыг байрлуулж хаалгыг нээгээрэй!

Оролт

Эхний мөрөнд хоёр бүхэл тоо $n$ ба $x$ байх ба өрөөний хэмжээ болон чимээ гарах тоог заана. Энэ бодлогын хувьд яг гурван тестийн тохиолдол байна:

  • $n = 5, x = 5$;
  • $n = 3, x = 2$;
  • $n = 100, x = 10^{5}$.

Эдгээр тестийн тохиолдлууд нь бүгд урьдчилсан тестэд байна.

Гаралт

$n$ мөр хэвлэнэ. Мөр бүрт $n$ тэмдэгт байна. $i$-р мөрийн $j$-р тэмдэгт нь $i$-р мөр $j$-р баганад байрлах хавтангийн агуулгыг илэрхийлэх ба дараах тэмдэгтүүдийн аль нэг нь байна:

  • '$^$', '$<$', '$>$', эсвэл '$v$': бодлогын нөхцөлд тодорхойлсон чулуу.
  • '$.$': хоосон хавтан.

Тэгээд дараагийн мөрөнд нь хоёр бүхэл тоо $r$ ба $c$ ($1 ≤ r, c ≤ n$) байх ба энэ нь таны хамгийн эхэнд идэвхжүүлэх чулуу дээрээсээ $r$-р мөрийн зүүнээсээ $c$-р баганад байрласан гэсэн үг. Мэдээж энэ нүдэнд чулуу байх ёстой.

Хэрвээ хэд хэдэн шийдэл байвал алийг нь ч хэвлэж болно.

Орчуулсан: Г.Мэндбаяр

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

Оролт
5 5
Гаралт
>...v
v.<..
..^..
>....
..^.<
1 1
Оролт
3 2
Гаралт
>vv
^<.
^.<
1 3

Тэмдэглэл

Эхний жишээг доор харуулсан байна, чимээ гарсан тоотой нь хамт харуулав.

0 чимээ 1 чимээ 2 чимээ 3 чимээ 4 чимээ 4 чимээ хэвээрээ

Дээрх зурагт идэвхжсэн чулуу нь '$^$' чулуунаас '$<$' чулууруу шилжсэн. Гэхдээ '$^$' чулуу нэг ч хавтан хөдлөхгүй учир ямар ч чимээ гарахгүй. Ингээд 4 удаа чимээ гарна.

5 чимээ гарна.

Энэ үед 5 удаа чимээ гарчихсан учир энэ шийдэл зөв. Гэхдээ жишээг цааш нь үргэлжлүүлэн юу болохыг харья.

6 чимээ 7 чимээ 7 чимээ хэвээрээ 8 чимээ

Ингээд хөдөлгөөн зогсоно. Нийтдээ 8 чимээ гарна. Сүүлийн хөдөлгөөн чимээ гаргана гэдгийг санаарай.

Хоёрдугаар жишээг авч үзье:

0 чимээ 1 чимээ 2 чимээ

Одоо идэвхтэй чулуу нь $10^{7}$ хязгаардаа хүрэх хүртэл ямар нэг чимээ гаргалгүйгээр тасралтгүй солигдоно. Ингээд хөдөлгөөн зогсоно.

Нийтдээ 2 чимээ гарах ба шийдэл зөв байна.

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