Баяр хүргэе!

Ази тивийн Оюутны програмчлалын 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 квадрат тооны нийлбэрт тавигдах тоонууд болж таарах юм.

Topcoder Diary - SRM 480 (Division 2)

Яагаад ч юм өмнө нь тэмдэглэж авсан дээр маань өглөө 7-цагаас болно гэчихсэн байхаар нь хар эрт 6 цагт сэрээд бүртгүүлчихээд харсан чинь 9 цагаас эхэлнэ гэж байдаг юм даа. И-мэйл-ээр ирсэн хуваарь дээрээ бол яалт ч үгүй 9 цагаас л байна лээ л дээ :P Бүүр сарын өмнөөс календарь дээрээс нь тэмдэглэж авсан болохоор дөхүүлээд цагаа өөрчилдөг ч байж магадгүй. Эсвэл би будилж бүтэлгүйтсэн бололтой ^^

Энэ удаа манайхаас доорх хүмүүс оролцжээ.
Div1-д: Khongor, Chamka
Div2-д: Khuyagbaatar, lmo0731, gmunkhbaatarmn, nursoltan_h, Jaamaa^{2nd contest!}, almabek, Jaamaa

Coding phase

Easy
Мөн л өмнөх шигээ хурдан бодчихлоо. Шууд тэстээ гүйлгэж хараад л ямархуу үйлдэл хийхээ баримжаалаад л өгүүлбэрээ нэг уншаад л бодолтондоо орсон. Ойрд practice хийгээгүйн гай гарч дэмий юман дээр цаг алдсаныг эс тооцвол дажгүй шүү. 250-аас 247 оноо. (Ойрд яасан романтик оноо аваад байна аа ^^)

Medium
Үнэхээрийн хайнга бодсон доо. Өгүүлбэр нь амархан санагдаад, за энийг л бодчихвол энэ тэмцээний норм хангагдчих юм чинь гээд яарсан ч үгүй :P 500-аас 354 оноо.

Hard
Анх тэмцээн эхлэхэд 900 онооны бодлого болохоор нь (ихэнхдээ 1000 байдаг) энэ ч өмнөхүүдээ бодвол амархан "hard" байгаа байхдаа гэж бодсон. Уг нь өгүүлбэрийг нь ойлгочихвол маний эзэмшсэн зэвсгийн эрдмээр бол нухчихаар л эд байна гэж бодоод өөрийгөө зоригжуулаад нэлээн нухлаа. Өрөөн дотроо баахан дэмий эргэцүүлж ганцаараа ярин байж жаал жуул нууцад нь нэвтэрлээ :) Greedy + Brute Force (элэмэнтүүдийнхээ алийг нь төгсгөлд нь тавих вэ гэдгээ бүгдийг нь шалгаж үзнэ)
Яг бодчихоод тэстэлтэл нэг л биш ээ, сайн харлаа. Дахиад сайн харлаа. Тэнэг чинь бодлогын өгүүлбэрийн 3 дахь нөхцлийг огт тооцоогүй байна шд (үнэхээр тэнэг байгаа биз?) Тооцоондоо багтаахад нэг их төвөг орсонгүй. Хугацаа дуусахаас 4 минутын өмнө submit хийлээ. 900-аас 407 оноо.

Challenge phase

Огт сорилт (challenge) хийсэнгүй.

System test phase

