Баяр хүргэе!

Ази тивийн Оюутны програмчлалын 35 дахь удаагийн бүсийн олимпиад БНХАУ-ын Тянжинь хотод болж өнгөрлөө. Уг олимпиадаас манай блогийн гишүүд болох Н.Алмабек, Л.Мөнх-Очир, Э.Хонгор нар болон Багаболд багш ахлагчтай МУИС-ийн МКС-ийн баг хүрэл медаль хүртэв.

Өнгөрсөн жил Л.Мөнх-Очир, Б.Хасан, Э.Хонгор нарын бүрэлдэхүүнтэй МУИС-ийн МКС-ийн баг мөн хүрэл медаль хүртэж байсан ба энэ жил амжилтаа бататган хошой хүрэл медалийн эзэд болжээ.

Дээрх тэмцээн нь олон улсын их, дээд сургуулиудын хооронд болдог бөгөөд програмчлах ур чадвар, мэдлэг, дадлага, багаар ажиллах чадварыг шалгасан програмчлалын дэлхийн хамгийн нэр хүндтэй тэмцээн юм.

Олон улсын олимпиадаас хүрэл медаль хүртсэн дээрх баг нь энэ оны дөрөвдүгээр сард болсон Монголын оюутны прог­рамчлалын тэмцээнд оролцож шалгарч Азийн бүсийн олимпиадад орох эрх авсан.

Бяцхан фото сурвалжлага:

Багийн дасгалжуулагч Багаболд багш


Багийн гишүүн Хонгор


Багийн гишүүн Мөнх-Очир


Багийн гишүүн Алмабек


Дурсгалын зураг даруулсан нь

Модтой тоглоё 3 4

Бодлого
Мод гэдэг нь чиглэлгүй, дурын 2 оройн хооронд яг ганц л янзын зам олддог(нэг л маршрутаар очиж болдог) цикл агуулагүй (бүх оройн хувьд өөрөөсөө гараад өөр дээрээ ирдэг зам олдох ёсгүй) холбоост (дурын оройгоос дурын оройд очиж болдог) графыг мод гэнээ. Өөрөөр хэлбэл цикл агуулаагүй бүх холбоост графыг мод гэнээ гэж ойлгож болно. N оройтой граф байхад циклгүй холбоост граф болгохын тулд N-1 ирмэг татна. Бодлогоо бодохын тулд графын нэвтрэлтүүд болох түвшний нэвтрэлт, гүний нэвтрэлт аль альныг нь ашиглаж болно. Нэвтрэлт хийгээд бүх орой дээр хүрсэн эсэхийг шалгахад л хангалттай. Энэ гайгүй бодлого болохоор сурч аваарай гээд :D код тавив. Нээрээ өөр нэмэлт маягаар хэлэхэд энэ бодлогыг бас Disjiont Union өгөгдлийн бүтэц ашиглаж бодож болно.
Гүний нэвтрэлт хийсэн бодолт:

#include<cstdio>
#include<cstdlib>
#include<queue>
#include<stack>
#include<algorithm>
#include<cmath>
#include<string>
#include<cstring>
#include<set>
using namespace std;
#define Max 10000
vector<int>a[Max+1];
bool visited[Max+1];
int n,m;
bool istree(){
 for(int i=1;i<=n;i++)if(visited[i]==0)return false;
 return true;
}
int DFS(int i){
   vector<int>::iterator it;
   visited[i]=1;
   for(it=a[i].begin();it<a[i].end();it++){
       if(visited[*it]==0)DFS(*it);
   }
}
int main(){
   //freopen("yi.txt","r",stdin);
   //freopen("yo.txt","w",stdout);
   scanf("%d%d",&n,&m);
   if(m>=n){printf("NO\n");return 0;}
   while(m--){
      int u,v;
      scanf("%d%d",&u,&v);
      a[u].push_back(v);
      a[v].push_back(u);
   }
   DFS(1);
   if(istree())printf("YES\n");
   else printf("NO\n");
return 0;}

Түвшний нэвтрэлт хийсэн бодолт:

#include<cstdio>
#include<cstdlib>
#include<queue>
#include<stack>
#include<algorithm>
#include<cmath>
#include<string>
#include<cstring>
#include<set>
using namespace std;
#define Max 100001
queue<int>q;
vector< int >a[Max+1];
bool visited[Max+1];
int n,m;
bool istree(){
 for(int i=1;i<=n;i++)if(visited[i]==0)return false;
 return true;
}
int main(){
   memset(visited,sizeof(visited),0);
   //freopen("in11.txt","r",stdin);
   //freopen("out11.txt","w",stdout);
   scanf("%d%d",&n,&m);
   if(m>=n){printf("Mod bish\n");return 0;}
   while(m--){
        int u,v;
        scanf("%d %d",&u,&v);
        a[u].push_back(v);
        a[v].push_back(u);
   }
   q.push(1);
   while(q.size()){
        int l=q.front();
        visited[l]=1;
        q.pop();
        vector<int>::iterator it;
        for(it=a[l].begin();it<a[l].end();it++)
           if(visited[*it]==0){
              visited[*it]=1;
              q.push(*it);
           }
   }
   if(istree())printf("Mod\n");
   else printf("Mod bish\n");
return 0;}

Модтой тоглоё 4
Дурын оройгоос Түвшний нэвтрэлт хийж хамгийн сүүлд очих навчнаас дахин Түвшний нэвтрэлт хийж хамгийн сүүлд очих навч хүртлэх ирмэгүүдийн тоо хариу болно.

Азтай хулгана

Тавил:
Тойрог дээр N ширхэг хулгана сууж байв. Хулганууд 1..N гэсэн дугааруудтай. Муур 1-р хулганаас эхлэн тоолоод k-р хулганыг идэж, цаашид (k+1)-р хулганаас эхлэн тоолж мөн k дахь хулганыг гэх мэтээр идсээр хамгийн сүүлд нэг хулганыг үлдээжээ. Хамгийн сүүлд үлдсэн азтай хулганы дугаарыг ол.
Эх өгүүлбэр

Бодолт:
Энгийн динамик програмчлалын арга ашиглая.
Хамгийн эхний хулганыг сонгочихлоо гэж бодъё. Өөрөөр хэлбэл K дахь хулгана түрүүлээд идэгдчихлээ гэсэн үг. Одоо тойрог дээр N-1 ширхэг хулгана үлдсэн ба K+1 дахь хулганаас эхлэн тоолох боловч энэ нь яг л N-1 ширхэг хулганы хувьд бодлого маань хэвээрээ тавигдана гэсэн үг. Тэгэхлээр N-1 ширхэг хулганы хувьд ямар нэг X дахь хулгана нь азтай хулгана болж таарна гэвэл тэр нь анхны N хулганы хувьд K+1 дахь хулганаас эхлэн тоолсон байх тул K+X дахь хулгана N хулганы хувьд азтай хулгана болж таарна. Мөн хулганууд тойргоор байрласан учир K+X тоо N-ээс хэтэрсэн тохиолдолд 1-ээс эхлэн тоологдох болно. Үүнийг харгалзан үзвэл дараах рэкуррэнт томьёо гарах ба үүгээр бодлогыг бодож бүрэн болно.

F(N) = (F(N-1) + K - 1) % N + 1

Factorial

Тавил:
N! M-д хуваагдах эсэхийг тогтоо. (N, M-үүд нь 32 битийн натурал тоо)
Эх өгүүлбэр

Бодолт:
M-г анхны тоон үржигдэхүүнд задална. Задаргаанд орсон анхны тоо бүр N! -д ямар зэрэгтэйгээр орсныг тогтоогоод харьцуулна. Хэрвээ уг анхны тоо M-д илүү олон зэрэгтэйгээр орсон бол хуваагдах боломжгүй, харин N!-д илүү олон зэрэгтэйгээр орсон бол хуваагдана.

N!-д тухайн анхны тоо хэдэн зэрэгтэйгээр үржигдэн орсныг дараах аргаар мэдэж болно.
Анхны тоон зэрэг = [N/p] + [N/p²] + [N/p³] + ...
[n] - n тооны бүхэл хэсэг.

Хамгийн анхны тоо

Тавил:
Өгөгдсөн N (N <= 10³³) хүртэлх тоонуудаас давтагдаагүй хамгийн олон анхны тоонуудын үржвэрт задардаг тоог олно уу.
Эх өгүүлбэр

Бодолт:
Хариу: 2-оос эхлэн анхны тоонуудын үржвэр. Гэхдээ N-ээс халихгүйгээр. N-ээс халихгүй гэхээр анхны тоонуудын тоо тийм ч олон биш, анхны тооны таблицаас харж байгаад л үржүүлчихэж болно ;)
(Бодолтонд N-н хязгаар нэлээн өндөр тул том тооны үйлдэл ашиглах байх)

