Topcoder Diary - SRM 480 (Division 2)

Яагаад ч юм өмнө нь тэмдэглэж авсан дээр маань өглөө 7-цагаас болно гэчихсэн байхаар нь хар эрт 6 цагт сэрээд бүртгүүлчихээд харсан чинь 9 цагаас эхэлнэ гэж байдаг юм даа. И-мэйл-ээр ирсэн хуваарь дээрээ бол яалт ч үгүй 9 цагаас л байна лээ л дээ :P Бүүр сарын өмнөөс календарь дээрээс нь тэмдэглэж авсан болохоор дөхүүлээд цагаа өөрчилдөг ч байж магадгүй. Эсвэл би будилж бүтэлгүйтсэн бололтой ^^

Энэ удаа манайхаас доорх хүмүүс оролцжээ.
Div1-д: Khongor, Chamka
Div2-д: Khuyagbaatar, lmo0731, gmunkhbaatarmn, nursoltan_h, Jaamaa^{2nd contest!}, almabek, Jaamaa

Coding phase

Easy
Мөн л өмнөх шигээ хурдан бодчихлоо. Шууд тэстээ гүйлгэж хараад л ямархуу үйлдэл хийхээ баримжаалаад л өгүүлбэрээ нэг уншаад л бодолтондоо орсон. Ойрд practice хийгээгүйн гай гарч дэмий юман дээр цаг алдсаныг эс тооцвол дажгүй шүү. 250-аас 247 оноо. (Ойрд яасан романтик оноо аваад байна аа ^^)

Medium
Үнэхээрийн хайнга бодсон доо. Өгүүлбэр нь амархан санагдаад, за энийг л бодчихвол энэ тэмцээний норм хангагдчих юм чинь гээд яарсан ч үгүй :P 500-аас 354 оноо.

Hard
Анх тэмцээн эхлэхэд 900 онооны бодлого болохоор нь (ихэнхдээ 1000 байдаг) энэ ч өмнөхүүдээ бодвол амархан "hard" байгаа байхдаа гэж бодсон. Уг нь өгүүлбэрийг нь ойлгочихвол маний эзэмшсэн зэвсгийн эрдмээр бол нухчихаар л эд байна гэж бодоод өөрийгөө зоригжуулаад нэлээн нухлаа. Өрөөн дотроо баахан дэмий эргэцүүлж ганцаараа ярин байж жаал жуул нууцад нь нэвтэрлээ :) Greedy + Brute Force (элэмэнтүүдийнхээ алийг нь төгсгөлд нь тавих вэ гэдгээ бүгдийг нь шалгаж үзнэ)
Яг бодчихоод тэстэлтэл нэг л биш ээ, сайн харлаа. Дахиад сайн харлаа. Тэнэг чинь бодлогын өгүүлбэрийн 3 дахь нөхцлийг огт тооцоогүй байна шд (үнэхээр тэнэг байгаа биз?) Тооцоондоо багтаахад нэг их төвөг орсонгүй. Хугацаа дуусахаас 4 минутын өмнө submit хийлээ. 900-аас 407 оноо.

Challenge phase

Огт сорилт (challenge) хийсэнгүй.

System test phase