Waiting ^^
500-дээрээ алдчихсан юм шиг байна (Lmo`s analiz :D)

IOI Day 2 Бодлого 2

Бодлого 2: Traffic Congestion.

Канад улсын иргэд хокэй үзэх үнэхээр дуртай. Тэд хокэйг шууд талбай дээр нь үзэхийн тулд улсын өнцөг булан бүрээс ирдэг. Харин тэмцээн дууссны дараа бүгд машиндаа суугаад харих хэрэгтэй ба ганц бэршээл нь маш их машин ирсэн учраас зам дээрх машины тоо хэтэрхий ихсэнэ. Нэгэн баян үйлдвэрийн эзэн хоккэйн баг худалдаж авсан ба түүндээ зориулж шинэ талбай барих болов. Таны даалгавар бол энэ баякаад тусалж хоккэйн талбай барих хамгийн тохиромжтой хотыг олно уу. Тохиромжтой гэдэг нь тэмцээн дууссны дараа зам дээр яваа машины тоог хамгийн бага байлгахаар хот юм.

Канад улс нь хоорондоо 2 чиглэлт замаар холбогдсон хотуудаас тогтоно. Аль нэг 2 хотын хооронд яг ганц замын маршруттай. Барих шинэ талбай нь энэ хотуудын аль нэг хотод баригдах ёстой. Мэдээж тэмцээн дууссны дараа тухайн хотын иргэдээс бусад нь бүгд машиндаа суугаад харьж таарна. Тухайн зам дээрх машины тоо нь тухайн замыг ашиглаж өөрийн хотдоо очиж байвал эдгээр хотуудын хоккэй-д дуртай хүмүүсийн нийлбэр байна. Таны програм талбай баригдсан хотын хамгийн их машин явах замын машины тоог хамгийн бага байлгах ёстой. Олон хариу байхыг үгүйсгэхгүй ба энэ тохиолдолд аль нэгийг гаргаж болноо. Та LocateCentre(N,P,S,D) процедурыг зохиох ба энд N нь бүх хотуудын тоог илтгэх эерэг бүхэл тоо, хотуудыг 0-ээс N-1 хүртэл дугаарлана, P нь N ширхэг тоог агуулсан массив байх ба 0<=i<=N-1 байх P[i] болгонд i-р хотын хоккэй үзэх фанатуудын тоо. Бүх хотуудад байгаа фанатуудын тоо нь хамгийн ихдээ 2 000 000 000 байх болно. S болон D нь мөн массив байх ба тус бүр N-1 элементтэй. S[i] D[i] нь энэ 2 хотын хооронд замтайг илтгэнэнэ. Таны зохиосон процедур зөвхөн талбайг барих хотын дугаарыг буцаах ёстой.

Жишээ: Доорх жишээнд эхний зурганд 0 1 2 гэсэн хотууд тус тус 10 хокэй сонирхохгчтой, 3 4 гэсэн хотууд тус бүр 20 сонирхогчтой. 2 дахь зурганд хокэйн талбайг 2 гэсэн дугаартай хотод барьвал хамгийн их машинтай зам нь 40 болохыг харуулж байна.3 дахь зурганд талбайг 3 гэсэн хотод барьвал хамгийн их машинтай зам нь 30 болохыг харуулсан байна. Эндээс 3 дугаартай хот нь 2 дугаартай хотоос илүү тохирох болохыг харуулж байна.





Эхний 25 онооны тест нь:

Хотуудыг зүүнээс баруун хүртэл шулуун шугаман байрлуулсан гэж үз. Ямар ч мөчөр байхгүй. Эндэ хамгийн ихдээ 1000 хот байна.

2 дахь 25 онооны тестүүд:

Хотууд адилхан шугаман байрлуулсан ба хамгийн ихдээ 1 000 000 хотууд байгаа гэж үд

3 дахь 25 онооны тестүүд:

Шугаман байх албагүй ба хамгийн ихдээ 1000 хот байгаа гэж үз

4 дахь 25 онооны тестүүд:

Мөн шугаман байрлах албагүй ба хамгийн ихдээ 1 000 000 хот байгаа гэж үз.

IOI Day 2 Бодлого 1

Бодлого 1: Memory
Жак Мемори гэдэг тоглоом тоглох дуртай ба энэ тоглоом нь 50 ширхэг хөзөрөөр тоглодог ба хөзөр бүр дээр латин цагаан толгойн A-Y үсэг наасан байгаа. Тэгэхээр нэг үсэг яг 2 ширхэг байна. Тоглохдоо хөзөрөө хольж байгаад үсэг наасан талыг доош нь харуулан тавиад хоёр хоёр хөзөр сонгож тухайн үсэгнүүдийг хараад буцааж доош нь харуулж тавина. Хэрэв сонгосон 2 хөзөр адилхан байвал Жак ээжээсээ чихэр авах юм. Хэрэв дахин нөгөө 2 хөзөрөө гаргаад ирвэл дахиж чихэр авахгүй. Энэ тоглоом нь Жак 25 ширхэг чихэрээ авсны дараа дуусах юм. Таны даалгавар бол Жакыг орлох Play процедурыг зохиох явдал юм. Таны програм тест зохиогчидын хэрэгжүүлцэн байгаа faceup(C) функцыг дуудах ёстой ба энэ функц нь C дугаар хөзөр дээрх үсгийг буцаана. С нь мэдээж 1-ээс 50 хооронд байх ба таны сөхөж үзэх хүсэлтэй тоо юм. Хөзөр сөхө явцад 2 дахь сөхсөн хөзөр болгоны дараа тухайн сонгосон 2 хөзөрийг доош нь харуулан дахин тавина. Таны зохиосон процедур зөвхөн Жакыг 25 чихрээ авсан тохиолдолд л дууса юм.
Жишээ:

Дуудалт	Буцаасан утга	Тайлбар
faceup(1)	'B'	1-р хөзөрт B үсэг.
faceup(7)	'X'	7-р хөзөрт X үсэг. Сонгосон 2 хөзөр маань адилхан биш
Нээсэн 1 болон 7-р хөзөрүүд буцаан доош харуулан тавигдана
faceup(7)	'X'	7-р хөзөрт X үсэг.
faceup(15)	'O'	15-р хөзөрт O үсэг. Сонгосон 2 хөзөр маань адилхан биш
Нээсэн 7 болон 15-р хөзөрүүд буцаан доош харуулан тавигдана
faceup(50)	'X'	50-р хөзөрт X үсэг.
faceup(7)	'X'	7-р хөзөрт X үсэг. Сонгосон 2 хөзөр ижил учир Жак эхнийхаа чихэрийг авав.
Нээсэн 50 болон 7-р хөзөрүүд буцаан доош харуулан тавигдана
faceup(7)	'X'	7-р хөзөрт X үсэг.
faceup(50)	'X'	50-р хөзөрт X үсэг. Сонгосон 2 хөзөр ижил гэвч чихэр авахгүй.
Нээсэн 7 болон 50-р хөзөрүүд буцаан доош харуулан тавигдана
faceup(2)	'B'	2-р хөзөрт B үсэг.
...
(энэ мэтчилэн функцууд дуудагдсаар)
...
faceup(1)	'B'	1-р хөзөрт B үсэг.
faceup(2)	'B'	2-р хөзөрт B үсэг. Жак 25 дахь чихэрээ авав.

Эхний 50 оноо: хугацаандаа амжиж ажиллаад байвал авч чадна.
2 дахь 50 оноо: faceup(C) функц 100-аас илүү дуудагдах ёсгүй.

IOI2010 Day 1 Бодлого 4

Бодлого 4: Language
Таньд Википедиа-гаас ямар нэгэн билэг өгөгдсөн бол ямар хэл болохыг нь таана уу. Оролдсон оролдлогоо ашиглан зөв хариуг ол. Хэл болгон 0<=L<=55 тоогоор төлөөлөгдөнө. Бүх бичлэгүүд яг 100 тэмдэгтээс тогтох ба, үүнийг бүхэл тоон төрлийн 100 элементтэй 1-ээс 65535 хүртлэх утга авах E массив төлөөлнө. Та excerpt(E) процедурыг зохиох ёстой. Таны процедур language(L)-г дуудах ёстой ба хэрэв language(L) = L бол зөв гэж үзнэ. Таны excerpt(E) нийт 10000 удаа дуудах ба хэдэн бичлэгийн хэлний кодыг зөв олсноор нь таны програмын хэр оновчтойг тодорхойлох болно. Жишээ энтэрийг эндээс үзнүү :D.

IOI2010 Day 1 Бодлого 3

Бодлого 3: Quality of living.
Албертаа дахь хотуудыг дөрвөлжин шугамтай цаасан дээр хойноос урд хүртлэхийг 0-ээс R-1 хүртэл дугаарлаж, баруунаас зүүн хүртлэхийг 0ээс C-1 хүртэл дугаарлан дүрслэж болох юм. Хот бүрийн чансааг тогтоосон байдаг ба тухайн нүд бүрт тухайн хотын чансааг илтгэх 1-ээс R*C тоог бичсэн байгаа. Чансаа нь 1 байвал хамгийн өндөр чансаа, R*C хамгийн муу. Хот төлөвлөлтийн газар дундаж чансаа хамгийн өндөр HxW хэмжээтэй тэгш өнцөгт газрыг сонгож авахыг хүсч байгаа. H W нь R C тоонуудаас тус бүр хэтрэхгүй сондгой тоонууд байх болно. Ямар нэгэн H W хэмжээтэй тэгш өнцөгт газрын хувьд дундаж чансааг дараах байдлаар тодорхойлно. Дундаж чансаа нь уг газрын аль нэг нүдэн дэх чансаа байх бөгөөд уг чансаанаас бага чансаатай нүдний тоо нь уг чансаанаас их чансаатай нүдний тоотой тэнцүү. Өөрөөр хэлбэл H W ширхэг тоог цувуулж бичээд эрэмбэлэхэд голын тоо нь гэсэн үг. Таны даалгавар бол бүх H W хэмжээтэй тэгш өнцөгт газрууд дотроос хамгийн сайн (утгаараа бага) дундаж чансааг олох rectangle(R,C,H,W,Q) процедурыг зохиох юм. Энд Q нь Q[a][b]-д орших хотын чансааг агуулсан массив юм.

R=5, C=5, H=3, W=3, 
Q=  5 11 12 16 25
17 18  2  7 10
4 23 20  3  1

24 21 19 14  9
6 22  8 13 15

rectangle(R,C,H,W,Q)=9
Дээрх жишээнд m=9 мөн бодлогын нөхцөлыг хангах хотуудыг дотруулсан байна.
Жишээ2:

R=2, C=6, H=1, W=5, 
Q=  6  1  2 11  7  5
9  3  4 10 12  8

rectangle(R,C,H,W,Q)=5

IOI2010 Day 1 Бодлого 2

Боодлого 2: Hotter Colder
Жак Жилл 2 Хоттер Колдер гэх тоглоом тоглдог. Жилл 1-N хүртлэх тооноос нэгийг санаж, Жак таахыг хэд хэдэн удаа оролдоно. Мэдээж Жак-н хэлж буй тоонууд нь 1-N завсарт байх ба оролдлого бүрт Жак hotter, colder, same гэсэн хариултыг өгнө. Жакын эхний оролдлогонд Жилл same гэсэн хариултыг өгнө. Үлдсэн оролдлогуудад Жилл дараах нөхцөлийг харж хариултаа хэлнэ.
• Хэрэв Жиллын санасан тоонд Жакын одоогийн хэлсэн тоо нь Жакын өмнөх оролдлогонд хэлсэн тооноос илүү ойрхон байвал hotter.
• Хэрэв Жиллын санасан тоонд Жакын одоогийн хэлсэн тоо нь Жакын өмнөх оролдлогонд хэлсэн тооноос илүү хол байвал colder.
• Хэрэв хол ч биш ойрхон ч биш бол same.
Таны даалгавар бол Жакын үүргийг гүйцэтгэх HC(N) програм зохио. Guess(G) нь 1<=G<=N ба 1 утга буцаавал hotter -1 утга буцаавал colder, 0 утга буцаавал same . HC(N) функц нь Жиллын санасан тоог буцаах ёстой.
Жишээ.
Доорх жишээнд N=5 мөн Жилл 2 гэсэн тоог санасан болно.

Дуудалт	Буцаасан утг	Тайлбар
Guess(5)	0	Same анхны дуудалтаар буцаана гэж байгаа
Guess(3)	1	Hotter
Guess(4)	-1	Colder
Guess(1)	1	Hotter
Guess(3)	0	Same

IOI2010 Day 1 Бодлого 1

Бодлого 1: Cluedo
Эрхэм Хар( hehe ) хүн амьний хэрэгт холбогдов. Мөрдөгч Жилл алуурчид, хэргийн газар, хэрэг үйлдсэн зэвсгүүдийг илэрүүлсэн байв. Энд 1ээс 6 хүртэл дугаарласан сэжигтэй алуурчид 1ээс 10 хүртэлх сэжигтэй хэргийн газар, мөн 1ээс 6 хүртэл дугаарласан сэжигтэй зэвсэгүүд байв. Жилл эдгээр илэрүүлсэн зүйлүүдээ ашиглаад байж болох хослолуудыг зохиогоод үүнийгээ Theory гэж нэрлэв. Мөн Жилл өөрийн туслах Жак-д хэлж үүнийг үнэн эсэхийг шалгах даалгавар өгөв. Хэрэв Жак Жиллийн хэлсэн Theory-г үнэн гэдэгийг баталж чадвал Жиллийн ажил дуусна. Эсрэг тохиолдолд Жилл дахин өөр боломжтой Theory-г Жак-д санал болгоно.
Таны даалгавар бол Жилл-ийн үүргийг сайн биелүүлэх процедур зохиох явдал юм. Таны функцийг маш олон удаа дуудах ба дуудагдах бүрд Theory(M,L,W) байна. Энд M-алуурчины дугаар, L-хэрэг болсон газарын дугаар, W-зэвсэгийн дугаарыг агуулсан theory байна. Таны функц 0 утга буцаавал Жак баталж чадсан эсрэг тохиолдолд буюу 1 2 3 гэсэн аль нэг утга буцаавал няцаагдах юм. Эндэ 1-алуурчин буруу, 2-хэргийн газар буруу, 3-зэвсэг буруу гэдэгийг илтгэнэнэ.

Дуудалт	Буцаасан утга	тайлбар
Theory(1, 1, 1)	1, or 2, or 3	3-уулаа буруу
Theory(3, 3, 3)	1, or 3	Зөвхөн хэргийн газарыг зөв оруулжээ
Theory(5, 3, 4)	1	Зөвхөн алуурчинг буруу оруулжээ
Theory(2, 3, 4)	0	Энэ удаад баталж чаджээ.

Topcoder Diary - SRM 479 (Division 2)

Энэ удаа манайхаас доорх хүмүүс оролцжээ.
Div1-д: Chamka, XaCaHaa, lmo0731
Div2-д: Khuyagbaatar, gmunkhbaatarmn, nursoltan_h, almabek, Jaamaa^new!

Coding phase

Easy
Өмнөх SRM дээр туршиж үзсэн аргаар эхлээд тэстээ гүйлгэж хараад дараа нь бодлогынхоо өгүүлбэрийг харлаа. Овоо хурдан ойлгочихлоо. Амархан ч бодлого юм. 250-аас 247.92 оноо. (Хувийн рекорд ^^)

Medium
За ёстой бүү мэд. Эхлээд greedy маягийн юм бичиж үзсэн болоогүй. Дараа нь нэг юмыг нь л sort хийх хэрэгтэй юм байна гэж бодсон. Тэрийгээ хайсаар байгаад цаг дуусгалаа даа :(

Hard
Нээж ч харж амжсангүй :)

Challenge phase

500 онооны бодлогыг нэг нөхөр хэтэрхий хялбарчлаад бодчихсон байсныг нь нээж үзээд ямар тэст зохиох вэ гэж бойтоглох зуур хэн нэгэн нь өрсчихвөө. "Challenge Succeeded". Өөр онц юм болсонгүй. Манай өрөөнд 1000-онооны бодлогоо бодсон хүн ч гарсангүй. 250 дээр алдаж магадгүй юм ч байсангүй. 500-гийн тухайд бол систем тэст дээр нэлээн их хүн унах байх даа :D

System test phase

Waiting ^^

Topcoder Diary - SRM 478 (Division 2)

За ёстой бөөн адал явдал гэхээс өөр юу гэхэв. Тэмцээн болтол түр гараад ирьюүү гээд гарчихаад ирсэн чинь тэмцээн эхэлснээс бараг 10 минутын дараа л орж ирж таардаг юм даа. Ямар азаар бодолтын цагийг бодлогоо нээж харсанаас хойш тооцдог юм бэ :)
Энэ удаа манайхаас доорх хүмүүс оролцжээ.

Div1-д: Khongor
Div2-д: XaCaHaa, lmo0731, ChNbLd, gmunkhbaatarmn, nursoltan_h, almabek

Coding phase

Easy
Урьд нь бодлогынхоо өгүүлбэрийг уншаад дараа нь тэстээ уншаад, тэгээд бодлогын өгүүлбэрээ уншаад, дахин тэстээ уншаад гэх мэтчилэн 4-5 удаа эргэцүүлсэний эцэст бодлогынхоо өгүүлбэрийг ойлгодог байсан бол энэ удаад шууд л эхэлж тэстээ хараад л бодлогынхоо баримжааг аваад л өгүүлбэрийг нь уншсаны дараа дахин нэг удаа тэстээ хальт харчихаад л бодолтоо бичиж эхэллээ. Овоо хурдан амжуулчихлаа. 233 оноо :)

Medium
Уншаад л. "Ээ за энэ удаад ч 500-гийн бодлогыг барна гэдэг худлаа болчихлоо" гэсэн шүү юм бодогдоод угаасаа хоцорч ирсэн энэ тэрийг тооцвол энэ тэмцээн угаасаа худлаа болчихлоо гээд л цухалдаж эхэндээ баахан суусаныг эс тооцвол дажгүй шүү :P
Эхний үйлдлийг A, дараагийн үйлдлийг B гэвэл. A*B = B*A, A*A*A=B*B болж таарахыг анзаарчихвал бодлого хялбарчлагдана. Өгөгдсөн тоон дээрээ A үйлдлийг л давтан хийсээр байна. Дараа нь 3 удаа A үйлдэл хийгдсэн болгоныг 2 B үйлдэл хийсэн гээд тоолчиход хангалттай. 262 оноо.

Hard
Хэсэглэл л байгуулаад BruteForce хийж болох юм шиг байсан. Гэхдээ хугацаандаа амжихгүй юм шиг санагдсан. Ямартаа ч би лав үлдсэн хугацаандаа хэсэглэл байгуулах гээд амжсангүй :P

Challenge phase

1000 онооны бодлогоо барахаасаа өнгөрлөө гээд чаат-лог хараад сууж байсан чинь 2 шинэков бололтой нөхөр 1000 онооны бодлогоо бараг л нээж харангуутаа эргээд submit хийж байх юм. Шууд л дотроо хүйтнээр инээгээд алгаа үрж challenge phase-г хүлээгээд эхлэнгүүт нь нөгөө хоёрын 1000-онооны бодлогыг дараалан унагаад сул +100 авав. Уг нь ингээд гоё эхэлсэн юм аа. Тэгсэн чинь нэг нөхрийн 250 онооны бодлого нь хугацааны хязгаарлалтаа давчих юм шиг санагдахаар нь 3 удаа амжилтгүй challenge хийгээд -75 оноо. Хаха. Уг нь сул авсан 100 оноогоо хадгалж байсан бол 560 оноотойгоор өрөөндөө нэгт нийт дүнгээр эхний 40-д багтах л байлаа. Гэхдээ энийг бичиж байх хооронд системийн тэст дуусчихаж өрөөндөө 3-рт div2-тоо 55-р байр. Юундаа ч гонсойхов :)

Topcoder Diary - SRM 477 (Division 2)

Энэ удаад манайхаас бүүр олон хүн орсон ба шинээр хэд хэдэн хүн нэмэгдсэн байна. Topcoder-т тавтай морил :)

Div1-д: Khongor
Div2-д: naranbayar_mon, XaCaHaa, Khuyagbaatar, lmo0731, nursoltan_h, gmunkhbaatarmn, almabek, janchiv, gantushig, ChNbLd

Coding phase

Easy
Өгүүлбэрийг нь ойлгох гэж их удсан. 191.58 оноо. Easy-г 200.0-д багтаачих бодол уг нь байдаг юм. Энэ удаад бодолтойгоо л хоцорхоос :P

Medium
Сондгой, тэгш мөрүүдийн хувьд тус тусад нь бичих байсныг нэг удаа тэстэлж үзээд мэдсэн, тэгээд засаад бичсэн боловч массивийн индекс тооцохдоо бяцхан алдаа гаргаад хайж олох гэж цаг алдсан. 347.95 оноо. Миний хувьд Medium-аа ямар ч гэсэн бодчихвол болоо гэсэн баримжааг ойрын үед барьж байгаа тул сэтгэл хангалуун байгаа :) Гэхдээ мэдиум нэлээн амархан санагдсан тул өөр их олон хүмүүс бас бодчихсон байх.

Hard
DP л юм шиг санагдсан.
F(N, K) = (N-K) * F(N-1, K-1) + (K-1) * F(N-2, K-2);
гэсэн DP арай гэж олсон боловч K = {0, 1, 2} үе болон эхний тусгай нөхцлүүдээ буруу бичсэн үү яасан жишээ тэстүүдийг даваагүй. Магадгүй DP маань буруу байсан ч байж болох юм.

Challenge phase

Манай өрөөнд easy бодлогон дээр бөөн алалцаан болох шив дээ. Хэд хэдэн бодлого уналаа. Гэхдээ би энэ удаад мөн л ангайж харсаар байгаад нэг ч challenge хийсэнгүй.

System testing phase

За манай хэд ч ихэнх нь тэстүүдээ давжээ. Ер нь нийтээрээ овоо дориун оролцчихлоо. Улсын рэйтинг ч дагаад өсөх байх даа :)

Topcoder Diary - SRM 476 (Division 2)

За энэ удаад манайхан их олон хүн хүний бүрэлдэхүүнтэйгээр оролцсон байна.

Div1-д: Khongor, Chamka
Div2-д: XaCaHaa, Khuyagbaatar, lmo0731, nursoltan_h, gmunkhbaatarmn, almabek, naranbayar_mon

Сониноос Topcoder-ын улс орнуудаар нь жагсаасан үзүүлэлтэд манай улс рейтингтэй болсон байна лээ. http://www.topcoder.com/stat?c=country_avg_rating Одоогоор 52-т жагсаж байгаа юм байна.

Систем тест хүлээх зуураа diary бичээд сурчихвал зүгээр ч юм уу гэж бодогдоод туршаад үзмээр санагдав. Болох нь уу үгүй юу үзээдхэе :D

Coding phase

Easy - MatrixShiftings
Матриксийг шилжүүлэх 4 үйлдэл зааж өгсөн, тэдгээрийг ашиглан хүснэгтэн дэхь заагдсан тоог зүүн дээд буланд авчрах хамгийн цөөн үйлдлийн тоог олох.
Бодолт: Матриксийг шилжүүлэх бүрд нэг нэг нүдээр ахих учраас зүүн болон дээд хажуугаас тус бүр хэдэн нүд зайтай байгааг тоолоод л болно. Гэхдээ мөн баруун болон доошоогоо шилжиж очих боломжтой учраас тус тус хувилбаруудаас хамгийн багуудыг нь олоод нэмнэ.

Medium - Badgers
Өгүүлбэрийг нь ойлгох гэж жаахан мунгинасаныг эс тооцвол гайгүй бодчихсон.

Hard - SubAnagrams
Пээ анх удаа л hard түвшний бодлого бодоод submit хийж явуулж үзлээ шд. Нүдний нулимс цийлэгнээд явчихаж байх чинь ээ. Уйлж л болдоггүй юм шүү.
Гэхдээ алдаатай байх гэж айгаад байна. DP байж магадгүй ч гэсэн Greedy бодолт л чадмаар санагдаад байхаар нь хийгээд явуулчихсан. Challenge, System test дуустал хүлээж л байя.

Challenge phase

Манай өрөөнд одоогоор нэг амжилтгүй, нэг амжилттай challenge хийгдээд байна. Ер нь систем тэстээ л хүлээе дөө. Challenge-н үеэр онц юм болохгүй бололтой.
Update: 1000-онооны бодлогоо бодсон манай өрөөний 2 хүний нэг нь challenge-д эцсийн мөчөд сугарваа хөөрхий :P Би ч далимдуулаад байр ахиад авлаа. System test-ээ гэж. Ямархуу юм болох болдоо?

System testing phase

За ёстой гоё юм болсон шүү. Medium, Hard 2-н бодолт маань system test-н дээр уначихлаа :)

TCO 10 ( Mongolia )

Энд TCO 10-т Монгол улсаас шалгарагчдыг бичнэ.

Qualficiation Round:

Khongor (Round 1)
XaCaHaa (Round 2)
lmo0731 (Round 3)


Elimination Round :

Khongor (Round 1)

TCO 2010 Qualification Round 1 (Diary)

TCO гэдэг нь TopCoder Open гэсэн үг болно :).

Qualification Round нь 3 үетэй ба аль нэгэнд нь эхний 600 байранд орвол дараагийн Elimination Round-д оролцох эрхтэй болно.

Энэ тэмцээнд нийт 954 хүн оролцохоор бүртгүүлсэн ба Монгол улсаас Khongor, gmunkhbaatarmn, Nursoltan_MGL гишүүд оролцсон.

За ингээд тэмцээнээ эхлүүлье :).

Coding Phase

250 :
G болон B үсгээс тогтох тэмдэгт мөрийг зэрэгцээ үсгийг солих замаар хамгийн цөөн үйлдлээр GG....GBB.....B эсвэл BB...BGG...G хэлбэртэй болго.
Дээрх 2 хэлбэрийг тусд нь хялбархан бодоод аль багыг гаргахад хангалттай.
5 минут 47 секунд

500:
Хязгааргүй хөлөг дээр роботыг дээш, доош, баруун, зүүн тийш хөдөлгөх үйлдлийн дараалал өгөгджээ. Уг дарааллыг маш олон удаа давтан биелүүлэхэд робот нийт хэдэн ялгаатай нүдэн дээр зорчих вэ?

Гол асуудал нь маш олон удаа давтан биелүүлэх учраас шууд үйлдлийг биелүүлэх боломжгүй. Өгөгдсөн үйлдлийн дарааллийг тодорхой удаа биелүүлэхэд шинээр зорчих нүдний тоо ижилхэн болох учраас бодож болно.
53 минут 27 секунд

1000:
500 онооны бодлогыг бодож байх зуур хальт гүйлгэж харсан учир бараг оролдоогүй. Сүүлийн хэдэн минутанд дахиад хартал 2тийн хайлт ашиглан бодох нь ойлгомжтой болов. Бодлогон дээр тооцох хийх зүйл хэтэрхий их учраас амжсангүй.

Coding Phase -н дараа Division Summary харахад 500 -с хойш байлаа. 2 бодлого минь 2уулаа л давахгүй бол эхний 600д орж чадахгүй гэсэн үг.

Challenge Phase:

Intermission дээр анзаарсан зүйл минь 500 дээр хүмүүс "тодорхой удаа" гэдгээс болж массивын индекс алдсан байх магадлалтай гэж бодсон.

Эхлээд нэг бодолт нээгээд жаахан буруу юм шиг харагдахаар нь challenge хийгээд 25 оноо алдлаа.
Дараагаар өөр бодолт нээтэл зөв тест өгвөл массивын индекс хэтрэх нь ойлгомжтой байсан учир тийм тест амархан зохиогоод 50 оноо авлаа.
Дахиад нэг хүний бодолт ижилхэн массивын индекс хэтрэх байсан учир тийм тест өглөө, гэтэл нөгөө хүний аз ч юм уу RunTimeError авсангүй. Дахиад тест өгөөд ашгүй 50 оноо авлаа.
-25+50-25+50=50 оноо авжээ.

System Test дуусч 2 бодлого ч давжээ. Ингээд 359т орж дараагийн шатанд оролцох эрхтэй болов.

Topcoder "diary" SRM 468 (division 2)

Өнгөрөгч SRM дээр 500-гаа алдаатай бичиж явуулаад 2 удаа амжилтгүй challenge хийж rating-ээ навс унагасан болохоор энэ удаад аль болох "хашир" тактик баримталж оров :P

Coding Phase

Easy 250:

type: ad hoc, sorting
Уншиж ойлгоход нэлээдгүй хугацаа зарцуулсаныг эс тооцвол хялбархан бодчихсон :)

Medium 500:

type: string parsing, sorting
Гар утасны "T9 dictionary"-н програмчлалыг бичих бодлого. Жаахан түвэгтэй л юм байна лээ. Кодоо бичихэд их хугацаа зарцуулсан. Азаар нэг их мунгинаж олон "debug" хийгээгүй. Бичиж дуусаад submit хийгээд цагаа харвал 17 минут үлдсэн байлаа. Арай л их хугацаа зарцуулчихаж дээ.

Hard 1000:

type: bfs л юм шиг санагдсан :D
Хугацаа бага үлдсэн ч гэсэн амжуулах гэж оролдсон. Цаг дуусахаас хэдхэн минут үлдсэн байхад яагаад ч амжихгүй гэдгээ ойлгоод больсон доо :)

Challenge Phase:

Хальт гүйлгээд л харсан. 250 дээр угаасаа алдсан хүн байхгүй л харагдана лээ. Бусад хүмүүсийн 500-гийн бодолтыг хальт харахад бол ойлгохгүй юм байна лээ. Сайн ойлгоогүй бодлогон дээр challenge хийж азаа үзэх хэрэггүй гэж энэ удаад шийдэв.
Манай өрөөнийхөн ч хашир байна даа. Өрөөнийхөн нийтдээ 3 удаа challenge хийж 3-уулаа амжилтгүй болох шив дээ. Challenge Phase-аа дуусгалгүй үүнийг бичиж эхлэв :P

System Testing Phase:

Хүлээгээд л байж байна :D Хэрвээ 2 бодлого маань 2-уулаа тэстээ давчихвал эхний 70-д орчих л юм шиг байна :)

Програмчлалын улсын 20-р олимпиад

SMCS баг

Олимпиадад нийт 7 бодлого ирсэн ба одоогоор файлаар олдсон 3 бодлогыг блогт нэмлээ. Мөн хүмүүст жаахан ч гэсэн сонирхолтой байж магад гэсэн үүднээс өөрийн багийн (Хонгор,Мөнх-Очир,Алмабек) оролцсон тэмдэглэлийг бичье.

Сүүлийн үед өөрийн гэсэн template их хэрэглэдэг болсон учир компъютер дээрээ суугаад шууд template-ээ бичив.
Бодлого ирлээ. Эхлээд нэг нэг бодлогоо уншлаа, миний уншсан бодлого нь Word гэсэн нэртэй бодлого байлаа. Шууд л DP + Matrix байсан учир (гэхдээ DP-ээ хараахан гаргаагүй) Matrix struct - аа бичиж эхлэв, тэгээд байж байтал Алмабек энд граф-н хамгийн их урсгалыг олох бодлого байна гэв. Хартал илүү дутуу юмгүй шууд Maximum Flow байв. Maximum Flow - г хангалттай их бичсэн учир бараг энэ нь гайгүй гэж бодоод дахиад л Maximum Flow бичиж эхлэвээ. Гэтэл Мөнх-Очир нэг бодлого үзүүлээд (a^b)%c олох бодлого байна гэв. Энэ бол хангалттай олон бичиж байсан бодлого учир шууд бичив, гэтэл жаахан bug гарсны гайгаар 22 дах минутанд анхны Yes -г авав.

Үүний дараа бодож санах юмгүй өмнөх Matrix-тай бодлогоо бичлээ, эхний хэдэн минутанд Matrix struct бичээд бараг л дууссан байсан учраас хийх зүйл нь DP байгуулах л байв. Бодлого энгийн байсан учраас үүнийг гялс хийгээд жишээ оролтууд ажиллаж байсан учир 29 дах минутанд submit хийв. Гэтэл No -Wrong Answer :(. Үнэхээр гайхав ..... Гэтэл үнэхээр жижигхэн алдаа байсан ба засаад 31 дах минутанд submit хийлээ. 2 дах Yes.

Одоо өмнө "сэглэсэн" Maximum Flow бодлогоо бичээд submit хийв. 46 дах минутанд Yes авлаа.

Ингээл тэмцээний дүнг хартал Манай баг 3 бодлоготой, бусад баг хараахан бодлого бодоогүй байв. Ингээд жаахан амьсгаа авлаа. Мөнх-Очир нэг бодлого уншиж байх хооронд Алмабек надад нэг бодлого үзүүлэв, тэр бодлого граф-н бүх Articulation Point-г олох бодлого байсан ба азаар би чадахгүй гэдгээ мэдэж байсан учир энэ бодлогыг бүр мөсөн хаяв. Мөнх-Очир оролдож байсан бодлогоо бодох аргыг олоод тэгээд Мөнх-Очир -н заавраар би бичив. 2 хүн бичсэн учир үнэхээр алдаагүй сайхан бичсэн. Тэгээд ганц нэг алдаа засаад жишээ оролт давангууд submit хийв. 72 дах минутанд Yes.

Ингээд 3 бодлого үлдсэн ба 1-г нь бүр мөсөн хаясан учир 2 бодлого үлдэв. Ball & Болхи схем. Ball гэдэг бодлого угийн амар бодогдчих эд биш байсан учир би оролдохоос татгалзаад Мөнх-Очирт өгөв. Мөнх-Очир уншиж байсан бодлогоо надад тайлбарлаж өгөв. Гэхдээ бид 2 Болхи-Схем бодлогыг нэг л ойлгож өгөхгүй байсан. Тэгээд зохиогчийг нь дуудаж тайлбар аваад арай дээрдсэн ч бүтэн ойлгосонгүй. Өрөө олон хүнтэй халууцаад байсан болохоор 00 оронгоо сэрүүцээд авав. Тэгээд орж ирээд бүтэн ойлголоо. Одоо яаж бодох вэ? :D. Ингээд энэ хэсэг дээр ~30 орчим минут болсон байх. Тэгээд бодож байтал бодлогын нөхцөл ёсоор мэдрэгч тавьсан ирмэгүүдийг таславал юу болох вэ? Мэдээж Граф-д цикл үлдэхгүй. Циклгүй чигэлгүй граф = Мод. Уг таслаж байгаа ирмэгүүдийн нийлбэр хамгийн бага учир зүгээр ч Мод биш "Хамгийн их үнэлгээт" мод юм. Мэдээж Kruskal -н алгоритмаар бодож болох байлаа. Гэхдээ хязгаарлалтыг харахад тийм ч амар биш 40000 орой + 160000 ирмэг. Иймээс Disjoint-Set өгөгдлийн бүтцийн тусламжтайгаар O(Ирмэг * log Орой) д бодож болно. Ингээд амжих нь тодорхой учир бичиж эхлэв, бодлогын оролтыг граф болгоход бас л төвөгтэй байсан учир их ч алдаж их ч удлаа. Ингээд жишээ оролт давсны дараа submit хийв. 159 дах минутанд Yes.

Одоо нэг л бодлого үлдсэн ба тэрийг үнэхээр барсангүй. Сүүлийн 2 цаг олон юм хийсэн дээ. Minesweeper+Утасны тоглоом+...... кк.

Submit 1 - Pandora - 22 - Yes
Submit 2 - Word - 29 - No Wrong Answer
Submit 3 - Word - 31 - Yes
Submit 4 - AAN - 46 - Yes
Submit 5 - Meet - 72 - Yes
Submit 6 - Bolhi - 159 - Yes

Энэ манай багийн 5 бодлогыг 159 минутанд бодсон бяцхан түүх байлаа. Одоо бүсийн тэмцээнд илүү амжилттай орохын төлөө.....

MNPC 2010-н бодлогууд - AAN

Artificial Neural network
Нейрон нь мэдрэлийн эсүүд болон тэдгээрийн хооронд мэдээлэл дамжуулах сувгуудаас тогтоно. Тэдгээр нь хэд хэдэн давхаргуудаас тогтох бөгөөд эхний ба сүүлийн давхарга нь нэг нэг эсээс тогтоно. Эхний ба сүүлийн давхаргуудын хооронд мэдээлэл дамжих боломжтой байдаг байна. Нэг эсээс нөгөө эс рүү сувгаар дамжих мэдээлэл нь хэмжээтэй. Тэгвэл эхний давхаргаас сүүлийн давхарга хүртэл мэдээлэл хүрч болдоггүй байхаар сувгуудыг хасахдаа хассан сувгуудын нийт мэдээллийн хэмжээ нь хамгийн бага байх програм зохио.
Оролт:
Оролт нь 5-аас илүүгүй тест агуулах ба тестийн бүтэц дараах хэлбэртэй байна. Эхний мөрөнд мэдрэлийн эсийн тоо N<=125 болон мэдээлэл дамжуулах сувгуудын нийт тоо M<=300 гэсэн тоонууд нэг хоосон зайгаар тусгаарлагдан байрлана. Дараагийн М мөр тус бүрт A B W тоонууд нэг хоосон зайгаар тусгаарлагдан байрлана. Үүнд: А, B тоонууд нь мэдрэлийн эсийн дугаарууд W (0<=10000 натурал тоо) нь мэдээллийг дамжуулах хэмжээ болно. A-гаас B-д мэдээлэл дамждаг байхад B-гээс A-д мэдээлэл дамжихгүй. Мөн эхний давхарга болон сүүлийн давхарга дахь эсийн дугаар нь 0 ба N-1 байна. Тестийн төгсгөлд N=0 M=0 байна.
Гаралт:
Гаралтанд тест бүрд харгалзах хассан сувгуудын нийт мэдээллийн хэмжээний хамгийн бага утгууд нэг нэг мөрөнд байрлана. Гаралтын төгсгөлд нэг мөр авсан байна.
Жишээ:
Оролт:
7 8
0 1 2
0 2 1
1 3 3
2 3 5
2 4 4
3 6 2
4 5 2
5 6 3
4 4
0 1 3
0 2 4
1 3 5
2 3 2
0 0
Гаралт:
3
5

MNPC 2010-н бодлогууд - Улс

Улс
Улс нь N ширхэг хоттой. Хот бүрээс өөр хот руу очиж болдог замууд (Хэд хэдэн хотоор дамжин очиж болно) байжээ.
Хотуудыг 0 ээс N-1 хүртэл дугаарлажээ. Нэг хотоос нөгөө хотод очих зам олддог бол харилцаатай хотууд гэе. Хэрэв тухайн хотоос гарах бүх замуудыг таслахад ямар нэгэн харилцаатай байсан хоёр хотын харилцаа тасардаг бол энэ хотыг “сайн” хот гэе.
Та “сайн” хотуудыг олох програм бичнэ үү.

Оролт:
Оролт нь нийт 5-аас ихгүй тест агуулах ба тестийн бүтэц нь дараах хэлбэртэй.
Эхний мөрөнд N<175000, M<265000 натурал тоонууд нэг хоосон зайгаар тусгаарлагдан байрлана.
Дараагийн М мөрөнд A,B тоонууд нэг хоосон зайгаар тусгаарлагдан байрлана.
A, B-хотын дугаар бөгөөд A,B хотууд хоорондоо замуудтай болохыг илэрхийлнэ.
Тестийн төгсгөлд N=0 M=0 байна.
Гаралт:
Тестийн тоонд харгалзах тохиолдлууд дараах байдлаар байна.
Тохиолдол бүрт харгалзах тоонуудыг өсөх эрэмбээр нэг нэг мөрөнд гаргана. Гаралтын төгсгөлд нэг мөр авсан байна.
Жишээ:
Оролт:
7 6
0 3
1 2
2 4
3 4
4 6
5 6
5 5
0 1
1 2
1 4
2 3
2 4
0 0
Гаралт:
2
3
4
6
1
2

MNPC 2010-н бодлогууд - Болхи схем

Болхи схем
Болхи схем өгөгджээ. Түүний бүтэц нь зангилаанууд болон тэдгээрийг холбосон холбогчуудаас тогтоно. Хоорондоо параллель N ширхэг утас мөн тэдгээрт перпендукляр M ширхэг утастай.(Зургийг хар)

Зураг

Мэдрэгч нь холбогч дээр байрлах ба холбогч бүр нь мэдрэгч тавихад тодорхой үнэтэй.
Мэдрэгч бүр нь холбогчоор гүйж байгаа электроны дугаар, хугацаа болон хөдөлгөөний чиглэлийг мэдээлнэ.

Мэдрэгчүүдийн мэдээллээр битүү маршрутаар (маршрут нь нэг явсан газраараа дахин явахгүй байна) явж байгаа ямар ч электроны явсан замыг нэг утгатай тодорхойлж чаддаг байхаар хамгийн бага үнэтэйгээр мэдрэгчүүдийг тавих програм бич.

Оролт:
Оролтын эхний мөрөнд T<=5 өгөгдөх ба тест бүр нь дараах бүтэцтэй. Оролтын эхний мөрд N, M (1<=200)гэсэн натурал тоонууд нэг хоосон зайгаар тусгаарлагдан байрлана. N нь схемийн хэвтээ утасны тоо, M нь босоо утасны тоо. Дараагийн (M-1)*N мөрөнд хэвтээ холбогчуудын мэдрэгч тавих үнүүд өгөгдөнө. Эдгээрийг нь утаснуудыг дээрээс нь доошоо, холбогчуудыг нь зүүнээс баруун тийшээ байдлаар өгнө. Түүний дараагийн (N-1)*M мөрөнд босоо холбогчуудын мэдрэгч тавих үнүүд өгөгдөнө. Тэдгээрийн хувьд утаснуудыг зүүнээс баруун тийшээ, холбогчуудыг нь дээрээс доошоо байхаар өгнө. Гаралт:

Тестийн тоонд харгалзах тоонууд нэг нэг мөрөнд байрлана.
Эдгээр тоонууд нь битүү марштрутаар явах электроныг нэгэн утгатай илэрхийлж чадах нийт үнэ нь хамгийн бага байхаар байрлуулах мэдрэгчүүдийн үнүүдийг нийлбэр байна. Гаралтын төгсгөлд нэг шинэ мөр байна.
Жишээ:
Оролт:
2
3 3
2
4
7
5
2
5
7
7
3
1
2
2
2 2
3
3
2
1Гаралт:
7
1

Монголын үндэсний програмчлалын олимпиад II

Монголын үндэсний програмчлалын II олимпиад 2010 оны 04 сарын 3-нд амжилттай явагдаж өнгөрлөө. Тэмцээний товч дүнг танилцуулъя.

1. МУИС - МКС 1-р баг - 5 оноо
Бүрэлдэхүүн : Хонгор, Мөнх-Очир, Алмабек
2. МУИС - МТС 2-р баг - 3 оноо
Бүрэлдэхүүн : Өсөхбаатар, Жамсрандорж, Мөнхжаргал
3. МУИС - МКС 2-р баг - 1 оноо
Бүрэлдэхүүн : Нямдаваа, Авирмэд, Ганбат
4. МУИС - МТС 1-р баг - 1 оноо
Бүрэлдэхүүн : Мөнгөншагай, Сүрэн, Хуягбаатар

Багийн гишүүдийг буруу бичсэн бол хэлж засуулна уу?

3-р сарын тэмцээн бодолт - 1

Jenny and you, BCC :

Энгийн оролт гаралттай ажиллах бодлого.


Хуваалт :

3/4 pizza иддэг хүмүүст тус тусад нь бүтэн pizza өгөхөөс аргагүй билээ. Ингээд үлдэгдэл 1/4 хэсгүүдийг 1/4 иддэг хүмүүст өгөх нь хэрэгтэй.
Тэгэхээр манай бодлого 1/4, 2/4 бодлоготой ижилхэн боллоо л гэсэн үг. 2/4 иддэг хүмүүсийг хоёр хоёроор нь хос болгон авч үзээд пиззаг өгөх хэрэгтэй. Ингэхэд нэг хүн сондгойрч болох ба энэ хүнийг 1/4 иддэг 2 хүнтэй хос болгоод, үлдсэн 1/4 иддэг хүмүүсийг дөрөд дөрвөөр хос болгоход хангалттай.
Баталгаа :
1/4, 2/4 хүмүүст дээрх санаагаар pizza хуваарилахад гагцхүү ганц pizza-с үлдэгдэл гарч болох учир уг бодолт зөв юм.


Хамгийн ойр нийлбэр :

Бүх боломжийн тоо 2^N болох учир хэтэрхий их болно. Гэхдээ N1=N/2, N2-N-N1 байхаар хоёр хэсэгт хуваагаад бүх нийлбэр S1[0..N1-1], S2[0..N2-1] бодож олъё. N1,N2<=19 тул санах ойд ч багтна. Одоо S2-оо эрэмбэлээд бүх i=0..N-1 хувьд S1[i]+S2[j]>=K байх j-г хоёртын хайлтаар олъё.
Бидний сонирхож байгаа нийлбэр j-1, j, j+1 3-н аль нэг болох учир бүгдийг шалгавал бодлого бодогдно.
Шаардагдах хугацаа:
Бүх нийлбэрийг олох - O(2*2^(N/2))
Эрэмбэлэлт - O(2^(N/2)*(N/2)),
Хоёртын хайлтаар бүх боломжит нийлбэрийг олох
O(2^(N/2)*(N/2)*3)
Иймд энэ бодолт O(2^(N/2)*(N/2)) болно.
Тайлбарыг Anonymous хийв. (Чимэд ах???)


Цэцэг тарив :

Зөвлөгөө : Өгөгдлийн бүтэц. ( Interval Tree? ) O(N * sqrt ( N )) эсвэл O(N * log N)


Гайхамшигт хослол :

Хамгийн муу тохиолдолд олонлог маань 8*7*6*5*4=6720 элемэнттэй байж болно.
Эхний буюуу хамгийн муу бодолт нь уг олонлогоос шууд дөрвөн тоо сонгож аваад "гайхамшигт хослол" үүсэх эсэхийг шалгах. Энэ бодолт O (N ^ 4) байх нь ойлгомжтой.
Дараагийн бодолт нь гайхамшигт хослолыг нийлбэрт орж буй 3 тоогоор илэрхийлж болно гэдгийг хараад a+b+c тоо олонлогт орших эсэхийг O(1)-д шалгаснаар O(N ^ 3) болно.
Эцсийн бодолт:
a+b+c=d илэрхийллийг a+b=d-c хэлбэртэй бичээд илэрхийллийн 2 талыг хайснаар O(N ^ 2) -д бодож болно

2-р сарын тэмцээн Бодолт - 2

Happy Single`s Day
Уг бодлогын санаа "Авсаархан Шийдлүүд - 1" бичлэг дээр бичигдчихсэн байв :)

