| Бодолт илгээх | Бүх бодолтууд | Шилдэг бодолтууд | Жагсаалт руу буцах |
MMZOS03A - Метро |
Улаанбаатар хотод шинээр нээгдсэн метроны суудлыг 1-ээс N хүртэл дугаарласан N мөр, 1 ба 2 дугаартай хоёр баганаас бүрдсэн хүснэгт хэлбэрээр дугаарлан зохион байгуулав. A(RA,CA) ба B(RB,CB) хоёр суудлын хоорондох зайг
√(RA−RB)2+(CA−CB)2 гэж олно.
Covid-19 цар тахлын улмаас ихэнх зорчигчид нийтийн тээврээр үйлчлүүлэхдээ бусад зорчигчдоос аль болох хол суудал сонгохыг үргэлж хичээдэг. Бүр тодруулбал зорчигч метроруу орохдоо хамгийн ойр байх хүнтэй суудал хүрэх зай нь боломжит хамгийн хол байх чөлөөт суудлыг сонгоно. Хэрэв ийм чөлөөтэй суудал нэгээс олон байвал тэд хамгийн бага мөрийн дугаартай суудлыг сонгох бөгөөд баганын хувьд ч нэгээс олон суудал байгаа бол бага баганын дугаартай суудлыг сонгох болно. Зорчигч метроноос буух хүртэл сонгосон суудалдаа сууна. Хэрэв метро хоосон байвал зорчигч 1 дүгээр мөр, 1 дүгээр баганын суудлыг үргэлж сонгох болно.
Даалгавар:
Зорчигч метроруу орох эсвэл гарах үйлдлүүдийн дараалал өгөгдөхөд орох үйлдэл тус бүрт зорчигчид хаана суух ёстойг тодорхойлох программ бичээрэй. Метро эхлээд хоосон байна.
Оролтын дарааллаар 1-ээс М хүртэл дугаарласан M үйлдэл байна. Орох гарах гэсэн хоёр төрлийн үйлдэл байдаг бөгөөд зорчигч метроруу орж буй үйлдлийг “Е”, харин гарч буй үйлдлийг “L” гэж тэмдэглэв. “L” үйлдлийн хувьд P бүхэл тоо хамт өгөгдөнө. Энэ тохиолдолд гарч буй зорчигч нь Р дүгээр үйлдлээр орсон зорчигч болохыг зааж өгнө.
Тестийн өгөгдлүүдэд зорчигч орох гэж оролдох бүрт метро дотор дор хаяж нэг сул суудал байхаар өгсөн болно.
Оролт:
Оролтын эхний мөрөнд метроны суудлын мөрийн тоо N, үйлдлүүдийн тоо M (1 ≤ N ≤ 150 000, 1 ≤ M ≤ 30 000) гэсэн хоёр бүхэл тоо зайгаар тусгаарлагдан өгөгдөнө. Дараагийн М мөрөнд үйлдлүүдийн тодорхойлолт байх бөгөөд тэдгээр M мөрний K дугаар мөрөнд K дугаар үйлдлийн тодорхойлолт байна. Энэ тодорхойлолт нь эсвэл E, эсвэл L тэмдэгт нэг хоосон зай ба PK (1 ≤ PK <K) бүхэл тоо байна. PK дугаар үйлдэл нь E хэлбэртэй байх бөгөөд зорчигч хоёр удаа гарахгүй гэсэн үг.
Гаралт:
Гаралтын мөрийн тоо нь оролтын E гэж тэмдэглэсэн үйлдлийн тоотой тэнцүү байх ёстой. Е үйлдэл бүрийн хувьд өгсөн дарааллаар нь зорчигчийн сонгох суудлын мөр ба баганын дугаарыг нэг мөрөнд нэг хоосон зайгаар тусгаарлан гаргаарай.
Жишээ:
|
Оролт |
Гаралт |
Оролт |
Гаралт |
Оролт |
Гаралт |
|
3 7 E E E L 2 E L 1 E |
1 1 3 2 1 2 3 1 1 1 |
13 9 E E E E E E E E E |
1 1 13 2 7 1 4 2 10 1 2 2 3 1 5 1 6 2 |
10 9 E E E E L 3 E E L 6 E |
1 1 10 2 5 2 7 1 4 2 2 2 4 1 |
| Нэмсэн: | munkhbat |
| Огноо: | 2021-03-27 |
| Хугацааны хязгаарлалт: | 1s |
| Эх кодын хэмжээний хязгаарлалт: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Програмчлалын хэлүүд: | Бүгд дараах хэлүүдээс бусад: NCSHARP JULIA PYPY3 |