Хорватын програмчлалын онлайн олимпиад #1

Сүүлийн 3 бодлого:

Бодлого Mag
Бодлого Kralj
Бодлого Vjeτtica

Хорватын Програмчлалын Онлайн Цуврал Олимпиадууд эхэллээ. Монголын Мэдээлэлзүйн Олимпиадыг Зохион байгуулах Хорооноос 2015 онд хийсэн тохиролцооны дагуу энэ жил ч мөн уг олимпиадуудын бодлогууд монгол хэл дээр орчуулагдсан байх болно. Та бүхэн өргөнөөр оролцоно уу.

Хуваарь:

Хорватын Програмчлалын Онлайн Олимпиад #1
2016-10-15 22:00 (Улаанбаатарын цагаар)

Хорватын Програмчлалын Онлайн Олимпиад #2
2016-11-05 22:00 (Улаанбаатарын цагаар)

Хорватын Програмчлалын Онлайн Олимпиад #3
2016-11-26 22:00 (Улаанбаатарын цагаар)

Хорватын Програмчлалын Онлайн Олимпиад #4
2016-12-17 22:00 (Улаанбаатарын цагаар)

Хорватын Програмчлалын Онлайн Олимпиад #5
2017-01-14 22:00 (Улаанбаатарын цагаар)

Хорватын Програмчлалын Онлайн Олимпиад #6
2017-02-04 22:00 (Улаанбаатарын цагаар)

Хорватын Програмчлалын Онлайн Олимпиад #7
2017-03-04 22:00 (Улаанбаатарын цагаар)

Зуны болон өвлийн цагийн шилжилтээс болж нэг цагаар зөрж магадгүйг анхаарна уу.

Мөн 2017 оны 3 сарын 25-нд болох Хорватын Улсын Мэдээлэлзүйн олимпиадыг орчуулах эрхийг авсан эсэхээ хавар мэдэгдэх болно.

http://hsin.hr/coci/

2015 оны Олон улсын мэдээлэлзүйн олимпиадад оролцох сурагчдаас ШУТИС, МХТС-ээс авсан сорилын бодлого, тест

Сум
Сегмент
Ундааны автомат
Сонгууль

Дэд тэмдэгт мөр хайх Морисс-Праттын алгоритм

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


