Wednesday, May 21, 2014

CF #247. В. Шүршүүр

Өглөө бүр дотуур байрны шүршүүрийн үүдэнд таван оюутан зогсч оочерлодог.
Шүршүүр нээгдэхэд эхний оюутан орно. Хэсэг хугацааны дараа оюутан гарахад дараагийнх нь орох гэх мэтээр дараалал дуустал үргэлжилнэ.
Дараалалд зогсох үедээ оюутнууд хоорондоо ярилцдаг. Гэхдээ дарааллын (2i-1)-р оюутан 2i-р оюутантай гэсэн зарчмаар хос хосоороо ярилцана.
Жишээ авч үзье. Оюутнуудыг 1-ээс 5 хүртэл тоогоор дугаарлая. Эхлээд оюутнууд 23154 гэсэн дарааллаар зогсч байсан гэе (2-р оюутан дарааллын эхэнд байгаа). Шүршүүр нээгдэх хүртэл 2, 3-р оюутнууд, 1, 5-р оюутнууд хоорондоо ярилцах ба 4 хэнтэй ч ярилцахгүй. Дараа нь 2 шүршүүрт орно. 2-ыг шүршүүрт байх хугацаанд 3, 1-р оюутнууд, 5, 4-р оюутнууд тус тус хоорондоо ярилцана. Дараа нь 3 шүршүүрт орно. 1, 5 хоёр хоорондоо ярилцах ба 4 хэнтэй ч ярилцахгүй. Дараа нь 1 шүршүүрт орсон хойгуур 5, 4 хоёр ярилцана. Дараа нь 5 орж, эцэст нь 4 орно.
Хэрэв i болон j оюутнууд ярилцаж байгаа бол i оюутан g[ij] хэмжээгээр баярлаж, j оюутан g[ji] хэмжээгээр баярладаг.
Тэгвэл оюутнуудын баяр баясгалангийн нийт хэмжээ хамгийн их байх тийм дарааллыг ол.
Зарим оюутнууд хэд хэдэн удаа хоорондоо ярьж болохыг анхаар. Жишээ нь 1, 5 хоёр шүршүүр онгойхоос өмнө болон 3-г шүршүүрт байх үед гээд хоёр удаа ярилцаж байгаа.

Оролт
Таван мөрөнд таван тоонууд өгөгдөх ба энэ нь g[ij](0 ≤ g[ij] ≤ 10^5) тоонууд юм. Бүх i-гийн хувьд g[ii]=0 байна.
Оюутнуудыг 1-ээс 5 хүртлэх тоонуудаар дугаарласан гэж үз.

Гаралт
Оюутнуудын нийт баяр баяслын хамгийн дээд хэмжээг илэрхийлэх ганц тоог гаргана.

No comments: