Хоосон эсвэл ханаас бүтсэн NхN хэмжээтэй хөлгийн хоосон нүдэнд бөмбөг байрлана. Мөн хөлгийгтойроод хана байгаа. Хөлгийг цагийн зүүний эсрэг, эсвэл цагийн зүүний дагуу эргүүлнэ. Эргүүлэхэд бөмбөг татах хүчний дагуу доошоо унана. Унахдаа хана байвал нэвтэлж чадахгүй ханан дээр тогтоно.
К удаа эргүүлсний дараа хөлөг ямар байдалтай байхыг харуул.
( 1<=N<=1000 ) , ( 1<=K<=500 000 )
Зөвхөн бөмбөгний хувьд бодолт хийе. Өөрөөр хэлбэл K үйлдлийн дараа бөмбөг хаана байрлах вэ? Гэдгийг тогтооё. Жишээ нь цагийн зүүны дагуу эргүүлнэ гэвэл бөмбөгний баруун талд орших хамгийн ойрхон ханыг олно гэсэн үг юм.
Хөлгийн элемэнт бүрд хамгийн ойр орших зүүн, баруун, дээд, доод ханын координатыг массивт хадгалаад бодвол хялбар бодогдно.
O(n^2+k);
Ziak buur nariin tootsoo hiij uzii daguu buh nudnees buh zug uruu chigluulehed ali nudend ochihiig hadgalj baina daraa n uuniigee ashiglah tul yag 4*N*N+M bolno.
ReplyDeleteHerev shuud ter nudneesee haishaa unahiig togtoohiig oroldvol hamgiin holdoo N nudnii daraa uneh uchir hamgiin ihdee N*M bolno.
Endees arai oorchlolt hiigeed omno n tootsoolson bairlalaa chiglel bolon nudee hadgalaad yavbal hamgiin ihdee 4*N*N+M bolno.
N<=1000 K<=500'000
gedgees
4*N*N+M<=N*M
tul ehnii arga n hoyordohoosoo guravdah arga n ehniiheesee hurdan bolno. Za ashiglaad baidaa
Goy yum bna. ene bodlogiig haana bodoh ve?
ReplyDelete