Waiting ^^
500-дээрээ алдчихсан юм шиг байна (Lmo`s analiz :D)

IOI Day 2 Бодлого 2

Бодлого 2: Traffic Congestion.

Канад улсын иргэд хокэй үзэх үнэхээр дуртай. Тэд хокэйг шууд талбай дээр нь үзэхийн тулд улсын өнцөг булан бүрээс ирдэг. Харин тэмцээн дууссны дараа бүгд машиндаа суугаад харих хэрэгтэй ба ганц бэршээл нь маш их машин ирсэн учраас зам дээрх машины тоо хэтэрхий ихсэнэ. Нэгэн баян үйлдвэрийн эзэн хоккэйн баг худалдаж авсан ба түүндээ зориулж шинэ талбай барих болов. Таны даалгавар бол энэ баякаад тусалж хоккэйн талбай барих хамгийн тохиромжтой хотыг олно уу. Тохиромжтой гэдэг нь тэмцээн дууссны дараа зам дээр яваа машины тоог хамгийн бага байлгахаар хот юм.

Канад улс нь хоорондоо 2 чиглэлт замаар холбогдсон хотуудаас тогтоно. Аль нэг 2 хотын хооронд яг ганц замын маршруттай. Барих шинэ талбай нь энэ хотуудын аль нэг хотод баригдах ёстой. Мэдээж тэмцээн дууссны дараа тухайн хотын иргэдээс бусад нь бүгд машиндаа суугаад харьж таарна. Тухайн зам дээрх машины тоо нь тухайн замыг ашиглаж өөрийн хотдоо очиж байвал эдгээр хотуудын хоккэй-д дуртай хүмүүсийн нийлбэр байна. Таны програм талбай баригдсан хотын хамгийн их машин явах замын машины тоог хамгийн бага байлгах ёстой. Олон хариу байхыг үгүйсгэхгүй ба энэ тохиолдолд аль нэгийг гаргаж болноо. Та LocateCentre(N,P,S,D) процедурыг зохиох ба энд N нь бүх хотуудын тоог илтгэх эерэг бүхэл тоо, хотуудыг 0-ээс N-1 хүртэл дугаарлана, P нь N ширхэг тоог агуулсан массив байх ба 0<=i<=N-1 байх P[i] болгонд i-р хотын хоккэй үзэх фанатуудын тоо. Бүх хотуудад байгаа фанатуудын тоо нь хамгийн ихдээ 2 000 000 000 байх болно. S болон D нь мөн массив байх ба тус бүр N-1 элементтэй. S[i] D[i] нь энэ 2 хотын хооронд замтайг илтгэнэнэ. Таны зохиосон процедур зөвхөн талбайг барих хотын дугаарыг буцаах ёстой.

Жишээ: Доорх жишээнд эхний зурганд 0 1 2 гэсэн хотууд тус тус 10 хокэй сонирхохгчтой, 3 4 гэсэн хотууд тус бүр 20 сонирхогчтой. 2 дахь зурганд хокэйн талбайг 2 гэсэн дугаартай хотод барьвал хамгийн их машинтай зам нь 40 болохыг харуулж байна.3 дахь зурганд талбайг 3 гэсэн хотод барьвал хамгийн их машинтай зам нь 30 болохыг харуулсан байна. Эндээс 3 дугаартай хот нь 2 дугаартай хотоос илүү тохирох болохыг харуулж байна.





Эхний 25 онооны тест нь:

Хотуудыг зүүнээс баруун хүртэл шулуун шугаман байрлуулсан гэж үз. Ямар ч мөчөр байхгүй. Эндэ хамгийн ихдээ 1000 хот байна.

2 дахь 25 онооны тестүүд:

Хотууд адилхан шугаман байрлуулсан ба хамгийн ихдээ 1 000 000 хотууд байгаа гэж үд

3 дахь 25 онооны тестүүд:

Шугаман байх албагүй ба хамгийн ихдээ 1000 хот байгаа гэж үз

4 дахь 25 онооны тестүүд:

Мөн шугаман байрлах албагүй ба хамгийн ихдээ 1 000 000 хот байгаа гэж үз.

IOI Day 2 Бодлого 1

Бодлого 1: Memory
Жак Мемори гэдэг тоглоом тоглох дуртай ба энэ тоглоом нь 50 ширхэг хөзөрөөр тоглодог ба хөзөр бүр дээр латин цагаан толгойн A-Y үсэг наасан байгаа. Тэгэхээр нэг үсэг яг 2 ширхэг байна. Тоглохдоо хөзөрөө хольж байгаад үсэг наасан талыг доош нь харуулан тавиад хоёр хоёр хөзөр сонгож тухайн үсэгнүүдийг хараад буцааж доош нь харуулж тавина. Хэрэв сонгосон 2 хөзөр адилхан байвал Жак ээжээсээ чихэр авах юм. Хэрэв дахин нөгөө 2 хөзөрөө гаргаад ирвэл дахиж чихэр авахгүй. Энэ тоглоом нь Жак 25 ширхэг чихэрээ авсны дараа дуусах юм. Таны даалгавар бол Жакыг орлох Play процедурыг зохиох явдал юм. Таны програм тест зохиогчидын хэрэгжүүлцэн байгаа faceup(C) функцыг дуудах ёстой ба энэ функц нь C дугаар хөзөр дээрх үсгийг буцаана. С нь мэдээж 1-ээс 50 хооронд байх ба таны сөхөж үзэх хүсэлтэй тоо юм. Хөзөр сөхө явцад 2 дахь сөхсөн хөзөр болгоны дараа тухайн сонгосон 2 хөзөрийг доош нь харуулан дахин тавина. Таны зохиосон процедур зөвхөн Жакыг 25 чихрээ авсан тохиолдолд л дууса юм.
Жишээ:

Дуудалт	Буцаасан утга	Тайлбар
faceup(1)	'B'	1-р хөзөрт B үсэг.
faceup(7)	'X'	7-р хөзөрт X үсэг. Сонгосон 2 хөзөр маань адилхан биш
Нээсэн 1 болон 7-р хөзөрүүд буцаан доош харуулан тавигдана
faceup(7)	'X'	7-р хөзөрт X үсэг.
faceup(15)	'O'	15-р хөзөрт O үсэг. Сонгосон 2 хөзөр маань адилхан биш
Нээсэн 7 болон 15-р хөзөрүүд буцаан доош харуулан тавигдана
faceup(50)	'X'	50-р хөзөрт X үсэг.
faceup(7)	'X'	7-р хөзөрт X үсэг. Сонгосон 2 хөзөр ижил учир Жак эхнийхаа чихэрийг авав.
Нээсэн 50 болон 7-р хөзөрүүд буцаан доош харуулан тавигдана
faceup(7)	'X'	7-р хөзөрт X үсэг.
faceup(50)	'X'	50-р хөзөрт X үсэг. Сонгосон 2 хөзөр ижил гэвч чихэр авахгүй.
Нээсэн 7 болон 50-р хөзөрүүд буцаан доош харуулан тавигдана
faceup(2)	'B'	2-р хөзөрт B үсэг.
...
(энэ мэтчилэн функцууд дуудагдсаар)
...
faceup(1)	'B'	1-р хөзөрт B үсэг.
faceup(2)	'B'	2-р хөзөрт B үсэг. Жак 25 дахь чихэрээ авав.

Эхний 50 оноо: хугацаандаа амжиж ажиллаад байвал авч чадна.
2 дахь 50 оноо: faceup(C) функц 100-аас илүү дуудагдах ёсгүй.

IOI2010 Day 1 Бодлого 4

Бодлого 4: Language
Таньд Википедиа-гаас ямар нэгэн билэг өгөгдсөн бол ямар хэл болохыг нь таана уу. Оролдсон оролдлогоо ашиглан зөв хариуг ол. Хэл болгон 0<=L<=55 тоогоор төлөөлөгдөнө. Бүх бичлэгүүд яг 100 тэмдэгтээс тогтох ба, үүнийг бүхэл тоон төрлийн 100 элементтэй 1-ээс 65535 хүртлэх утга авах E массив төлөөлнө. Та excerpt(E) процедурыг зохиох ёстой. Таны процедур language(L)-г дуудах ёстой ба хэрэв language(L) = L бол зөв гэж үзнэ. Таны excerpt(E) нийт 10000 удаа дуудах ба хэдэн бичлэгийн хэлний кодыг зөв олсноор нь таны програмын хэр оновчтойг тодорхойлох болно. Жишээ энтэрийг эндээс үзнүү :D.

IOI2010 Day 1 Бодлого 3

Бодлого 3: Quality of living.
Албертаа дахь хотуудыг дөрвөлжин шугамтай цаасан дээр хойноос урд хүртлэхийг 0-ээс R-1 хүртэл дугаарлаж, баруунаас зүүн хүртлэхийг 0ээс C-1 хүртэл дугаарлан дүрслэж болох юм. Хот бүрийн чансааг тогтоосон байдаг ба тухайн нүд бүрт тухайн хотын чансааг илтгэх 1-ээс R*C тоог бичсэн байгаа. Чансаа нь 1 байвал хамгийн өндөр чансаа, R*C хамгийн муу. Хот төлөвлөлтийн газар дундаж чансаа хамгийн өндөр HxW хэмжээтэй тэгш өнцөгт газрыг сонгож авахыг хүсч байгаа. H W нь R C тоонуудаас тус бүр хэтрэхгүй сондгой тоонууд байх болно. Ямар нэгэн H W хэмжээтэй тэгш өнцөгт газрын хувьд дундаж чансааг дараах байдлаар тодорхойлно. Дундаж чансаа нь уг газрын аль нэг нүдэн дэх чансаа байх бөгөөд уг чансаанаас бага чансаатай нүдний тоо нь уг чансаанаас их чансаатай нүдний тоотой тэнцүү. Өөрөөр хэлбэл H W ширхэг тоог цувуулж бичээд эрэмбэлэхэд голын тоо нь гэсэн үг. Таны даалгавар бол бүх H W хэмжээтэй тэгш өнцөгт газрууд дотроос хамгийн сайн (утгаараа бага) дундаж чансааг олох rectangle(R,C,H,W,Q) процедурыг зохиох юм. Энд Q нь Q[a][b]-д орших хотын чансааг агуулсан массив юм.

R=5, C=5, H=3, W=3, 
Q=  5 11 12 16 25
17 18  2  7 10
4 23 20  3  1

24 21 19 14  9
6 22  8 13 15

rectangle(R,C,H,W,Q)=9
Дээрх жишээнд m=9 мөн бодлогын нөхцөлыг хангах хотуудыг дотруулсан байна.
Жишээ2:

R=2, C=6, H=1, W=5, 
Q=  6  1  2 11  7  5
9  3  4 10 12  8

rectangle(R,C,H,W,Q)=5

IOI2010 Day 1 Бодлого 2

Боодлого 2: Hotter Colder
Жак Жилл 2 Хоттер Колдер гэх тоглоом тоглдог. Жилл 1-N хүртлэх тооноос нэгийг санаж, Жак таахыг хэд хэдэн удаа оролдоно. Мэдээж Жак-н хэлж буй тоонууд нь 1-N завсарт байх ба оролдлого бүрт Жак hotter, colder, same гэсэн хариултыг өгнө. Жакын эхний оролдлогонд Жилл same гэсэн хариултыг өгнө. Үлдсэн оролдлогуудад Жилл дараах нөхцөлийг харж хариултаа хэлнэ.
• Хэрэв Жиллын санасан тоонд Жакын одоогийн хэлсэн тоо нь Жакын өмнөх оролдлогонд хэлсэн тооноос илүү ойрхон байвал hotter.
• Хэрэв Жиллын санасан тоонд Жакын одоогийн хэлсэн тоо нь Жакын өмнөх оролдлогонд хэлсэн тооноос илүү хол байвал colder.
• Хэрэв хол ч биш ойрхон ч биш бол same.
Таны даалгавар бол Жакын үүргийг гүйцэтгэх HC(N) програм зохио. Guess(G) нь 1<=G<=N ба 1 утга буцаавал hotter -1 утга буцаавал colder, 0 утга буцаавал same . HC(N) функц нь Жиллын санасан тоог буцаах ёстой.
Жишээ.
Доорх жишээнд N=5 мөн Жилл 2 гэсэн тоог санасан болно.

Дуудалт	Буцаасан утг	Тайлбар
Guess(5)	0	Same анхны дуудалтаар буцаана гэж байгаа
Guess(3)	1	Hotter
Guess(4)	-1	Colder
Guess(1)	1	Hotter
Guess(3)	0	Same

IOI2010 Day 1 Бодлого 1

Бодлого 1: Cluedo
Эрхэм Хар( hehe ) хүн амьний хэрэгт холбогдов. Мөрдөгч Жилл алуурчид, хэргийн газар, хэрэг үйлдсэн зэвсгүүдийг илэрүүлсэн байв. Энд 1ээс 6 хүртэл дугаарласан сэжигтэй алуурчид 1ээс 10 хүртэлх сэжигтэй хэргийн газар, мөн 1ээс 6 хүртэл дугаарласан сэжигтэй зэвсэгүүд байв. Жилл эдгээр илэрүүлсэн зүйлүүдээ ашиглаад байж болох хослолуудыг зохиогоод үүнийгээ Theory гэж нэрлэв. Мөн Жилл өөрийн туслах Жак-д хэлж үүнийг үнэн эсэхийг шалгах даалгавар өгөв. Хэрэв Жак Жиллийн хэлсэн Theory-г үнэн гэдэгийг баталж чадвал Жиллийн ажил дуусна. Эсрэг тохиолдолд Жилл дахин өөр боломжтой Theory-г Жак-д санал болгоно.
Таны даалгавар бол Жилл-ийн үүргийг сайн биелүүлэх процедур зохиох явдал юм. Таны функцийг маш олон удаа дуудах ба дуудагдах бүрд Theory(M,L,W) байна. Энд M-алуурчины дугаар, L-хэрэг болсон газарын дугаар, W-зэвсэгийн дугаарыг агуулсан theory байна. Таны функц 0 утга буцаавал Жак баталж чадсан эсрэг тохиолдолд буюу 1 2 3 гэсэн аль нэг утга буцаавал няцаагдах юм. Эндэ 1-алуурчин буруу, 2-хэргийн газар буруу, 3-зэвсэг буруу гэдэгийг илтгэнэнэ.

Дуудалт	Буцаасан утга	тайлбар
Theory(1, 1, 1)	1, or 2, or 3	3-уулаа буруу
Theory(3, 3, 3)	1, or 3	Зөвхөн хэргийн газарыг зөв оруулжээ
Theory(5, 3, 4)	1	Зөвхөн алуурчинг буруу оруулжээ
Theory(2, 3, 4)	0	Энэ удаад баталж чаджээ.

Topcoder Diary - SRM 479 (Division 2)

Энэ удаа манайхаас доорх хүмүүс оролцжээ.
Div1-д: Chamka, XaCaHaa, lmo0731
Div2-д: Khuyagbaatar, gmunkhbaatarmn, nursoltan_h, almabek, Jaamaa^new!

Coding phase

Easy
Өмнөх SRM дээр туршиж үзсэн аргаар эхлээд тэстээ гүйлгэж хараад дараа нь бодлогынхоо өгүүлбэрийг харлаа. Овоо хурдан ойлгочихлоо. Амархан ч бодлого юм. 250-аас 247.92 оноо. (Хувийн рекорд ^^)

Medium
За ёстой бүү мэд. Эхлээд greedy маягийн юм бичиж үзсэн болоогүй. Дараа нь нэг юмыг нь л sort хийх хэрэгтэй юм байна гэж бодсон. Тэрийгээ хайсаар байгаад цаг дуусгалаа даа :(

Hard
Нээж ч харж амжсангүй :)

Challenge phase

500 онооны бодлогыг нэг нөхөр хэтэрхий хялбарчлаад бодчихсон байсныг нь нээж үзээд ямар тэст зохиох вэ гэж бойтоглох зуур хэн нэгэн нь өрсчихвөө. "Challenge Succeeded". Өөр онц юм болсонгүй. Манай өрөөнд 1000-онооны бодлогоо бодсон хүн ч гарсангүй. 250 дээр алдаж магадгүй юм ч байсангүй. 500-гийн тухайд бол систем тэст дээр нэлээн их хүн унах байх даа :D

System test phase

Waiting ^^

Topcoder Diary - SRM 478 (Division 2)

За ёстой бөөн адал явдал гэхээс өөр юу гэхэв. Тэмцээн болтол түр гараад ирьюүү гээд гарчихаад ирсэн чинь тэмцээн эхэлснээс бараг 10 минутын дараа л орж ирж таардаг юм даа. Ямар азаар бодолтын цагийг бодлогоо нээж харсанаас хойш тооцдог юм бэ :)
Энэ удаа манайхаас доорх хүмүүс оролцжээ.

Div1-д: Khongor
Div2-д: XaCaHaa, lmo0731, ChNbLd, gmunkhbaatarmn, nursoltan_h, almabek

Coding phase

Easy
Урьд нь бодлогынхоо өгүүлбэрийг уншаад дараа нь тэстээ уншаад, тэгээд бодлогын өгүүлбэрээ уншаад, дахин тэстээ уншаад гэх мэтчилэн 4-5 удаа эргэцүүлсэний эцэст бодлогынхоо өгүүлбэрийг ойлгодог байсан бол энэ удаад шууд л эхэлж тэстээ хараад л бодлогынхоо баримжааг аваад л өгүүлбэрийг нь уншсаны дараа дахин нэг удаа тэстээ хальт харчихаад л бодолтоо бичиж эхэллээ. Овоо хурдан амжуулчихлаа. 233 оноо :)

Medium
Уншаад л. "Ээ за энэ удаад ч 500-гийн бодлогыг барна гэдэг худлаа болчихлоо" гэсэн шүү юм бодогдоод угаасаа хоцорч ирсэн энэ тэрийг тооцвол энэ тэмцээн угаасаа худлаа болчихлоо гээд л цухалдаж эхэндээ баахан суусаныг эс тооцвол дажгүй шүү :P
Эхний үйлдлийг A, дараагийн үйлдлийг B гэвэл. A*B = B*A, A*A*A=B*B болж таарахыг анзаарчихвал бодлого хялбарчлагдана. Өгөгдсөн тоон дээрээ A үйлдлийг л давтан хийсээр байна. Дараа нь 3 удаа A үйлдэл хийгдсэн болгоныг 2 B үйлдэл хийсэн гээд тоолчиход хангалттай. 262 оноо.

Hard
Хэсэглэл л байгуулаад BruteForce хийж болох юм шиг байсан. Гэхдээ хугацаандаа амжихгүй юм шиг санагдсан. Ямартаа ч би лав үлдсэн хугацаандаа хэсэглэл байгуулах гээд амжсангүй :P

Challenge phase

1000 онооны бодлогоо барахаасаа өнгөрлөө гээд чаат-лог хараад сууж байсан чинь 2 шинэков бололтой нөхөр 1000 онооны бодлогоо бараг л нээж харангуутаа эргээд submit хийж байх юм. Шууд л дотроо хүйтнээр инээгээд алгаа үрж challenge phase-г хүлээгээд эхлэнгүүт нь нөгөө хоёрын 1000-онооны бодлогыг дараалан унагаад сул +100 авав. Уг нь ингээд гоё эхэлсэн юм аа. Тэгсэн чинь нэг нөхрийн 250 онооны бодлого нь хугацааны хязгаарлалтаа давчих юм шиг санагдахаар нь 3 удаа амжилтгүй challenge хийгээд -75 оноо. Хаха. Уг нь сул авсан 100 оноогоо хадгалж байсан бол 560 оноотойгоор өрөөндөө нэгт нийт дүнгээр эхний 40-д багтах л байлаа. Гэхдээ энийг бичиж байх хооронд системийн тэст дуусчихаж өрөөндөө 3-рт div2-тоо 55-р байр. Юундаа ч гонсойхов :)