| Бодолт илгээх | Бүх бодолтууд | Шилдэг бодолтууд | Жагсаалт руу буцах |
MMZOS04B - Хуралдай |
Эрт урьд цагт нэгэн улс далай тэнгист олон жижиг арлыг эзэгнэн оршдог байж гэнэ. Энэхүү улсын газрын зураг нь 2500 мөр, 2500 багана бүхий нэгж квадратуудаас бүрдсэн тор юм. Мөрүүдийг хойноос урагш 1-ээс 2500 гэж дугаарладаг бол багануудыг зүүнээс баруун тийш 1-ээс 2500 хүртэл дугаарлана. Далайд 1-ээс N хүртэл дугаарлагдсан N арал байдаг бөгөөд арал бүр нь ижилхэн нэгж квадрат дотор багтаж байрладаг. K арлын байршлыг түүнийг агуулж буй нэгж квадратын координатаар өгнө. Координат нь түүний мөрийн дугаар RK ба баганын дугаар CK байна. Ижил байрлалтай хоёр арал байхгүй.
Салхи болон далайн урсгалаас хамаарч тухайн нэг арлаас баруун хойд эсвэл зүүн өмнөд зүгт байрладаг арлууд руу дарвуулт завиар аялах боломжтой. Илүү тодруулвал A ба B хоёр арлын хувьд RA <RB ба CA <CB гэсэн нөхцөл, эсвэл RA> RB ба CA> CB гэсэн нөхцөлийн аль нь ч биелсэн тохиолдолд А-аас В аралруу дарвуулт завиар нэг “үсрэлт”-ээр очих боломжтой юм. Хоёр арлын хоорондох зай эсвэл тэдгээрийн хооронд өөр бусад арлууд байгаа нь нэгээс нөгөө рүү очих “үсрэлт”-д нөлөөлөхгүй гэдгийг анхаараарай. Хэрэв А-аас В хүртэл шууд нэг “үсрэлт”-ээр очих боломжгүй бол бусад арлуудаар дамжин хэд хэдэн “үсрэлт”-ээр очих боломжтой. А-аас В хүртэлх аялалын зайг А-аас В хүртэл явахад шаардагдах хамгийн цөөн “үсрэлт”-ийн тоо гэж тодорхойлно.
Жишээлбэл дээрх зурагт 2-р мөрний 3-р багана дээрх аралруу түүнээс зүүн өмнө байрлах дөрвөн арлаас нэг “үсрэлт” –ээр очих боломжтой бол үлдсэн хоёр арлаас хоёр “үсрэлт” –ээр очино.
Даалгавар:
Улсын хаан хуралдай зохион байгуулах арал сонгох гэж байна. Ингэхдээ тухайн арал дээр бусад арлуудаас очих аялалын зайнуудын нийлбэр хамгийн бага байх арлыг сонгох шаардлагатай. Иймд N арлын байршлыг харгалзан арал тус бүрийн аялалын зайн нийлбэр олох программ бичээрэй.
Тестийн өгөгдөлд дурын А ба В арлуудын хувьд А-аас В хүртэл хэдэн “үсрэлт”-үүдийн дарааллыг ашиглан аялах боломжтой байх болно.
Оролт:
Оролтын эхний мөрөнд арлын тоо болох N (3 ≤ N ≤ 250 000) бүхэл тоо орно. Дараагийн N мөрөнд арлуудын байршлыг агуулна. Байршил бүр нь 1-с 2500 хүртэлх утгатай хос бүхэл тоо зайгаар тусгаарлагдан өгөгдөх бөгөөд эдгээр нь харгалзан мөр, баганын дугаар гэсэн эрэмбэтэй байна.
Гаралт:
Гаралт нь N мөр агуулсан байх ёстой. Арал тус бүрийн хувьд оролтонд өгсөн дарааллын дагуу бусад бүх арлуудаас тухайн арал хүртэлх аялалын зайн нийлбэрийг нэг мөрөнд гаргана.
Үнэлгээ:
- Нийт 25 оноотой тестийн тохиолдолд N нь хамгийн ихдээ 100 байх болно.
- Нийт 50 оноотой тестийн тохиолдолд N нь хамгийн ихдээ 1500 байх болно.
- Нийт 60 оноотой тестийн тохиолдолд N нь хамгийн ихдээ 5000 байх болно.
- Нийт 80 оноотой тестийн тохиолдолд N нь хамгийн ихдээ 25000 байх болно.
Жишээ:
|
Оролт1 |
Гаралт1 |
Оролт1 |
Гаралт1 |
|
7 1 7 7 5 4 5 4 8 6 6 6 1 2 3 |
16 11 12 11 12 16 8 |
4 1 1 2 3 3 2 4 4 |
3 4 4 3 |
| Нэмсэн: | munkhbat |
| Огноо: | 2021-03-31 |
| Хугацааны хязгаарлалт: | 1s |
| Эх кодын хэмжээний хязгаарлалт: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Програмчлалын хэлүүд: | Бүгд дараах хэлүүдээс бусад: NCSHARP JULIA PYPY3 |