Болхи тоо
(1<=Ni<=10000) гэдгээс F(N) < 2^63 байх юм. (Үүнийг тооцож үзээд шалгачихаж болно) F(K) - нь болхи тоо гэдгээс F(K) * 2, F(K) * 3, F(K) * 5 нь тус тус болхи тоо гэж гарна. Энэ аргаар 2^63-аас бага бүх (~12000 ширхэг) "Болхи тоо"-г урьдчилан тооцоолж олоод эрэмбэлнэ. Ингээд эхний 10000 болхи тоо массивт хадгалаастай байх учраас бодлогын оролтонд харгалзах хариуг амархан гаргаад байж болно.

Анхны тоо шалгагч
Эх хувилбар: Spoj.pl/problems/PON
Анхны тоо шалгадаг магадлалт алгоритмууд болох "Фермагийн магадлалт шалгуур", "Миллер-Рабины магадлалт шалгуур" алинаар нь ч бодож болно. Шалгалтын үр дүнг сайжруулахыг тулд эхний цөөн хэдэн анхны тоог урьдчилан бэлтгэж тэдгээрт хуваагдаж байгаа эсэхийг шалгаж болно. (Эхний 1000 анхны тоо юм уу 10000, 100000 хүртэлх анхны тоонуудад хувааж үзэх)

