Olimpiad Bod

3507. Миний дэлгүүр Бодлогын дугаар: CSMS0062 2108 он гэхэд Миний дэлгүүрийн сүлжээ Монгол орон даяар тархсан байв. Энэ үед Монгол улс n ширхэг аймагт хуваагдсан байсан ба аймаг бүр өөрийн төвтэй болсон байна. Харин аймгуудын төв бүрт Миний дэлгүүрийн нэг салбар байна. Тэдгээр нь хоорондоо бараа тээвэрлэхдээ тийрэлтэт пуужин ашиглана. Аймгийн төвүүдийн хоорондох зайнаас хамааран нэг удаа тийрэлтэт пуужингаар ачаа тээвэрлэх үнэ харилцан адилгүй байна. Миний дэлгүүрийн захирал Их хуралд сонгогдсон тул Зам тээврийн яамнаас хоорондоо тийрэлтэт пуужингаар тээвэр хийж болох аймгуудын нэрс болон тэдгээрийн бүгдийнх нь үнэ тарифуудыг нууцаар олж авчээ. Ингээд салбар дэлгүүр хоорондын ачаа тээвэрлэлтийн зардлыг багасгахын тулд эдгээр хурдтай тээвэрлэлтүүдээс хэдийг нь сонгон авч хэрэглэхээ сонгох хэрэгтэй болсон байна. Сонгон авсан тээвэрлэлтүүдийг ашиглан аль ч дэлгүүрээс бусад дэлгүүрүүдийг дамжин (эсвэл шууд) бусад бүх дэлгүүрүүд рүү ачаа хүргэж болдог байна. Ийм шинж чанарыг хангасан бөгөөд нийт үнэ нь хамгийн бага байх тээвэрлэлтүүдийг сонговол хамгийн ашигтай сонголт болох байв. Гэвч хамгийн ашигтай хувилбарыг сонговол Зам тээврийн яамнаас нууцаар мэдээлэл авсан нь илэрхий болох тул захирал хамгийн ашигтай хувилбарын дараагийн хувилбарыг сонгон авахаар шийджээ. Миний дэлгүүрийн захиралд тус болж хамгийн ашигтай ба түүний дараах хувилбаруудын тээвэрлэлтүүдийн үнийн нийт дүнг олох програм бич.Input Эхний мөрөнд нийт аймгуудын тоо болох n (2<=n<=500) бүхэл тоо болон пуужингаар хийгддэг тээвэрлэлтийн тоо болох m бүхэл тоо өгөгдөнө. Дараагийн m мөрөнд тээвэрлэлт хийгдэж буй хотуудын дугаар ai, bi (1<=ai, bi<=n) болон тээвэрлэлтийн үнэ болох wi (0<= wi <=1000) тоонууд байрлана. Хэрэв А хотоос Б хот руу тээвэрлэлт хийгддэг бол Б хотоос А хот руу мөн адил зардлаар тээвэрлэлт хийж болдог байна. Дурын хоёр хотын хооронд нэгээс илүүгүй тээвэрлэлт хийгдэнэ. Дурын хотоос бусад хотууд руу шууд эсвэл дамжин өнгөрөх аргаар ачаа хүргэж болдог байна. Output Хамгийн ашигтай хувилбарын тээвэрлэлтийн нийт зардал болон түүний дараагийн хувилбарын тээвэрлэлтийн нийт зардлыг нэг нэг мөрөнд хэвлэнэ. Хамгийн ашигтай хувилбар хэд хэд байвал аль нэгийнх нь нийт зардлыг хэвлэнэ. Аль нэг хувилбар нь байх боломжгүй бол -1-ийг хэвлэнэ. Example Input: 4 6 1 2 2 2 3 2 3 4 2 4 1 2 1 3 1 2 4 1 Output: 4 4 Input: 3 2 1 2 2 2 3 2 Output: 4 -1

