TCO 11 Elimination Round 2

Энэ үе хүртэл 850 хүн шалгарч үлдсэн ба шилдэг 350 оролцогч цааш оролцох авахаас гадна T-Shirt авна :). Өмнөх үед бусад Монголчууд маань шалгарч чадаагүй учир ганцаараа оролцов. Ганц дайчин юу гэдэг билээ :D.
Division 1: Khongor

Тэмцээн эхэллээ. Бодлогуудын оноо 250, 500, 1000 байсан учраас medium-г бодох боломжтой гэж таамаглалаа. Эхлээд easy буюу 250 онооны бодлогыг нээлээ.
250:
Зөвхөн Y,N үсгээс тогтох тэмдэгт мөрийг "баримт" гэж нэрлэе. Тэмдэгт мөрийг 1-с эхлэн индекслэх ба хэрвээ i-р үсэг Y байвал тоо i-д хуваагдана, N байвал хуваагдахгүй. Өгөгдсөн (<=1000000) урттай өөрт нь ядаж нэг тоо тохирох нийт "баримт"-н тоог ол.
Бодлогыг оролдсоор байсан ч нэг л болж өгөхгүй, санаа орж ирэхгүй, цаг өнгөрсөөр нэг хартал 20 минут өнгөрчээ. Маш олон хүмүүс хурдтай бодож байсан болохоор би одоо энэ бодлогыг бодсон ч цаашид шалгарч чадахгүй нь тодорхой байсан. Тийм учраас эцсийн боломж болох medium-ээ нээлээ.

500:
s,t 2 тэмдэгт мөр өгөгдсөнө. C(i,j) (i=0..n) (j=0..m) тэмдэгт мөрөн хүснэгтийг дараах аргаар үүсгэе. Эхлээд C(0,j) дагуу s тэмдэгт мөрийг, C(i,0) дагуу t тэмдэгт мөрийг бичнэ. Үлдсэн нүднүүдийг C(i,j)=min(C(i,j-1),C(i-1,j))+max(C(i,j-1),C(i-1,j)) буюу зүүн болон дээд талын нүдэн дэх 2 тэмдэгт мөрийн цагаан толгойн дарааллаар бага дээр нь нөгөөг нь залгах байдлаар үүсгэнэ. Таны даалгавар C(n,m) нүдэн дэх тэмдэгт мөрийн ямар нэгэн хэсгийг олох юм. Хэсгийн урт 50-с хэтрэхгүй. Хамгийн хэцүү зүйл нь C(n,m) дээр үүсэх тэмдэгт мөрийн урт 10^18 байж болно. Иймээс шууд үүсгэх боломжгүй. Хэрвээ C(n,m)-н ямар нэг үсгийг олж чаддаг бол бүх үсгүүдийг залгаснаар бодлогыг бодож болно. Ямар нэгэн K дах үсгийг олохдоо зүүн тал эсвэл дээд талын алинд хамаарагдахыг олсноор бодлогыг бодож болно. Хялбар сонсогдож магадгүй ч нэлээд хэцүү бодлого байсан. Хамгийн гол нь Topcoder-н тэмцээн 75 минут үргэлжилдэг учраас хурдан бодох хэрэгтэй. Ямар ч байсан бодлогыг бичиж дууслаа, 4 минут үлджээ :). Тэмцээний дүнг харлаа, хэрвээ medium маань давах юм бол 350-д багтна.

System Test дуусч бодлого минь давлаа, бөөн баяр :). Одоо мэдээж ханах болоогүй шилдэг 150-д орох хэрэгтэй :D.