Програмчлахтай холбоотой асуудал нь:
A^B mod C =-г олох явдал. (1<B, C<2^63)
Bigmod(A, B, C) = A^B mod C гэж тэмдэглэе. Дараах байдлаар програмчилж LogN хугацаанд олж болно

LONG BIGMOD(A, B, C) {  if (B mod 2 == 0) {    return SQUARE(BIGMOD(A, B/2, C)) mod C  } else {    return BIGMOD(A, B-1, C) * (A mod C) mod C  }}

Гэвч ингээд бүрэн бодогдчихгүй юм. Учир нь X*Y mod Z үйлдлийг хийх үед X*Y үйлдлийн хариу нь 2^63 зэрэгтээс халих юм. Иймээс X*Y mod Z үйлдлийг (X+...+X) mod Z (Y удаа нэмнэ) байдлаар шийдэж болно. Үүнийг мөн өмнөх зэрэг дэвшүүлэх үйлдэлтэй адилханаар LogN хугацаанд багтааж болно.

MULTIPLY_MOD(X, Y, Z) {  if (Y mod 2 == 0) {    return MULTIPLY_MOD(X, Y/2, Z) * 2 mod Z  } else {    return (MULTIPLY_MOD(X, Y-1, Z) + X) mod Z  }}

MULTIPLY_MOD(X, Y/2, Z) * 2 үйлдэл дээр бас 2^63 -ээс халих асуудал гарах боловч өгөгдлийн төрлөө "UNSIGNED LONG LONG" гэж зааж өгснөөр энэ асуудлыг тойрж болно.