Stripes

Тавил:
Тэгш өнцөгт координатын системд зурагт үзүүлсэн шиг судлуудыг үүсгэсэн бол өгөгдсөн тэгш өнцөгт дотор хэдэн ширхэг хар нүд байгааг ол. X1, Y1, X2, Y2 буюу тэгш өнцөгтийн зүүн доод булан, баруун дээд булангийн координатууд өгөгдөнө.



Бодолт:
sudal(x, y) гэсэн функцаар (0,0) цэгээс (x,y) хүртэлх тэгш өнцөгтийн дотор хар нүдний тоог тэмдэглэвэл олох ёстой хариу маань:
sudal(x2, y2) + sudal(x1, y1) - sudal(x2, y1) - sudal(x1, y2)
болно.

Одоо харин sudal(x, y) функцийн утгыг олох нь маш хялбархан юм. Доорх зурагт дүрсэлсэний дагуу улаан хүрээтэй хэсгийн утгыг, бас цэнхэр хүрээтэй хэсгийнхийг тус тусад нь олоод л болчихно.

Дундаж

Тавил:
N (N<=10000) урттай натурал тоон дараалал өгөгдөв. Аль нэг хоёр (тэр хоёрынхоо нэг нь өөрөө байж болно) элэмэнтийнх нь арифметик дундаж болдог дарааллын элэмэнтийг дундаж гэе. Тэгвэл уг дараалалд хичнээн дундаж байгааг тоол.
Эх өгүүлбэр

Бодолт:
Эхлээд уг дарааллаа эрэмбэлье. (Quicksort ~ O(N*LogN))
Дараа нь уг эрэмбэлэгдсэн дарааллын аль нэг элэмэнтийг (K дугаарх) дундаж мөн эсэхийг тогтооё.
Хэрвээ аль нэг хөрш элэмэнт нь тухайн элэмэнттэй тэнцүү бол тэр элэмэнт дундаж болж чадна.
(A[K+1] == A[K] OR A[K] == A[K-1])

Аль ч хөрш нь өөртэй нь тэнцүү биш бол өөрөөс нь их болон бага нэг нэг элэмэнтийн дундаж л байх боломжтой. A[K] = (A[K-j] + A[k+i]) / 2
Мөн A[K+i]-A[K] болон A[K]-A[K-j] ялгаварууд хоорондоо тэнцүү үед л уг A[K] элэмэнт маань дундаж болно гэж үзэж болох ба i, j өсөхөд тус ялгаварууд мөн дагаж өсөх тул хэрвээ аль нэг ялгавар нь нөгөөгөөсөө бага байвал тухайн i юм уу j коэффицэнтийн утгыг нэмээд яваад байх боломжтой.
if (A[K+i]-A[K] < A[K]-A[K-j]) i++; else j++;
Гэхмэтчилэнгээр дарааллын аль нэг зах хүртэл юм уу, K дахь элэмэнт дундаж болох нь батлагдах хүртэл энэ давталтыг явуулна.

Уг бодолт нь хамгийн муу тохиолдолд O(N*N) юм. Гэхдээ дундаж тохиолдолд үүнээс хамаагүй хурдан ажиллана.

Квадрат

Тавил:
Өгөгдсөн N (1 <= N <=100000) тоог хамгийн цөөндөө хичнээн тооны квадратуудын нийлбэрт тавьж болох вэ?
[Эх өгүүлбэр]

Бодолт:
Ямар ч натурал тоог 4 бүхэл тооны квадратуудын нийлбэр хэлбэрт тавигддаг гэсэн теоремын дүгнэлтийг шууд авч ашиглавал бидний гаргах ёстой хариулт маань 1, 2, 3, 4 гэсэн 4 утгын нэг байх юм.

N <= 100000 гэдгийг анхаарвал хариулт нь 1 байх тоонуудыг ойролцоогоор 320 удаагийн үйлдлээр (1х1, 2х2, 3х3, ... , 320х320), хариулт нь 2 байх тоонуудыг 320х320 удаагийн үйлдлээр, хариулт нь 3 байх тоонуудыг 320х320х320 (1 секундэд амжиж байна лээ :D) удаагийн үйлдлээр бүгдийг нь бүртгээд массивт хадгалчихаж болно. Харин массивын утга нь 0 байгаа тоонууд нь хамгийн цөөндөө 4 квадрат тооны нийлбэрт тавигдах тоонууд болж таарах юм.