Олон улсын мэдээлэлзүйн олимпиадад (IOI - International Olympiad in Informatics) бэлтгэгчдэд зориулав. Аль нэг жил олон улсын мэдээлэлзүйн олимпиадад оролцох гэж байгаа сурагчид өмнөх жилүүдэд ирсэн бодлогуудыг бодсон байх шаардлагатай байдаг. Харин зарим хүүхдүүд юмыг бүүүүр эхнээс нь эхлээд нэг ч бодлогыг алгасалгүй бодох хүсэлтэй байдаг. Ийм хүүхдүүдэд зориулав.
(бодлогын арай хялбаршуулсан хувилбарыг http://www.spoj.com/CSMS/problems/IOI1989/ дээрээс үзэж болно)
2*n тооны нүд бүхий дараалал өгөгдөв (n<=5). Хоёр хөрш нүд хоосон ба бусад нүднүүдэд n-1 ширхэг А, n-1 ширхэг В тэмдэгтийг байрлуулсан. n=5 үеийн жишээ:
|A|B|B|A| | |A|B|A|B|
Нүүдлийн дүрэм. Дурын хоёр дараалсан нүдэнд байгаа тэмдэгтийг, эрэмбийг нь алдагдуулахгүйгээр хоосон нүднүүд рүү зөөж болно.
Зорилго. Дээрх дүрмийг ашиглан бүх А тэмдэгтүүд бүх В тэмдэгтүүдийн зүүн талд гарсан байх байрлалд оруул. Хоосон нүднүүд хамгийн сүүлд хаана очих нь чухал биш.
Даалгавар. Дараах үйлдлүүдийг гүйцэтгэх програмыг бич:
А, В тэмдэгтүүд болон 0 (хоосон нүд) - ээс тогтох дарааллаар өгөгдөх байрлалыг гараас авна. Буруу байрлал өгөгдсөн тохиолдолд WRONG гэсэн гаралт гаргана.
Өгөгдсөн анхны байрлалын хувьд зорилгодоо хүрэх ямар ч зам байхгүй бол "IMPOSSIBLE" гэж хэвлэнэ
Зам байвал зорилгод хүрэхэд хамгийн цөөндөө хэдэн нүүдэл хийхийг заасан бүхэл тоог болон нүүдлүүдийг хэвлэнэ. Нүүдлүүдийн хувьд хоосон хоёр нүд рүү илгээгдэж буй дараалсан хоёр нүдний эхний нүдний дугаарыг хэвлэнэ.
Бодолт (үзэх)
No comments:
Post a Comment