Лавлагаа:
[1] Олон оронтой тооноос үлдэгдэл олох хамаагүй сонирхолтой.

2 сарын тэмцээн - бодолт 1

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

Үржвэр нь N - с хэтрэхгүй байх эхний дараалсан анхны тоонуудын үржвэр хариу болно. Төвөгтэй хэсэг нь Том тооний үйлдэл байх.

Number:

+1+2+...+N илэрхийллийг авч үзье. Ямар нэгэн +i тоог -i болговол нийт нийлбэр маань 2i -р багасах буюу тэгш байсан бол тэгш, сондгой байсан бол сондгой хэвээр үлднэ.
Иймд 1+2+...+N>=K && (1+2+...+N)%2==K%2 байх хамгийн бага N-г олоход тэр нь хариу болно.
K тоо сөрөг үед модуль аван бодоход хангалттай.

Дахиад л шадар гурван квадрат:

Тэгш өнцөгтийг N өндөртэй тэгш өнцөгт гэж үзээд доороос нь эхлэн түвшин түвшингээр дүүргэсэн гэж үзье. Тэгш өнцөгтийн эхний i-1 түвшинг бүтэн дүүргэсэн, i дэх түвшинг бүтэн эсвэл хагас дүүргэсэн боломж нь 16 хэсэгт задарна. 0000, 0001, ...., 1111.
Тэгвэл f[i][j] -р эхний i-1 түвшинг бүтэн дүүргэсэн, i дэх түвшинг j дэх дүүргэлтээр дүүргэсэн нийт боломжийг тэмдэглэе. j нь дээрх битүүдийн 10тын тооллын систем дэх дүрслэл гэж ойлго (0<=j<=15). Тэгвэл f[i][j] = f[i-1][j1] + f[i-1][j2]+... хэлбэртэй томъёо олдно. Энэ аргаар бодвол бодлогыг O(N* 16 ) хугацаанд бодож чадна. f[i] г 1*16 хэмжээс бүхий матрикс гэж үзвэл f[i] * m = f[i+1] байх m матрикс олдно. Матриксын зэргийг log-д олох аргыг хэрэглэвэл бодолт O(16*16*16*logN) болж өгөгдсөн хугацаанд хангалттай амжна.

Муруй зам:

Уг бодлогыг хүн бодоогүй учир бодолтыг бичихгүй :).

Зарлал

Coder.mn сайт дээр сар бүр тогтмол тэмцээн явуулж байхаар тогтсоныг олж уншсан гэж найдаж байна :D. Иймээс үүнтэй холбогдуулан сар бүрийн тэмцээнээс зарим бодлогын бодолтыг нийтлэж байх болно. Тэмцээндээ идэвхтэй ороороой, бас амжилт хүсье!