3512. КолаБодлогын дугаар: FJNF0801 Coca cola компани Fuji infox компанийн менежерт дараах саналыг тавив. Coca cola компани зар сурталчилгааны өдөрлөгтөө дараах асуудлыг хүмүүст тавих гэсэн боловч тооцоолж чадахгүй байгаа болохоор Fuji infox компанийн программистуудаас нь тусламж авахаар болов. Энэхүү асуудал нь төрөл бүрийн хэмжээтэй лонхонд ундаанууд хийж тавиад яг дараалсан гурван лонхонд байгаа ундаануудыг ууж болохгүй нөхцөлд тэдгээрээс хамгийн ихдээ хичнээн хэмжээний ундаа уух боломжтойг тогтоох хэрэгтэй болно.Гэхдээ ууж дууссаад хоосон лонхыг байранд нь буцааж тавина. Уухдаа нэг лонхондохоо ууж байж дараагийн лонхыг сонгох ёстой. Энэ асуудлыг хэрхэн шийдвэрлэх вэ? Та туслана уу! Input Эхний мөрөнд лонхны тоо N (N>=4) , дараагийн N мөрүүдэд лонхнуудын хэмжээг илэрхийлсэн Vi натурал тоонууд байрлана. Output Ууж болох хамгийн их ундааны хэмжээнээс тогтоно. Бусад хязгаарлалт: N<=1000, Vi<10000.

Example Input: 6 6 10 13 9 8 1

Output: 33 Тайлбар: Эхлээд 1,2,4,5-ийг сонгоход.

Бодлогын дугаар: FJNF0802 Эрт цагт Европийн нэгэн жижиг тосгонд нэртэй цуутай цуурхал тараадаг хүмүүс байдаг байлаа. Өглөө бүр эдгээр хүмүүс тухайн тосгонд хэний ч мэдэхгүй, сонсоогүй дуулаагүй сонин содон зүйлийг мэдэж авдаг байлаа. Тэгээд өдөржингөө хоёр хоёроороо уулзаж мэдсэн сонссоноо ярьж чалчдаг байв. Бидний асуудал бол яриа хөөрөө, цуурхаж ярьсан бүх зүйлийг бүх алдартангууд маань тэр өдөртөө мэдэж чадсан эсэхийг тогтоох програм бичих явдал юм. Та туслана уу!

Input Оролт хэд хэдэн тестүүдээс тогтох бөгөөд эдгээр тестүүд нь хоорондоо хоосон мөрөөр тусгаарлагдан байрлана. Тоо ширхэг нь өгөгдөхгүй. Тест бүрийн эхний мөр нь N ба M хоёр натурал тооноос тогтоно. N бол нэртэй цуутай цуурхал тараадаг хүмүүсийн тоо. M бол тэдгээрийн уулзалтын тоо. Дараагийн N мөрөнд тэдгээрийн нэрс, харин дараагийн M мөрөнд уулзалтуудын мэдээлэл байрлана. Уулзалтын мэдээлэл хоорондоо хоосон нэг зайгаар тусгаарлагдан байрлах нэрсээс тогтоно. Оролтын сүүлчийн мөрөнд хоосон зайгаар тусгаарлагдсан 0 0 (тэгүүд) байрлана. Урдаа нэг хоосон мөртэй байна.

Output Гаралтанд тест болгоны хувьд цуу ярианууд хэрэв бүх алдартангуудад маань тэр өдөртөө хүрсэн бол YES, эсрэг тохиолдолд NO гэсэн үгүүд мөр бүрд байрлана. Бусад хязгаарлалт: Нэрийн урт хамгийн ихдээ 12 тэмдэгт, N<=300, M<1000

Example Input: 3 3 Alice Bob Cindy Alice Bob Bob Cindy Cindy Alice 4 4 Kirk Lucy Mike Nancy Kirk Lucy Lucy Mike Mike Nancy Nancy Lucy 0 0 Output: YES NO