n урттай y тэмдэгт мөрөөс m урттай х тэмдэгт мөрийг хайж байна гэж үзье. Тухайн тохиолдолд у тэмдэгт мөрийн j дэх тэмдэгтээс (0≤j
Моррис-Праттын алгоритм дахь шилжилт (v нь u-гийн хил болно)

Алгоритмын бэлтгэл ажиллагаа болох mpNext хүснэгтийг байгуулах хугацаа O(m) ба ажиллах нийт хугацааг O(n+m) гэж үнэлж болно.

Жишээ:
void preMp(char *x, int m, int mpNext[]) {
int i, j;

i = 0;
j = mpNext[0] = -1;
while (i < m) { while (j > -1 && x[i] != x[j])
j = mpNext[j];
mpNext[++i] = ++j;
}
}


void MP(char *x, int m, char *y, int n) {
int i, j, mpNext[XSIZE];

/* Preprocessing */
preMp(x, m, mpNext);

/* Searching */
i = j = 0;
while (j < n) { while (i > -1 && x[i] != y[j])
i = mpNext[i];
i++;
j++;
if (i >= m) {
OUTPUT(j - i);
i = mpNext[i];
}
}
}

ОХУ-ын Олон Улсын Мэдээлэлзүйн Олимпиадын бэлтгэлийн хөтөлбөр

IOI буюу ОУМЗО дээр дөрвөн сурагч нь бүгд алтан медаль авч чаддаг цөөхөн хэдэн улсын нэг нь ОХУ билээ. Тэдний бэлтгэлийн хөтөлбөрийг орчуулсныг доороос үзнэ үү.
ОХУ-ын Олон улсын Мэдээлэлзүйн олимпиадын бэлтгэлийн хөтөлбөр

Хөтөлбөр дэх дидактикийн нэгж бүрт олон улсын мэдээлэлзүйн олимпиадын бэлтгэлд зориулан тодорхой түвшинг оноосон байгаа. Нийтдээ доор тодорхойлсон гурван түвшин байна:
“*” гэсэн тэмдэггүй дидактикийн нэгжүүд нь анхан шатны түвшинд хамаарна. Энэ түвшний мэдлэгтэй байх нь оролцогч олон улсын олимпиадад ороход тавигдах шаардлагуудыг ойлгоход тус болно. Мөн бодлого бодох сэдэлтэй, өөрийн санааг илэрхийлэх чадвартай байна гэсэн үг юм.
“*” тэмдэгтэй дидактикийн нэгжүүдийг нэмж судлах нь оролцогчид олимпиадын бэлтгэлийн түлхүүр ойлголт, чадваруудад суралцах боломж олгоно. Мөн олимпиадын бодлогыг хангалттай түвшинд шийдэж, өөрийн боломжийг олон улсын түвшинд харуулж шагналт байруудад орох чадвартай болгоно.
“**” тэмдэгтэй дидактикийн нэгжүүдийг эзэмшсэнээр сурагчид өөрийн мэдлэгийн хүрээг тэлж, олон улсын мэдээлэлзүйн олимпиадын тэргүүн байрын төлөө өрсөлдөх чадвартай болно.
Математик үндэс
Функц, харьцаа, олонлог
Функц, урвуу функц, давхар функц
Харьцаа (рефлекс, симметр, транзитив, эквивалент, цагаан толгойн дараалал)
Олонлог (Веннийн диаграм, гүйцээлт, декартын үржвэр)
Бүрэн эрэмбэлэгдсэн олонлог*
Олонлогийн чадал ба тоологдох олонлог**
Геометрийн үндэс
Цэг, шулуун, хэрчим, вектор, өнцөг
Евклидийн огторгуй дахь Декартын координатууд
Евклидийн зай
Хавтгай дээрх вектор болон скаляр үржвэр
Гурвалжин, тэгш өнцөгт, олон өнцөгт
Гүдгэр олон өнцөгт
Тригонометрийн функцууд болон томъёонууд*
Воронойн диаграм ба Делонегийн триангуляц**
Логикийн үндэс
Логик хувьсагч, үйлдэл, илэрхийлэл
Үнэний хүснэгт
Булийн функц
Квантор (универсал, оршин байх)
Логик функцийн өгөгдөх болон үүсгэх хэлбэр
Логик илэрхийллийг хувиргах
Нормал хэлбэр (конъюнктив и дизъюнктив) *
Булийн функцийг минималчлах *
Логикийн үндсэн хуулиуд *
Предикатын логик *
Тооцооллын үндэс
Тооцооллын үндэс:
Нэмэх ба үржүүлэх дүрэм
Арифметик ба геометр прогресс
Фибоначчийн тоо
Оруулж-хасах зарчим *
Рекуррент харьцаа
Матриц ба түүн дээр гүйцэтгэх үйлдэл *
Тоо болон матрицийг хурдан үржүүлэх**
Баталгааны аргууд
Шууд баталгаа
Дирихлейн зарчим
Эсрэг жишээгээр батлах
Эсрэгцүүлэн батлах
Зөрчилд оруулан батлах
Математик индукц
Тооны онолын үндэс
Анхны тоо. Арифметикийн үндсэн теорем
Үлдэгдэлтэй хуваах
ХИЕХ
Харилцан анхны тоо
Үлдэгдлийн ангиуд*
Үлдэгдлийн тухай хятадын теорем*
Анхдагч язгуур ба дискрет логарифм**
Алгебрын үндэс
Олон гишүүнт ба түүн дээр хийгдэх үйлдлүүд. Квадрат тэгшитгэл. Виетийн теорем.
Виетийн теоремийн ерөнхий хэлбэр. Симметр олон гишүүнт*
Бүлгийн тухай ойлголт**
Бүлгийн шинж чанарууд**
Энгийн дэд бүлгүүд**
Гомоморфизм болон изоморфизмын тухай теорем**
Комбинаторикийн бодлогыг бодоход бүлгийн онолыг хэрэглэх**
Хослолын онолын үндэс
Сэлгэмэл, гүйлгэмэл ба хэсэглэл:
Үндсэн тодорхойлолт
Паскалийн дүрэм
Биномын теорем
Грейн код: дэд олонлог, хэсэглэл, сэлгэмэл*
Сэлгэмлийн инверсийн хүснэгт *
Дэд олонлогт хуваах. Стирлингийн тоо*
Хаалтуудын дараалал*
Хаалтуудын дараалал болон бусад комбинаторикийн объектуудын холбоо(хоёртын болон өлгөсөн мод, триангуляц)**
Комбинаторикийн объектуудын тооны үнэлгээ. Стирлингийн томъёо. Мөрдлөгөөнүүд.**
Графын онол
Графын төрлүүд
Зам ба холбоос
Граф дээрх үйлдлүүд
Моднууд
Холболтын мод (spanning tree)
Графыг будах
Эйлерийн болог Гамильтоны граф
Бүрхэлт ба үл хамаарал*
Графыг зурах. Хавтгай граф*
Давхар холбоост граф. Гүүр, блок, мөчлөгийн цэг*
Чиглэлтэй циклгүй граф ба эрэмбийн харьцааны холбоо. Транзитив битүүрэл*
Хоёр талт граф*
Урсгал ба сүлжээ*
Сүлжээний графикийг төлөвлөх*
К-холбоост граф**
Магадлалын онолын үндэс
Магадлал болон математик дунджийн тухай ойлголт. Магадлалын онолын аксиомууд*
Бүтэн магадлалын томъёо болон Байесын томъёо. Нөхцөлт математик дундаж**
Тестлэхэд зориулан санамсаргүй объектуудыг үүсгэх**
Оновчлолын бодлогын дөхөлтийн аргууд**
Тоглоомын онолын үндэс
Тоглоом болон тоглоомын үр дүнгийн тухай ойлголт
Энгийн тоглоом болон стратеги
Грандийн функц*
Матриц дээрх тоглоом**
Шугаман програмчлал
Шугаман програмчлалын бодлогын тавил. Шугаман програмчлалын бодлогын геометр тайлбар *
Шугаман програмчлалын бодлогыг бодох үндсэн аргууд:симплекс арга, хүснэгтийн арга**
Шугаман програмчлалын хосмог бодлого**
Урсгал хайх, ажил хуваарилах, богино замын тухай бодлогууд шугаман програмчлалын жишээ бодлогууд болох нь**
Бүхэл тоон програмчлалын тухай ойлголт**
Математик анализын үндэс
Уламжлал ба интеграл. Талбайг тооцоолох. *
Гриний томъёо**
Автомат ба дүрэм
Төгсгөллөг автоматын тухай ойлголт**
Төгсгөллөг автомат ба дүрэм**
Практик дээр бодлого бодоход төгсгөллөг автоматын хэрэглээний үндэс**
Нормал хэлбэрүүд ба тэдгээрийг дүрмийн шинжилгээ хийхэд ашиглах**
Алгоритмын шинжилгээ ба зохиомж
Алгоритм ба түүний шинж чанар
Алгоритмын тухай ойлголт
Алгоритмын зарчим ба шинж чанар
Алгоритмыг формал бус хэл дээр бичих
Өгөгдлийн бүтэц
Энгийн үндсэн бүтцүүд
Олонлог
Дараалал
Жагсаалт
Чиглэлгүй граф
Чиглэлтэй граф
Мод
Пирамид ба хэрчмийн мод* (Фенвикийн мод г.м)
Фенвикийн мод ба түүний олон хэмжээст хэлбэр*
Тэнцвэртэй мод *
Хэш-хүснэгт ба ассоциатив массив *
Угтварын мод**
Залгаврын мод**
Алгоритмын шинжилгээний үндэс
Том О тэмдэглэгээ
Алгоритмын үнэлгээний стандарт ангиуд
Алгоритмын хамгийн муу болон дундаж тохиолдлын асимптотик үнэлгээ
Алгоритмын санах ой болон ажиллах хугацааны хоорондох холбоо*
Рекурсив алгоритмын шинжилгээнд рекуррент харьцааг хэрэглэх*
Бүрэн NP бодлогууд**
Үр ашигтай тооцоологдох чанар**
Универсал алгоритм ба өөртөө хэрэглэгдэх чанар**
Матроид**
Алгоритмын стратегиуд
Бүх боломжийг шалгах алгоритм
"Шуурхай" алгоритм
"Хуваагаад эзэмш" төрлийн алгоритм *
Буцаалттай хайлт*
Эвристик *
Салаа болон хилийн арга**
Хайлшийн арга**
Дөрвөн оросын алгоритм**
Рекурс
Рекурсийн тухай ойлголт
Математикийн рекурсив функц
Энгийн рекурсив процедур
Рекурсийг хэрэгжүүлэх
"Хуваагаад эзэмш" зарчим*
Рекурсээр буцаалттай хайли гүйцэтгэх*
Тооцооллын үндсэн алгоритмууд
Энгийн тоон алгоритмууд
Комбинаторикийн сонгодог алгоритмууд
Дэд олонлогийн алгоритмууд: үүсгэх, дугаараар нь сэргээх, дугааруудыг олох, дараагийн болон өмнөх дэд олонлогийг үүсгэх (элемент нэмэх ба хасах)
Хэсэглэл ба сэлгэмлийн алгоритмууд: үүсгэх, дугаараар нь үүсгэх, дугааруудыг олох, дараагийн болон өмнөхийг үүсгэх.
Шугаман болон хоёртын хайлтын алгоритмууд
Квадрат хугацаатай эрэмбэлэх алгоритмууд (сонгон эрэмбэлэх, оруулж эрэмбэлэх)
Шугаман хугацаанд тоолж эрэмбэлэх.
O(N log N) хугацаатай эрэмбэлэх алгоритмуу (түргэн эрэмбэлэлт, пирамид эрэмбэлэлт,
хольж эрэмбэлэх) *
Цифрээр эрэмбэлэх*
Тэмдэгтүүдийнх нь сэлгэмлүүдийг цагаан толгойн дарааллаар эрэмбэлсний дараах үгийн дугаарыг тооцоолох алгоритм*
Олон оронтой бүхэл тоон дээрх арифметикийн үйлдлүүд*
Тооны онолын алгоритмууд
Тоог анхны тоон үржвэрт задлах
Эратосфены тор
Евклидын алгоритм
Евклидийн өргөтгөсөн алгоритм. Алгоритмыг хуваалт ашиглалгүйгээр хэрэгжүүлэх*
Евклидийн алгоритмыг ашиглан шугаман харьцуулалтуудыг шийдэх*
Эратосфены торыг богино хугацаанд хэрэгжүүлэх (O(n)) *
Гауссын арга ба урвуу матриц**
Модуль ашиглан зэрэгт дэвшүүлэх хурдан алгоритм. RSA нууцлал**
Дискрет логарифмчлал**
Модулиар язгуур авах**
Анхны тоо эсэхийг шалгах үр ашигтай алгоритм**
Тоог анхны тоон үржвэрт хурдан задлах алгоритм. Ро-эвристик**
Берлэкэмпийн алгоритм**
Тэмдэгт мөрийн алгоритмууд
Тэмдэгт мөрөөс дэд тэмдэгт мөр хайх. Энгийн арга
O(N+M) хугацаанд тэмдэгт мөрөөс дэд тэмдэгт мөр хайх алгоритмууд (Кнут-Моррис-Пратын болон Z-алгоритм) *
Үелэх болон цикл тэмдэгт мөр*
Редакцийн зай болон оновчтойгоор тэнцүүлэх*
Бойер-Мурын алгоритм**
Шугаман хугацаанд хэд хэдэн дэд тэмдэгт мөр хайх Ахо-Корасикийн алгоритм**
Залгаврын мод байгуулах алгоритм**
Залгаврыг цифрээр эрэмбэлэх**
Анхны тэмдэгт мөрүүдэд задлах**
Залгаврын автомат байгуулах**
Графын алгоритмууд
Модны богино замын уртыг тооцоолох
Графын түвшний болон гүний нэвтрэлт
Түвшний нэвтрэлтийг хэрэгжүүлэх аргууд(“энгийн” болон дараалал ашигласан)
Графыг холбоост эсэхийг шалгах
Жинтэй графын богино зам хайх алгоритмууд
Графын тополог эрэмбэлэлт, хүчтэй холбоостой компонентыг олох эрэмбийн диаграм байгуулах*
Сөрөг урттай цикл — шалгах нөхцөл, хайх*
Хугацааг синхрончлох бодлого болон тэнцэтгэл бишийн системийн тухай бодлого*
Эйлерийн циклийг олох алгоритм (цагаан толгойн хувьд хамгийн бага) *
Графын транзитив битүүрлийг олох*
Жинтэй, бүрхэлтийн модыг олох алгоритмууд*
Хоёр холбоост компонент, мөчлөлтийн цэг, гүүрийг гүний нэвтрэлтээр олох алгоритмууд*
Хоёр талт графаас хамгийн их хос оноолтыг болон оройн хамгийн бага бүрхэлтийг олох алгоритм*
Сүлжээн дэх хамгийн их урсгалыг хайх**
Хамгийн бага үнэлгээтэй урсгалыг хайх**
Ажил хуваарилалтын тухай бодлогыг шийдэх Унгар арга. Унгар арга, хамгийн бага үнэлгээтэй урсгал болон Дейкстрагийн алгоритмын хоорондын холбоо**
О(N3) хугацаанд хамгийн их урсгалыг олох хурдан алгоритмууд**
Динамик програмчлал
Динамик програмчлалын үндсэн санаа. Рекурсивээр болон циклээр хэрэгжүүлэх.
Хүснэгт дээрх монотон чиглэлтэй хөдөлгөөнтэй бодлого
Үүргэвчний тухай бодлого– динамик програмчлалын аргаар бодох
Үүргэвчний тухай бодлогыг динамик програмчлалын аргаар бодох үеийн оновчлол (илүү параметруудыг хасах) *
Динамик програмчлалын бодлогын шийдийг сэргээх *
Динамк програмчлалын бодлогыг бодох ерөнхий схем *
Нэг хэмжээсээр нь болон дэд олонлогоор динамаик програмчлалыг гүйцэтгэх *
Нэг хэмжээсээр хийгдэх түргэн динамик програмчлал *
Тоглоомын онолын алгоритмууд
Тоглоомын бодлогуудыг бодоход динамик програмчлал, бүх боломжийг шалгах аргуудыг ашиглах. Циклгүй граф дээрх тоглоомууд*
Циклтэй граф дээрх тоглоомыг шийдэх ретроанализын арга ба түүний үр ашигтай хэрэгжүүлэлт**
Булийн илэрхийллийг товчоор тооцоолох алгоритмыг тоглоомын шинжилгээнд хэрэглэх**
Байрлалын үнэлгээ. Альфа-бета огтлол**
Геометрийн алгоритмууд
Цэг, цацраг, шулуун болон хэрчмийн давхцлыг тодорхойлох алгоритмууд
Цэг, шулуун болон хэрчмийг хавтгай дээр дүрслэх
Хавтгай дээрх объектуудын хоорондын зайг олох*
Хавтгай дээрх хэрчмүүдийн огтлолцлыг тодорхойлох алгоритмууд*
Оройн координатуудаараа өгөгдсөн олон өнцөгтийн талбайг тооцоолох алгоритмууд. Бүхэл тоон торны тохиолдол(Пикийн томъёо) *
Гүдгэр бүрхүүл байгуулах алгоритмууд (Грэхем ба Жарвисын алгоритм) *
Хавтгай дээрх тойрог ба түүний бусад объекттой хийх огтлолцол*
Цэг олон өнцөгт дотор оршиж байгаа эсэхийг шалгах*
Шилжих шулууны арга*
Хагас хавтгайн арга**
“Бэлэг боох” арга**
Хавтгай дээр хамгийн ойр хоёр цэгийг олох үр ашигтай алгоритм**
Воронойн диаграмыг үр ашигтайгаар байгуулах алгоритм**
Програмчлалын үндэс
Програмчлалын хэлүүд
Програмчлалын хэлүүдийн ангилал
Процедур хандалтат хэлүүд
Дээд түвшний хэлний синтакс болон семантикийн үндэс
Синтаксийг тодорхойлох формал аргууд:
Бэкуса-Наурын хэлбэр *
Объект хандалтат хэлүүд*
Програмчлалын үндсэн бүтцүүд
Хувьсагч, төрөл, илэрхийлэл ба утга олголт
Оролт/гаралтын үндэс
Нөхцөл шалгах болон давталтын операторууд
Функц ба параметр дамжуулалт
Бүтцийн задлал*
Хувьсагч ба өгөгдлийн төрөл
Өгөгдлийн төрөл - утгуудын олонлог болон тэдэн дээр хийх үйлдлүүд болох нь
Зарлалтын шинж чанарууд (холболт, харагдах муж, блок ба амьдрах хугацаа)
Төрөл шалгах аргууд
Өгөгдлийн бүтцийн төрлүүд
Энгийн төрлүүд
Массив
Бичлэг
Зөв өгөгдлийн бүтэц сонгох стратеги
Өгөгдлийг санах ойд дүрслэх*
Санах ойг статик, автомат болон динамикаар хуваарилах*
Заагч ба заалт*
Холбоост өгөгдлийн бүтцүүд*
Стек, дараалал болон хэш-хүснэгтийг хэрэгжүүлэх *
Граф болон модыг хэрэгжүүлэх аргууд*
Хийсвэрлэлийн механизм.
Процедур, функц и итераторууд хийсвэрлэлийн механизм болох нь
Параметржүүлэх механизмууд (заалт ба утга)
Програмчлалын хэлэн дэх модулиуд
Төрлөн параметр болон параметрчлэгдсэн төрлүүд**
Үндсэн алгоритмуудыг програмчлахад гарах онцлогууд.
Бодлого бодох стратеги
Бодлого бодох ажиллагаанд алгоритмын гүйцэтгэх үүрэг
Алгоритмуудыг хэрэгжүүлэх стратегиуд
Рекурсийг хэрэгжүүлэх
Зүгшрүүлэх стратеги*
Мэдээллийн технологийн үндэс
Тоон логик
Логик схемүүд
Тооллын систем
Компьютерийн арифметик
Өгөгдлийг компьютерийн санах ойд дүрслэх
Бит, байт болон үг
Тоон өгөгдлийн дүрслэл *
Бэхлэгдсэн болон хөвөх таслалтай системүүд *
Тэмдгийн бит болон гүйцээлт байдлаар кодлох *
Тоон бус өгөгдлийг дүрслэх (тэмдэгтийн код, графикийн өгөгдөл) *
Массив болон бичлэгийг дүрслэх*
Компьютерийн ажиллагааны зохион байгуулалт
Фон Нейманы зарчим
Удирдах төхөөрөмж: командыг унших, задлах болон гүйцэтгэх
Командын багц болон төрөл(өгөгдөл боловсруулах, удирдлагын, оролт-гаралтын)
Командын форматууд *
Хаяглалтын горимууд *
Процедурыг дуудах болон түүнээс буцах механизм*
Оролт-гаралт болон тасалдал*
Компьютер санах ойн төхөөрөмж
Үндсэн санах ойн зохион байгуулалт ба түүн дээр хийх үйлдлүүд
Санах ойн шатлал
Өгөгдлийг кодлох, өгөгдлийг шахах болон бүрэн бүтэн байдлыг нь хангах*
Кэш санах ой*
Холболт, харилцан үйлчлэл
Оролт-гаралтын үндэс
Гадаад санах ой, физик зохион байгуулалт ба төхөөрөмж
Сүлжээний технологийн үндэс
Санах ойн шууд хандалт*
Үйлдлийн систем
Үйлдлийн системийн үндэс
Үйлдлийн системийн үүрэг ба асуудлууд
Энгийн үйлдлийн системийн ажиллагаа
Хавтас: агуулга ба бүтэц
Нэрлэх, хайх, хандах, нөөц хуулбар үүсгэх
Үйлдлийн системийн үндсэн функцууд
Хийсвэрлэл, процес ба нөөцүүд
Төхөөрөмжийн зохион байгуулалт
Хамгаалалт, хандалт болон нэвтрэх
Санах ойн удирдлага
Физик санах ой болон санах ойг удирдах техник хангамжийн тухай
Санах ойн хуудаслалт ба сегментчлэлт *
Кэш санах ой *
Програмчлалын технологийн үндэс
Програмчлалын хэрэгсэл ба орчин.
Програмчлалын орчин
Тестлэх хэрэгслүүд *
Програм хангамжийг тестлэх
Тестлэлтийн үндэс, тестийн төлөвлөгөө ба тест үүсгэх*
Тестлэх «хар хайрцгийн» болон «цагаан хайрцгийн» арга *
Нэгжийн, нэгдсэн, системийн тест болон хүлээн авах тест*
Ачааллын тест *
Тооцооллын болон загварчлалын аргууд
Тооцон бодох математикийн үндэс.
Тооцон бодох математикийн үндсэн аргууд
функцийн утга болон язгуурыг тооцоолох *
хавтгай дүрсийн периметр, талбай болон эзэлхүүнийг тооцоолох *
Функцийг алхамтайгаар тооцоолох. Торны арга*
Хөвөх таслалын арифметик**
Алдаа, тогтвортой байдал, нийлэлт**
Загварчлалын үндэс.
Загвар болон загварчлалын тухай ойлголт
Загварын үндсэн төрлүүд
Компьютерийн загварын бүрдэл хэсгүүд ба тэдгээрийг тодорхойлох аргууд: оролтын болон гаралтын хувьсагчид, төлвийн хувьсагчид, шилжилтийн болон гаралтын функцууд, хугацааны шилжилтийн функц
Компьютерийн загварыг байгуулах үндсэн үе шатууд болон онцлогууд
Практикийн бодлогыг бодоход компьютерийн загварчлалыг ашиглах үндсэн үе шатууд
Компьютерийн сүлжээний технологи
Сүлжээ
Сүлжээний карт ба сүлжээний төхөөрөмж
Өгөгдөл дамжуулах орчин
Сүлжээний архитектур
Нууц үг болон бусад хандалтын хяналтын механизмууд
Үйлчилгээний чанарын асуудал: хурд,гэмтлээс сэргэх хугацаа*
Утасгүй сүлжээ.
Утасгүй болон зөөврийн төхөөрөмжийн асуудлууд
Утасгүй болон зөөврийн төхөөрөмж дээр програм суулгах
Утасгүй дотоод сүлжээ ба холбооны шугам

CF #247. K-мод

к-мод гэж дараах нөхцлүүдийг хангах модыг нэрлэе:
- орой бүр к ширхэг хүүтэй байна
- ирмэг бүр тодорхой жинтэй байна
- орой бүрийн хувьд хүү оройтой нь холбосон ирмэгүүд 1, ..., к гэсэн жингүүдтэй байна
Доорх зурагт 3-модны хэсгийг үзүүлэв:

Дараах асуултын хариуг ол:
"к-модны үндэснээс эхэлсэн, дайрч өнгөрөх ирмэгүүдийн нийт жин нь n-тэй тэнцүү байх, d-гээс багагүй жинтэй ядаж нэг ирмэг агуулах замын тоо хэд байх вэ?"
Энэ тоо нь маш том байж болох тул түүнийг 1000000007 (10^9+7) тоонд хуваасны үлдэгдлийг олоорой.

Оролт
Ганц мөрөнд n, k болон d (1 ≤ n, k ≤ 100; 1 ≤ d ≤ k) тонууд өгөгдөнө.

Гаралт
Бодлогын хариуг 1000000007 (10^9+7) тоонд хуваасны үлдэгдлийг хэвлэнэ.

CF #247. В. Шүршүүр

Өглөө бүр дотуур байрны шүршүүрийн үүдэнд таван оюутан зогсч оочерлодог.
Шүршүүр нээгдэхэд эхний оюутан орно. Хэсэг хугацааны дараа оюутан гарахад дараагийнх нь орох гэх мэтээр дараалал дуустал үргэлжилнэ.
Дараалалд зогсох үедээ оюутнууд хоорондоо ярилцдаг. Гэхдээ дарааллын (2i-1)-р оюутан 2i-р оюутантай гэсэн зарчмаар хос хосоороо ярилцана.
Жишээ авч үзье. Оюутнуудыг 1-ээс 5 хүртэл тоогоор дугаарлая. Эхлээд оюутнууд 23154 гэсэн дарааллаар зогсч байсан гэе (2-р оюутан дарааллын эхэнд байгаа). Шүршүүр нээгдэх хүртэл 2, 3-р оюутнууд, 1, 5-р оюутнууд хоорондоо ярилцах ба 4 хэнтэй ч ярилцахгүй. Дараа нь 2 шүршүүрт орно. 2-ыг шүршүүрт байх хугацаанд 3, 1-р оюутнууд, 5, 4-р оюутнууд тус тус хоорондоо ярилцана. Дараа нь 3 шүршүүрт орно. 1, 5 хоёр хоорондоо ярилцах ба 4 хэнтэй ч ярилцахгүй. Дараа нь 1 шүршүүрт орсон хойгуур 5, 4 хоёр ярилцана. Дараа нь 5 орж, эцэст нь 4 орно.
Хэрэв i болон j оюутнууд ярилцаж байгаа бол i оюутан g[ij] хэмжээгээр баярлаж, j оюутан g[ji] хэмжээгээр баярладаг.
Тэгвэл оюутнуудын баяр баясгалангийн нийт хэмжээ хамгийн их байх тийм дарааллыг ол.
Зарим оюутнууд хэд хэдэн удаа хоорондоо ярьж болохыг анхаар. Жишээ нь 1, 5 хоёр шүршүүр онгойхоос өмнө болон 3-г шүршүүрт байх үед гээд хоёр удаа ярилцаж байгаа.

Оролт
Таван мөрөнд таван тоонууд өгөгдөх ба энэ нь g[ij](0 ≤ g[ij] ≤ 10^5) тоонууд юм. Бүх i-гийн хувьд g[ii]=0 байна.
Оюутнуудыг 1-ээс 5 хүртлэх тоонуудаар дугаарласан гэж үз.

Гаралт
Оюутнуудын нийт баяр баяслын хамгийн дээд хэмжээг илэрхийлэх ганц тоог гаргана.

Codeforces #247 A. Хар квадрат

Мэдрүүртэй утсан дээр Хар квадрат гэдэг тоглоом байдаг.
Дэлгэцэн дээр дөрвөн зурвас байна.
Секунд бүрт аль нэг зурвас дээр хар квадрат гарч ирдэг. i-р зурвас дээр гарч ирсэн квадрат дээр дарахад a[i] калори зарцуулагдаг.
Тоглолтын явцыг харуулах s тэмдэгт мөр болон зурвасуудын калорийг харуулсан a[1], a[2], a[3], a[4] тоонууд өгөгдсөн бол тоглолтонд зарцуулагдах нийт калорийг ол.

Оролт
Эхний мөрөнд калориудыг заах a1, a2, a3, a4 (0 ≤ a1, a2, a3, a4 ≤ 10^4) бүхэл тоонууд өгөгдөнө.
Хоёр дахь мөрөнд s (1 ≤ |s| ≤ 10^5) тэмдэгт мөр өгөгдөнө. Түүний тэмдэгт бүр нь тухайн секундэд аль зурвас дээр квадрат гарч ирснийг заана.

Гаралт
Зарцуулагдан нийт калорийг гаргана.

Луугийн муруй

Coder-Strike 2014 - Round 1: Problem C. Pattern

Шаблон гэж энэ бодлогон дээр жижиг англи үсгүүд болон ? тэмдгээс тогтсон тэмдэгт мөрийг хэлнэ.
? гэдэг нь ямар ч жижиг англи үсэг байж болно гэсэн үг.
Иймд нэг шаблоноос олон янзын тэмдэгт мөрүүд үүсч болно.
Хоёр шаблон огтлолцоно гэдэг нь тэр хоёроос үүсдэг тэмдэгт мөрүүдийн олонлог огтлолцож байна гэсэн үг.
Бидэнд ижил урттай n ширхэг шаблон өгөгдсөн.
Тэгвэл бүх шаблонтой огтлолцох шаблоныг ол. Энэ шаблон хамгийн цөөн тооны ? тэмдэгттэй байх ёстой.

Оролт

Эхнийн мөрөнд шаблоны тоо болох n (1 ≤ n ≤ 10^5) тоо өгөгдөнө.
Дараагийн мөрүүдэд ижил урттай шаблонууд өгөгдөнө. Шаблонуудын нийт урт нь 10^5 тооноос хэтрэхгүй.

Гаралт
Хайж буй шаблоныг гаргана

Coder-Strike 2014 - Round 1. Problem B. Network Configuration

Сүлжээний олимпиад явагдах гэж байгаа.
Ангид n компьютер байгаа.
Харин оролцогчийн тоо k.
Компьютеруудын сүлжээний хурд янз бүр.
Админууд компьютерийн сүлжээний хурдыг нь зөвхөн багасгаж чаддаг.
Харин оролцогчдын компьютер бүгд ижил сүлжээний хурдтай байх ёстой.
n компьютерийн сүлжээний хурд нь өгөгдсөн бол тэдгээрээс ядаж k ширхэг компьютерийн сүлжээний хурдыг нь ижилхэн T утгатай болгосон гэвэл Т-г олно уу. Т нь аль болох их байх ёстой.

Оролт

Эхний мөрөнд n, k тоонууд өгөгдөнө.
Дараагийн мөрөнд a[1], ..., a[n] гэсэн компьютеруудын сүлжээний хурдууд өгөгдөнө.

Гаралт
Т тоог хэвлэнэ.

RCC 2014 Warmup (Div. 2) Problem B: Crash

Онлайн тэмцээнд оролцогчид ижил бодолтуудаа дахин дахин илгээх нь их байдаг.

Оролцогч бүр өөрийн давтагдашгүй k гэсэн дугаартай байна. Илгээгдсэн бодолт А бүр дараах хоёр тоогоор илэрхийлэгдэнэ: х гэдэг нь А-тай ижил хамгийн эхний бодолтоос өмнө систем рүү илгээгдсэн А-гаас ялгаатай бодолтуудын тоо, k гэдэг нь бодолт илгээсэн оролцогчийн дугаар. Иймд яг ижилхэн бодолтуудын х нь ижил байна.
Онлайн системд бүх илгээгдсэн бодолтууд хугацаагаараа эрэмбэлэгдсэн байдаг. Өөрөөр хэлбэл ямар нэг k дугаартай оролцогчийн x (x>0) дугаартай бодолт системд байгаа бол энэ оролцогчийн x-1 дугаартай бодолт түүнээс өмнөх хаа нэг газар байгаа гэсэн үг.

Онлайн шалгах системийг алдааны дараа сэргээсэн. Шүүгчид илгээсэн бодолтуудыг гарган авсан боловч одоо тэд нар хугацааны зөв дарааллаараа байгаа эсэхийг мэдэхийг хүсч байгаа.

Оролт

Эхний мөрөнд бодолтуудын тоо болох n тоо өгөгдөнө. Дараагийн n тооны мөрөнд x, k тоонууд зайгаар тусгаарлагдан өгөгдөнө. Бүх тоонууд 10^5 - ээс хэтрэхгүй, тэгээс их бүхэл тоо байна.

Гаралт
Бодолтууд хугацааны зөв дараалалтай байгаа бол YES, үгүй бол NO гэсэн үгийг хэвлэнэ.

RCC 2014 Warmup (Div. 2) Problem A. Elimination

2214 оны КодКап дараах журмаар явагдана:
Үндсэн болон Нэмэлт үеүүд байна. Үндсэн үеээс эхний n оролцогч финалд шалгарах бол нэмэлт шатнаас эхний нэг л оролцогч финалд шалгарна.
Өмнөх жилүүдийн аварга болох k тооны оролцогчийг шууд финалд оруулна.
Финалд доод тал нь m*n тооны оролцогчийг оруулах ёстой. Хэрэв үндсэн шатанд c тооны бодлого, нэмэлт шатанд d тооны бодлого хэрэгтэй байдаг бол тэмцээн зохиогчид финалаас өмнөх шалгаруулалтуудад хамгийн багадаа нийт хэдэн бодлого зохиох хэрэгтэй вэ?

Оролт

Эхний мөрөнд c, d тоонууд,
Дараагийн мөрөнд n, m тоонууд,
Сүүлийн мөрөнд k тоо байрлана.

Гаралт

Бодлогын нийт тооны хамгийн бага утгыг гаргана.

Coder-Strike 2014 - Qualification Round: C. Kicker

Хоёр баг хоорондоо хөлбөмбөг тоглохоор шийдсэн.
Хоёр багийн нийт тоглогчдыг 1-4 хүртлэх тоогоор дугаарласан.
1, 2-р тоглогч нэгдүгээр багт, 3,4-р тоглогч хоёрдугаар багт тоглоно. i-р тоглогчийн хувьд түүний хамгаалах чадвар a[i] болон довтлох чадвар b[i] мэдэгдэж байгаа.
Тоглолтын өмнө багууд яаж тоглохоо шийддэг. Эхлээд нэгдүгээр баг хэнийг довтлогчоор, хэнийг хамгаалагчаар тоглуулахаа шийднэ. Үүний дараа хоёрдугаар баг нэгдүгээр багийн сонголт дээр үндэслэн өөрсдийн багтаа хэнийгээ довтлогчоор, хэнийгээ хамгаалагчаар тоглуулахаа шийднэ.
Багийн хамгаалалт гэж тэр багийн хамгаалагчийн хамгаалах чадварыг хэлнэ. Багийн довтлолт гэж тэр багийн довтлогчийн довтлох чадварыг хэлнэ. Хэрэв ямар нэг багийн хамгаалалт нь нөгөө багийн довтлолтоос эрс их ба довтлолт нь нөгөө багийнхаа хамгаалалтаас эрс их бол тэр баг нөгөө багаа хожно гэж үзнэ.
Хоёр баг бие биенээ сайн мэдэх тул багаа оновчтойгоор зохион байгуулна. Оновчтойгоор тоглоод хожих багийг тодорхойл. Эсвэл ийм баг байхгүй гэж гаргана.

Оролт

Дөрвөн мөрөнд дөрвөн тоглогчийн чадварууд болох a[i] (хамгаалах чадвар), b[i] (довтлох чадвар) тоонууд өгөгдөнө.

Гаралт

Хэрэв нэгдүгээр баг хожих бол "Team 1", хоёрдугаар баг хожих бол "Team 2" гэж хэвлэх ба аль ч баг нь хожих боломжгүй бол "Draw" гэж хэвлэнэ.

Coder-Strike 2014 - Qualification Round: B. Multi-core Processor

Олон цөмт процессор

Олон цөмт процессор нь n цөмтэй ба k үүр бүхий санах ойтой.
Цикл бүрт процессорын цөм бүр санах ойн аль нэг үүр рүү хандах эсвэл юу ч хийхгүй байх командыг биелүүлнэ.
Хэрэв нэг циклийн үед хэд хэдэн цөм нэг зэрэг санах ойн нэг үүр рүү хандвал түгжрэл үүсч, тэдгээр цөмүүд болон санах ойн үүр үүрд блоклогдоно.
Блоклогдсон цөмүүд цааш команд биелүүлэхээ болих ба блоклогдсон үүр рүү хандсан цөм өөрөө блоклогдоно.
m тактын дараа цөмүүд хэд дэх такт дээр блоклогдсон болон блоклогдоогүй байх тухай мэдээллийг ол.

Оролт

Эхний мөрөнд цөм, цикл болон санах ойн үүрийн тоо болох n, m, k тоонууд өгөгдөнө (1 ≤ n, m, k ≤ 100). Дараагийн n мөрөнд командууд өгөгдөнө. i-р мөрөнд m ширхэг бүхэл тоо x(i1), x(i2), ..., x(im) (0 ≤ x(ij) ≤ k) өгөгдөх ба x(ij) нь i-р цөм, j-р циклд хийх командыг илэрхийлнэ.  x(ij) нь тэг бол юу ч хийхгүй байх гэсэн команд байна. Хэрэв x(ij) нь 1-ээс k хүртлэх тоо байвал ийм дугаартай санах ойн үүр рүү ханд гэсэн команд байна.

Гаралт

n мөр гаргана. i-р мөрөнд i-р цөмийн блоклогдох циклийн дугаар t(i) тоог хэвлэнэ. Хэрэв цөм блоклогдохгүй үлдэх бол 0 тоог хэвлэнэ.

Asia-Pacific Informatics Olympiad 2014

Ази-Номхон далайн орнуудын Мэдээлэлзүйн олимпиад APIO 2014 тавдугаар сарын 3-4-нд ШУТИС-ийн МХТС дээр болно.

Зохион байгуулагчид: ММЗОЗБХ, ШУТИС КТМС, ШУТИС МХТС, Kazakh-British Technical University (http://kbtu.kz/)
Вэбсайт: http://olympiads.kz/apio2014/

Оролцох хүсэлтэй сурагчид 2004-04-19-ны дотор овог, нэр, мэйл хаяг, topcoder id (байгаа бол), codeforce id (байгаа бол) гэсэн мэдээллүүдээ khuder@csms.edu.mn хаягаар явуулна уу.

Facebook Hacker Cup 2013. Бодлого Альцгеймер

Альцгеймер
Та N ширхэг ачтай ба ач нартаа төрсөн өдрөөр нь настай нь тэнцүү тооны доллар өгдөг (шинэ төрсөн ач нартаа 0 доллар өгдөг).
Элли гэдэг нэг ач чинь төрсөн өдрөөр өгөх долларын шинэ схем бодож олсон: “Хэрэв дурын хоёр ач өөрсдийн авсан долларын хэмжээг харьцуулж үзвэл хоёулаа К тоонд хуваагддаг байна. К-гаас их бөгөөд хоёуланг нь хуваадаг бүхэл тоо олдохгүй”.
Ингэснээр ач бүр дор хаяж хуучин схемээр авч байсан доллараа авна.
0 гэдэг тоо бусад бүх тоондоо хуваагдана.
Та хөгшрөөд альцгеймерийн өвчтэй болсон тул эдгээрийг тооцоолох програм ашиглахаар шийдсэн.
Оролт
Эхний мөрөнд тестийн тоо болох Т бүхэл тоо байрлана.
Тест бүрийн эхний мөрөнд N болон K тоонууд байрлана.
Дараагийн мөрөнд ач нарын чинь насууд болох N бүхэл тоо байрлана: A1, A2, ..., AN.
Гаралт
i – р тест бүрийн хувьд “Case #i: “ гээд настай нь тэнцүү мөнгө өгч байсан дээр хамгийн багадаа ямар хэмжээний мөнгө нэмж болохыг харуулсан бүхэл тоог гаргана.
Хязгаарлалтууд
1 ≤ T ≤ 20
2 ≤ N ≤ 20
1 ≤ K ≤ 20
0 ≤ Ai ≤ 50
Жишээ
Эхний жишээн дээр та хэн нэгэнд 2-ыг өгөөд нөгөөд нь 3-ыг өгнө. Нийт 5 болно. Хуучин схемээр бол хоёулаа 2-ыг аваад нийт 4 болох байсан. Хариу нь 5-4=1 юм. Та хоёуланд нь 2-ыг өгч чадахгүй ба учир нь тэр хоёрын мөнгө хоёулаа 1-ээс гадна 2-т хуваагдах болно.
Хоёр дахь жишээн дээр нэг боломжит шийд нь 3, 7, 5, 16-г өгөх ба нийт 31 болно. Хуучин схемээр бол 28-ыг өгөх байсан тул хариу нь 31-28=3.
Гурав дахь жишээн дээр бүх мөнгө 3-т хуваагдаж байх ёстой. Нэг боломжит шийд нь 6, 21, 51 юм. Энэ нь тэдний насны нийлбэрээс 6-гаар их юм. 6, 18, 51 нь гуравт хуваагдах боловч 6, 18 хоёр нь 6-д ч бас хуваагдах тул энэ нь зөв шийд биш юм.
5
2 1
2 2
4 1
2 7 5 14
3 3
5 18 49
3 1
1 2 3
4 2
0 0 1 2
Case #1: 1
Case #2: 3
Case #3: 6
Case #4: 0
Case #5: 3

Facebook Hacker Cup 2013. Бодлого АААААА

AAAAAA
Элийн тоглоомын газрыг AAAAAA гэдэг ба хүмүүс маш ихээр ирдэг.
Үйлчлүүлэгчид машины зогсоол дээр урт дараалал үүсгэн зогсдог. Эл аль болох олон хүнийг зогсоол дээрээ багтаахыг хүсч байгаа. Харин хүмүүс хэтэрхий их мушгиралдсан дараалалд зогсохыг хүсдэггүй.
Зогсоолыг тэгш өнцөгт хэлбэртэй бөгөөд нүднүүдээс тогтоно гэж үзэж болно. Орох хаалга нь зүүн дээд талын буланд байрлана. Бүх дараалал эндээс эхэлнэ. Зогсоол дээр машинууд байж болох ба тэдгээрийг ‘#’ тэмдгээр тэмдэглэнэ. Үйлчлүүлэгчид машин дээр гарч чадахгүй. Бусад нүднүүдэд ‘.’ тэмдэгт байрлана. Хэрэглэгчдийн хүсэлтээр дараалал үргэлж доош болон баруун чиглэлд үргэлжилнэ. Мөн хэрэглэгчид нь нэг буулт хийсэн нь нэг дараалалд ганц ширхэг, үргэлжилсэн дээш чиглэсэн хэсэг эсвэл ганц ширхэг зүүн тийш чиглэсэн үргэлжилсэн хэсгийн аль нэг нь байж болно гэсэн нөхцөл юм. Энэ хоёр үргэлжилсэн хэсэг нэг дараалалд хоёулаа байж болохгүй.
Дараалал нь эдгээр дөрвөн чиглэлд л үргэлжилнэ. Диагоналиар явахгүй.
Сул зай бүрт ганц л үйлчлүүлэгч багтах ба дараалсан хоёр үйлчлүүлэгч хоорондоо хөрш нүднүүдэд байрлана. Дараалсан хоёр үйлчлүүлэгч хоорондоо зайтай, тасарсан байж болохгүй.
Оролт
Эхний мөрөнд тестийн тоо болох Т бүхэл тоо байрлана.
Тест бүрийн эхний мөрөнд тэгш өнцөгтийн мөр болон баганын тоог илэрхийлэх N, M бүхэл тоонууд өгөгдөнө.
Дараагийн N ширхэг мөрөнд яг M ширхэг тэмдэгт бүхий тэмдэгт мөр байрлана.
Гаралт
i-р тест бүрийн хувьд зүүн дээд өнцгөөс эхлэн байрлуулж болох хамгийн урт дарааллын хэмжээг “Case #i: “ гэсний дараа гаргана.
Хязгаарлалт
1<=T<=20 1<=N, M<=500 Тэгш өнцөгт дэх тэмдэгтүүд ‘#’ эсвэл ‘.’ байна. Зүүн дээд булангийн тэмдэгт дандаа ‘.’ байна.

Жишээ оролт
5
5 5
.....
.....
.....
.....
.....
1 10
..........
5 5
...#.
...#.
...#.
...#.
.....
3 3
..#
#.#
...
3 8
........
#.#.#.#.
#.#.#.#.
Жишээ гаралт
Case #1: 17
Case #2: 10
Case #3: 17
Case #4: 5
Case #5: 10

ACM ICPC, Баруун Өмнөд Европын Мужийн Олимпиад, Бодлого I

Чухал сэдэв

Бодолт илгээх

ACM ICPC, Баруун Өмнөд Европын Мужийн Олимпиад, Бодлого С

Худалдааны төв

Бодолт илгээх