Codeforces Round #804 (Div. 2)
4 өдрийн дараа |
E. Талбай доторх баавгай
хугацааны хязгаарлалт 1 секунд
санах ойн хязгаарлалт 256 мегабайт
оролт стандарт оролт
гаралт стандарт гаралт
Манай баавгайн ой нь алаг эрээн талбайтай байв. Уг алаг эрээн талбай гэдэг нь $n × n$ хэмжээтэй хүснэгт бөгөөд мөрнүүд нь дээрээсээ доош хүртэл 1-ээс $n$ хүртэл дугаарлагдсан ба баганууд нь зүүнээсээ баруун хүртэл 1-ээс $n$ хүртэл дугаарлагдсан байв. Уг талбайн $x$ мөр болон $y$ баганын огтлолцол дээрх нүдийг $(x, y)$-ээр тэмдэглэе. Талбайн нүд болгон ургаж буй бөөрөлзгөнө агуулах ба талбайн $(x, y)$ нүд нь $x + y$ ширхэг бөөрөлзгөний бут агуулна.
Баавгай нь талбайг хөндлөн алхахаар иржээ. Алхалтын эхлэл хэсэгт түүний хурд нь $(dx, dy)$ байна. Дараа нь баавгай яг $t$ секундийг талбай дээр өнгөрөөнө. Секунд болгонд дараах үйлдлийг хийнэ:
- Уг мөчид баавгай $(x, y)$ нүдэнд байгаа гэж үзье.
- Эхлээд баавгай одоо зогсож байгаа нүднийхээ бүх бутнуудын бөөрөлзгөнийг иднэ. Баавгай $k$ бутнуудаас бөөрөлзгөнө идсэнийхээ дараа өөрийн хурдныхаа бүрэлдэхүүн хэсэг болгоныг $k$-аар нэмэгдүүлдэг аж. Өөрөөр хэлбэл хэрэв $k$ ширхэг бутнуудын бөөрөлзгөнийг идэхээс өмнө түүний хурд нь $(dx, dy)$ байсан бол бөөрөлзгөнө идсэний дараа түүний хурд $(dx + k, dy + k)$-тай тэнцүү болох юм.
- Баавгайн одоогийн хурдыг $(dx, dy)$-аар тэмдэглэе (энэ нь өмнөх алхмаар нэмэгдсэн байгаа юм). Дараа нь баавгай $(x, y)$ нүднээс $(((x + dx - 1) mod n) + 1, ((y + dy - 1) mod n) + 1)$ нүд уруу нүүнэ.
- Үүний дараа талбайн нүд болгонд нэг нэмэлт бөөрөлзгөний бут ургана.
Таны даалгавар бол баавгайн үйлдлүүдийг урьдчилан хэлэх юм. Хэрэв тэрээр $(sx, sy)$ нүднээс эхэлж алхах бол түүний алхалт ямар нүдэн дээр дуусахыг олно уу. Бут болгон нь хязгааргүй тооны бөөрөлзгөнөтэй ба баавгай хэзээ ч бүгдийн идэж чадахгүй гэж үзнэ үү.
Оролт
Эхний мөрөнд зайгаар тусгаарлагдсан 6-н бүхэл тоо $n$, $sx$, $sy$, $dx$, $dy$, $t$ $(1 ≤ n ≤ 10^{9}; 1 ≤ sx, sy ≤ n; - 100 ≤ dx, dy ≤ 100; 0 ≤ t ≤ 10^{18})$ өгөгдөнө.
Гаралт
$t$ секундийн дараа баавгайн зогсох нүдний координатууд болох 2 бүхэл тоог хэвлэнэ үү.
Орчуулсан: Баатархүү
Жишээ тэстүүд
Оролт
5 1 2 0 1 2
Гаралт
3 1
Оролт
1 1 1 -1 -1 2
Гаралт
1 1
Тэмдэглэл
$a mod b$ үйлдэл нь $a$-г $b$-д хуваасны дараах үлдэгдлийг илэрхийлнэ. Уг үйлдлийн үр дүн нь үргэлж сөрөг биш тоо байхыг анхаарна уу. Жишээлбэл $( - 1) mod 3 = 2$.
Эхний жишээнд эхний үйлдлээс өмнө хурдны вектор нь (3,4)-тэй тэнцүү байх ба баавгай (4,1) нүдэнд очих юм. 2-дахь үйлдлээс өмнө хурдны вектор нь (9,10)-тай тэнцүү байх ба баавгай нь (3,1) нүдэнд очно. 2-дахь үйлдэл дээр бөөрөлзгөний бутны тоо нь 1-ээр ихэссэн байгааг санана уу.
2-дахь жишээнд эхний үйлдлээс өмнө хурдны вектор нь (1,1)-тэй тэнцүү байх ба баавгай (1,1) нүдэнд очих юм. 2-дахь үйлдлээс өмнө хурдны вектор нь (4,4)-тэй тэнцүү байх ба баавгай нь (1,1) нүдэнд очно. 2-дахь үйлдэл дээр бөөрөлзгөний бутны тоо нь 1-ээр ихэссэн байгааг санана уу.