Тэмцээн - 1

Юуны өмнө тэмцээнд оролцсон хүмүүст баярлалаа. Бас эхний байруудад орсон idiot, tvvv, Adya 3т баяр хүргэе.
Одооноос кодер дээрх тэмцээнүүдийг Тэмцээн тэд гэж нэрлэнээ. хэхэ, гадны сайтуудыг л дагаж байнадаа. Тэмцээний цагийг бас иймэрхүү орой хийвэл яаж байна саналаа үлдээгэрэй. Бодлогуудын хувьд бас л гадны сайтуудаас бодсон бодлогуудаас ишлэж зохиосон, тэстүүдэд бас их цаг гаргаж TRICKY тэстүүд их оруулсан. Ингээд бодлогын анализ хийе.
Эргэлт
Энэ хамгийн амархан бодлого байсан байх. Мөрийн дагуу хэд эргэх баганы дагуу хэд эргэхийг бодож үзсэн бол хариу: min(n*2-2, m*2-1)
35
Мэдээж цөөн сав хэрэглэхийн тулд аль болох 5-н сав ашиглах хэрэгтэй. Хэрэв N тоо 5-д хуваагдахгүй бол ядаж нэг удаа 3-н сав ашиглаж ёстой.
Бага тоо
Шууд хүчээр тоог 1-ээр ихэсгээд бодлогын шаардлагыг хангах тоог гаргаж авж болно. Хэрэв саяас илүү удаа 1-ээр нэмэгдүүлэх үйлдэл хийсэн бол шийдгүй юм. Өөр нэгэн бодолт өгөгдсөн тоон оронгийн тоонуудыг бүх боломжоор сэлгэж бодлогын хариуг гаргаж болно. N<=999999 учир бид хамгийн ихдээ 6! үйлдэл хийгдэх юм.

Тэгш өнцөгт

Энэ бодлогын өгүүлбэрийг их буруу бичсэнүү, хүмүүс ойлгох гэж цагаа их алдсан байх. Энэ бодлого нь codeforces.com дээр бүх боломжийг шалгахаар бодож болохоор өгөгдсөн ба та эндээс харж болно. Харин би хязгаарлалтыг сая болгож бүх боломжийг шалгах боломжгүй болгосон юм. Миний бодолт бол динамик програмчлал ашиглах ба left[i]-ээр тухайн i-р тэгш өнцөгтийн зүүн талд орших түүнтэй хөрш бөгөөд дараалсан мөн өөрөөс нь бага буюу тэнцүү урттай тэгш өнцөгтийн тоог тэмдэглэнэ. Үүнтэй адилаар right[i]-ээр i-аар хайрцагны баруун талд орших түүнтэй хөрш бөгөөд дараалсан мөн өөрөөс нь бага буюу тэнцүү өндөртэй тэгш өнцөгтүүдийн тоог тэмдэглэв. Тэгвэл хариу max(left[i]+right[i]) (i=1..n). Бодолт O(N)

Тэгийн тоо

Факториалын сүүлийн 0-үүдийн тоог яаж олдог хүмүүс бол бодох л байсан бодлого. Бодлогын хариунд тооцогдож болох үржвэрийн тэгүүдийн тоо нь min(fac2, fac5) юм. Энд fac2, fac5 нь 2 болон 5ууд тус бүр хэдэн удаа үржвэрт байгааг илэрхийлнэ. Энэ нь бидэнд бодлогыхоо хариуг гаргаж авахад заавал бүх тоог үржүүлэхээс зайлсхийх боломжийг олгох юм. Одоо бодлогоо динамик програмчлал ашиглан хоёр өөр маршрут гаргаж авна. Нэг нь үржвэрт хамгийн бага 2 орсон, нөгөө нь мэдээж хамгийн бага 5 орсон. Тэгвэл хариу нь уг 2 маршрутын бага нь болно. Бодолтыг O(N^2)-аар шийднэ.

Mario on Box
Энэ бодлогыг одоохондоо бичихгүйгээр шийдлээ.