SRM 476

Энэ удаад манайх их олуулаа оржээ, магадгүй миний орж эхэлснээс хойш хамгийн олон монгол зэрэг орж байна.
Division 1: Khongor, Chamka
Division 2: naranbayar_mon, XaCaHaa, Khuyagbaatar, lmo0731, nursoltan_h, gmunkhbaatarmn, almabek

Easy бодлогоо өрөөнөөсөө хамгийн хурдан бодлоо (4 минут). Итгэл муутай байсан болохоор бараг 1 минут хянасан байх. Medium бодлогын өгүүлбэрээ буруу уншчихсан байналээ. 36 character гэдгийг 36 number гэж ойлгоод бодлогыг бодох боломжгүй болгочихсон юм байналэ :D. Challenge Phase дээр алдах л юм бол хэдэн зуун байр ухрах том аюултай байсан учир энэ удаад бараг алгаслаа. Easy минь даваад чансаа 81-р өсөөд 1821 буюу Maximum рейтингдээ хүрчихлээ. Ер нь easy маш хурдан хийгээд, medium яаж ийгээд бодоод байвал мөрөөдлийн өнгө рүүгээ дөхөх шинжтэй.

Div 1 Easy/Div 2 Medium: Greedy алгоритм яг зөв гэдэгт итгэлгүй байна. K амьтан авч чадах эсэхийг шийдье. Тэгвэл амьтан бүрийн өдөрт идэх хэмжээг нь олж болно. total(i)=hunger(i)+greed(i)*(k-1). Ингээд total-аараа хамгийн бага К ширхэг амьтны нийлбэр таны мөнгөнөөс хэтрэхгүй бол авч болно гэсэн үг. Хязгаарлалт жижиг байсан тул К дээр шугаман хайлт хийж болно, хэрэв том байсан бол 2тын хайлт хийж болно.

class Badgers{
public:
int feedMost(vector hunger, vector greed, int totalFood)
{
vector g=greed;
int n=g.size();
for (int i=n;i>=1;i--)
{
for (int j=0;j<n;j++)
g[j]=greed[j]*(i-1)+hunger[j];
sort(g.begin(),g.end());
int s=0;
for (int k=0;k<i;k++)
s+=g[k];
if (s<=totalFood) return i; } return 0; } };
Div 2 Easy: Ямар нэгэн нүдийг зүүн дээд булан руу зөөхөд шаардагдах хамгийн цөөн үйлдэл нь зүүн дээшээ, зүүн доошоо, баруун дээшээ, баруун доошоо дөрвийн минимум байх болно. Манай Div 2 хүмүүс жаахан удсан юм шиг байна.

class MatrixShiftings{
public:
int minimumShifts(vector matrix, int value){
int ret=1<<30; int n=matrix.size(),m=matrix[0].size(); for (int i=0;i<matrix.size();i++) for (int j=0;j<matrix[0].size();j++) if (matrix[i][j]-'0'==value){ ret<?=i+j; ret<?=n-i+j; ret<?=i+m-j; ret<?=n-i+m-j; } return ret==1<<30?-1:ret; } };

Div 2 Hard: Энгийн O(N^3) DP. Гэвч хугацаанд амжихын тулд жаахан юм хийх хэрэгтэй (Precomputation). Удахгүй source оруулна.