Dreaming:
Энэ бодлого энэ удаагийн олимпиадын 2 дахь амархан бодлого байсан. Баярхүү сайн бодсон, бүтэн бодолт. Нэг илүү юмыг ярихад өнгөрсөн хавар улсын олимпиадад энэнээс хамаагүй хүнд модны бодлогыг бодсон 2 хүүхэд яагаад энийг бодож чадсангүй вэ?
За анализдаа ороё.
Бодлогын хариу 2 тохиолдолд байж болно. Нэг нь компонент бүрийн хамгийн урт замуудын хамгийн урт нь. Модны хамгийн урт замыг диаметр гэж нэрлэдэгийг хэлж байсан. Үүнийг 2 түвшний нэвтрэлт хийгээд эсвэл, гүний нэвтрэлт хийгээд орой бүрийн хувьд хамгийн урт 2 дэд модны нийлбэрээр тодорхойлогдоно. Одоо тэгвэл эдгээр компонентуудаа холбох ирмэг нэмбэл яах мөн аль орой дээр нэмэх вэ? Бид орой бүрийн хувьд хамгийн хол орших оройг жинтэй нь хамт ганц түвшний нэвтрэлт хийгээд олж чадна. Тэгвэл компонент бүрийн хувьд хамгийн хол замыг агуулсан оройг олоод үүнийгээ жингүүдээр нь эрэмбэлэе. Үүнийг модны радиус гэж нэрлэдэг, тус бүр r1 > r2> r3> .. гэж үзье. Тэгэхээр ядаж r1+r2+L эсвэл r2+r3+L гэсэн урттай зам байж таарна. Бодлогын хариу энэ 2-н их нь байна, яагаад?
Art Class:
Heuristic search төрлийн бодлого байх. Ийм төрлийн юм судлаж байгаагүй болохоор доривтой юм хэлж чадахгүй нь IOI-д ч ийм бодлого ирж байсан удаагүй. Гэхдээ толгойд байгаа бодолт, бодлогын хариу тухайн бүсэд байгаа өнгнүүдийн давтамжуудаас тодорхойлогдох нь харагдаж байна. Тэгэхээр тэрийг эвтэйхэн тооцоолоох хэрэгтэй. DP ашиглаад 2^6 хүртлэх бүх талтай бүх хэсэгүүдэд байгаа өнгөнүүдийн давтамжуудийг тоолчиж чадна. Зургийн төрөл бүрийн хувьд тухайн өнгний давтамжуудыг ойролцоогоор тооцоолчиж болно. Түүнтэйгээ жишээд хариугаа гаргах, ийм л юм толгойд байна.
