Intermediate “Hello World!”

ACM ICPC Regional Dalian 2011

2011-09-30T10:30:00.000+08:00

9 сарын 23-25ны хооронд БНХАУ-н Далиан хотноо ACM ICPC бүсийн тэмцээн амжилттай болж өнгөрлөө. Уг тэмцээнд Хонгор, Мөнх-Очир, Баасанбат нарын бүрэлдэхүүнтэй S.M.C.S баг Монгол улсаа (блогоо :P) төлөөлөн оролцоод ирлээ. Манай баг 2009 онд Монгол улсын анхны хүрэл медал, 2010 онд амжилтаа бататган дахин хүрэл медал хүртээд байсан билээ.

9.23:

Бид Бээжин хотоос 12 цаг галт тэргээр явсаар 9.23-ны өглөө Далиан хотод ирлээ. Ингээд тэндээсээ шууд бүртгэлдээ очиж тэмцээний билэгдэл болох футболкоо авцгаалаа. Уг өдрөө тэр хавиараа жаахан танилцсан байдалтай л өнгөрүүллээ.

9.24:

Энэ өдөр бол дасгал тэмцээний өдөр. Дасгал тэмцээний гол зорилго нь систем болон компьютер, эдитор гэх зүйлүүдтэйгээ танилцах зорилготой өдөр юм. Гэхдээ уг өдөр сайн орвол сэтгэл зүйн хувьд дээшлэх байх гэж бодож байлаа. Гэтэл санаснаас хамаагүй тааруу орлоо :(.

9.25:

Жинхэнэ тэмцээний өдөр. Өмнөх дасгал дээр сайн ороогүй учир жаахан эмээж байсан. За тэмцээн эхэллээ.
A-J хүртэл дугаарлагдсан 10 бодлого. Олон бодлогоо хувааж аваад уншиж байх хооронд эхний баг D бодлого дээр AC авлаа. Хамт уншихад үнэхээр хялбархан simulation төрлийн бодлого байсан. Кодоо бичээд submit хийлээ, хариу ирээгүй байхад буруу гэдгээ шууд мэдэв - freopen :). Тэнэг froepen-оо хаагаад явуултал мэдээж AC кк.
Дараагийн бодлогоо хайж байтал E бодлогыг бас л өөр баг AC авчихлаа. Жаахан бодсоны эцэст DP бодолтыг олов. Бичээд явуултал AC. Board хартал 16 хавьцаа явж байна, бөөн баяр .....
Хялбар бодлого хайж нэлээд л удлаа. Гэтэл I бодлогыг E-с ч олон хүн бодсон байх юм. Нэг л барьцгүй эвгүй бодлого байв. Тэгээд G бодлогыг уншихад болмоор санагдаад нэлээд хурдан санаа олохыг оролдсон, эцэст нь санаагаа ч оллоо. Гэхдээ бодлогууд хугацааны хязгаарлалтууд тодорхойгүй болохоор TLE авахаас айж байсан ч бичихээр шийдээд бичлээ. Жишээ тестүүдийг давж байна, өөрсдөө үүсгэсэн tricky тестүүдийг ч давж байна. Submit хийлээ, AC :).
Бодлого хайсаар, I дээр гацсаар. Гэтэл C бодлогыг 2 баг бодсон мөртлөө болмоор санагдаад бодоод бичлээ. Нэлээд удсаны эцэст submit хийхэд WA, бид нэг л юм орхиод байгаа бололтой.
Сүүлийн 1 цаг эхэллээ, 2 цаг зүгээр суучихлаа, байдал эвгүй болж эхэлж байна ккк. Одоо манай эцсийн боломж I гэдгийг мэдэж байсан. I бодлогыг бодоход манайд хэрэгтэй байсан ганц зүйл нь 1^4+2^4+..+n^4 -г O(1)-д олдог томъёо. квадрат зэрэг, куб зэргийг мэдэж байсан ч 4 зэргийг мэддэггүй шүү. Томъёог нь гаргах гэж үзээд ч чадсангүй. n<=10^8 байсан болохоор нэг удаа precomputation хийчихвэл O(1)-д олж чадна. Гэхдээ л memory-д багтсангүй, TLE ч авлаа. 8 минут үлджээ, эцсийн эцсийн эцсийн арга гээд үзлээ. 1..10^8 хүртэл бүх утга биш харин 0-р төгссөн тоонуудыг нь хадгалчихвал ямар ч тоог ихдээ O(10) үйлдэл хийгээд олж чадна. Энэ бодолтоо Submit хийгээд 295 дахь минутанд AC. Хэзээ ч бодлого бодоод ингэж их баярлаж байсангүй кк. Дүнгийн хурал:Манайх мөнгө эсвэл хүрэл медал авах нь ойлгомжтой байсан. Хүрэл медалуудыг дуудсаар, манайх дуудагдсангүй :). Мөнгөн медал дээр S.M.C.S багийг дуудлаа. Ингээд анхны мөнгөн медалыг МУИС-МКС-н S.M.C.S баг хүртлээ.

Тэмцээн - 1

2011-09-09T23:41:00.005+08:00

Юуны өмнө тэмцээнд оролцсон хүмүүст баярлалаа. Бас эхний байруудад орсон idiot, tvvv, Adya 3т баяр хүргэе.
Одооноос кодер дээрх тэмцээнүүдийг Тэмцээн тэд гэж нэрлэнээ. хэхэ, гадны сайтуудыг л дагаж байнадаа. Тэмцээний цагийг бас иймэрхүү орой хийвэл яаж байна саналаа үлдээгэрэй. Бодлогуудын хувьд бас л гадны сайтуудаас бодсон бодлогуудаас ишлэж зохиосон, тэстүүдэд бас их цаг гаргаж TRICKY тэстүүд их оруулсан. Ингээд бодлогын анализ хийе.
Эргэлт
Энэ хамгийн амархан бодлого байсан байх. Мөрийн дагуу хэд эргэх баганы дагуу хэд эргэхийг бодож үзсэн бол хариу: min(n*2-2, m*2-1)
35
Мэдээж цөөн сав хэрэглэхийн тулд аль болох 5-н сав ашиглах хэрэгтэй. Хэрэв N тоо 5-д хуваагдахгүй бол ядаж нэг удаа 3-н сав ашиглаж ёстой.
Бага тоо
Шууд хүчээр тоог 1-ээр ихэсгээд бодлогын шаардлагыг хангах тоог гаргаж авж болно. Хэрэв саяас илүү удаа 1-ээр нэмэгдүүлэх үйлдэл хийсэн бол шийдгүй юм. Өөр нэгэн бодолт өгөгдсөн тоон оронгийн тоонуудыг бүх боломжоор сэлгэж бодлогын хариуг гаргаж болно. N<=999999 учир бид хамгийн ихдээ 6! үйлдэл хийгдэх юм.

Тэгш өнцөгт

Энэ бодлогын өгүүлбэрийг их буруу бичсэнүү, хүмүүс ойлгох гэж цагаа их алдсан байх. Энэ бодлого нь codeforces.com дээр бүх боломжийг шалгахаар бодож болохоор өгөгдсөн ба та эндээс харж болно. Харин би хязгаарлалтыг сая болгож бүх боломжийг шалгах боломжгүй болгосон юм. Миний бодолт бол динамик програмчлал ашиглах ба left[i]-ээр тухайн i-р тэгш өнцөгтийн зүүн талд орших түүнтэй хөрш бөгөөд дараалсан мөн өөрөөс нь бага буюу тэнцүү урттай тэгш өнцөгтийн тоог тэмдэглэнэ. Үүнтэй адилаар right[i]-ээр i-аар хайрцагны баруун талд орших түүнтэй хөрш бөгөөд дараалсан мөн өөрөөс нь бага буюу тэнцүү өндөртэй тэгш өнцөгтүүдийн тоог тэмдэглэв. Тэгвэл хариу max(left[i]+right[i]) (i=1..n). Бодолт O(N)

Тэгийн тоо

Факториалын сүүлийн 0-үүдийн тоог яаж олдог хүмүүс бол бодох л байсан бодлого. Бодлогын хариунд тооцогдож болох үржвэрийн тэгүүдийн тоо нь min(fac2, fac5) юм. Энд fac2, fac5 нь 2 болон 5ууд тус бүр хэдэн удаа үржвэрт байгааг илэрхийлнэ. Энэ нь бидэнд бодлогыхоо хариуг гаргаж авахад заавал бүх тоог үржүүлэхээс зайлсхийх боломжийг олгох юм. Одоо бодлогоо динамик програмчлал ашиглан хоёр өөр маршрут гаргаж авна. Нэг нь үржвэрт хамгийн бага 2 орсон, нөгөө нь мэдээж хамгийн бага 5 орсон. Тэгвэл хариу нь уг 2 маршрутын бага нь болно. Бодолтыг O(N^2)-аар шийднэ.

Mario on Box
Энэ бодлогыг одоохондоо бичихгүйгээр шийдлээ.

Модтой тоглоё 6

2011-06-20T11:34:00.003+08:00

IOI2010-n 2dahi odoriin Traffic Congestion bodlogiig bodloo. tgj bgad nemelt tailbar hiinee. Source-g ni tavichii.

//Task: IOI2010_2_2
//by Dunno
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;
static int N,P[1000000],S[1000000],D[1000000];
int n;
vector<int> v[1000000];
int prev[1000000];
int col[1000000];
int sum;
int *p;

int go(int x) {
    int ans = p[x];
    int m = 0;
    for (int i = 0; i < (int) v[x].size(); i++) {
       int u = v[x][i];
       if (u == prev[x])
          continue;
       prev[u] = x;
       int tmp = go(u);
       m = max(m, tmp);
       ans += tmp;
    }
    m = max(m, sum - ans);
    col[x] = m;
return ans;
}

int LocateCentre(int n, int *p, int *s, int *d) {
    ::n = n;
    ::p = p;
    sum = accumulate(p, p + n, 0); 
    for(int i=0; i<n; i++){
       v[s[i]].push_back(d[i]);
       v[d[i]].push_back(s[i]);
    }

    prev[0] = -1;
    go(0);
    int id = 0;
    int best = col[0];
    for (int i = 1; i < n; i++) {
        if (col[i] < best) {
        best = col[i];
        id = i;
        }
    }

return id;
}
int main(){
   int i;
   freopen("grader.in","r",stdin);
   freopen("grader.out","w",stdout);
   scanf("%d",&N);
   for (i=0;i<N;i++) scanf("%d",&P[i]);
   for (i=0;i<N-1;i++) scanf("%d%d",&S[i],&D[i]);
   int r = LocateCentre(N,P,S,D);
   printf("%d\n",r);
   return 0;
}

let me know about errors, if any

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

2011-04-28T14:06:00.000+08:00

2-р өдрийн 1-р бодлого.

Гурвалжинг судлая

Хугацааны хязгаарлалт: 2 сек

Координатын эх О-цэгийн баруун талд (эерэг талд) ОХ-тэнхлэг дээр бүхэл координаттай С цэг тэмдэглэв. Ингэхэд О цэгээс с-зайтай, С-цэгээс а-зайтай эерэг хагас (ОХ-тэнхлэгээс дээш) хавтгайд орших цор ганц В-цэг олдоно. Үүний дараа та дараах 2 даалгаварыг гүйцэтгэ.

1-рт нь:
ОВ-хэрчим дээр С1, С2, ... , Ск гэсэн ялгаатай цэгүүдийг ОС1, ОС2, ... , ОСк хэрчмүүдийн урт бүхэл тоо байхаар тэмдэглэв. Дараа нь мөн ОС-хэрчим дээр В1, В2, ... , Вm гэсэн ялгаатай цэгүүдийг OB1, OB2, ... , OBm хэрчмүүдийн урт бүхэл тоо байхаар тэмдэглэв. Эцэст нь BC хэрчим дээр A1, A2, ... , An гэсэн ялгаатай цэгүүдийг BA1, BA2, ... , BAn хэрчмүүдийн урт бүхэл тоо байхаар тэмдэглэв.

1-р даалгавар:
CCi, OAj, BBt хэрчмүүд нэг цэгт огтлолцдог байх бүх (i,j,t) гурвалуудыг ол. (1 <= i <= k, 1 <= j <= n, 1 <= t <= m)

2-рт нь:
1-р даалгавраа гүйцэтгэсний дараа, О-цэгээс зүүн талд (сөрөг талд) ОХ-тэнхлэг дээр D1, D2, ... , Dp гэсэн ялгаатай цэгүүдийг OD1, OD2, ... , ODp хэрчмийн урт бүхэл байхаар авав.

2-р даалгавар:
Ci, Aj, Dt цэгүүд нэг шулуун дээр оршдог байх бүх (i,j,t) гурвалуудыг ол. (1 <= i <= k, 1 <= j <= n, 1 <= t <= p)

Оролт (tr.in)
Оролтын файл 10 мөрөөс тогтоно.
Эхний мөрөнд С цэгийн координат болох "b" гэсэн 10000-аас хэтрэхгүй натурал тоо байна.
2-р мөрөнд B-цэгийг олоход хэрэглэх "c" ба "a" гэсэн 2 натурал тоо хоосон зайгаар тусгаарлагдан өгөгдөнө.
Эдгээр тоонууд мөн 10000-аас хэтрэхгүй. (2 < a,b,c <= 10000)
3-р мөрөнд k-гэсэн натурал тоо байна. (k <= 150)
Дараагийн мөрөнд OC1, OC2, ... , OCk хэрчмүүдийн уртыг илэрхийлэх c1, c2, ... , ck гэсэн ялгаатай натурал тоонууд хоосон зайгаар тусгаарлагдан байрлана. (ci < c, i=1..k)
5-р мөрөнд m гэсэн натурал тоо байна. (m <= 150)
Дараагийн мөрөнд OB1, OB2, ... , OBm хэрчмүүдийн уртыг илэрхийлэх b1, b2, ... , bm гэсэн ялгаатай натурал тоонууд хоосон зайгаар тусгаарлагдан байрлана. (bi < b, i=1..m)
7-р мөрөнд n гэсэн натурал тоо байна. (n <= 150)
Дараагийн мөрөнд BA1, BA2, ... , BAn хэрчмүүдийн уртыг илэрхийлэх a1, a2, ... , an гэсэн ялгаатай натурал тоонууд хоосон зайгаар тусгаарлагдан байрлана. (ai < a, i=1..n)
9-р мөрөнд p-гэсэн натурал тоо байна. (p <= 150)
Эцсийн мөрөнд OD1, OD2, ... , ODp хэрчмүүдийн уртыг илэрхийлэх d1, d2, ... , dp гэсэн 10000-аас хэтрэхгүй ялгаатай натурал тоонууд хоосон зайгаар тусгаарлагдан байрлана.

Гаралт (tr.out)
Мөр бүрт 1-р даалгаврын хариу болох (i, j, t) гурвалуудыг илэрхийлэх i, j, t гэсэн 3 тоо хоосон зайгаар тусгаарлагдан байрлана. Тус гурвалуудыг хэвлэхдээ i-гийн координатаар өсөхөөр эрэмбэлж гаргана, хэрэв i-нь тэнцүү бол i-координатаар нь өсөхөөр эрэмбэлж гаргана. Жишээ нь: (1,3,2) (2,2,3) (2,3,1) гэсэн дарааллаар хэвлэнэ.
1-р даалгаврын бүх хариуг хэвлэж дууссаны дараа "PART 2" гэсэн тэмдэгт мөр хэвлэнэ. (1-р даалгавар нэг ч хариугүй байсан ч PART 2 гэж хэвлэнэ)
Үүний араас мөр бүрт 2-р даалгаварын хариу болох (i,j,t) гурвалуудыг илэрхийлэх i,j,t гэсэн 3 тоо хоосон зайгаар тусгаарлагдан байрлана. Тус гурвалуудаа хэвлэх дараалал нь өмнөхтэй адил байна.

Жишээ оролт

Жишээ гаралт

2 2 3
PART 2

Тайлбар
CC2 = 5, OA2 = 6, BB3 = 4 хэрчмүүд нэг цэгт огтлолцох тул 2 2 3 гэж гаргана.
Ci, Aj, Dt цэгүүд дунд нэг шулуун дээр орших гурвал олдохгүй байна.

Улсын програмчлалын 21-р олимпиадын дүн

2011-04-26T08:32:00.003+08:00

Өнгөрсөн амралтын өдрүүдээр буюу 4 сарын 23-24 өдрүүдэд Улсын Програмчлалын 21-р олимпиад КТМС дээр зохиогдож дүнгээ гаргалаа. Ингээд нийлбэр дүнгээр

1. Өсөхбаатар МУИС-МТС - 240
2. Хонгор МУИС-МКС - 210
3. Мөнх-Очир МУИС-МКС - 200
4. Чинбат КТМС - 195
5. Амар КТМС - 185
6. Амгаланбаатар КТМС - 185

Багийн дүнгээр МУИС-МТС 1-р баг түрүүлж шилжин явах цомын эзэд боллоо. Амжилттай оролцсон хүмүүстээ баяр хүргэе!

Програмчлалын Улсын 21-р олимпиадын алдаа

2011-04-25T10:16:00.002+08:00

Энэ удаад олимпиадын дүнг танилцуулахаас өмнө алдаануудыг бичихээр шийдлээ.

Эхний өдөр:
Ороод суухад лабораторын компьютерийн бэлтгэл ажил муу байсан. Жишээлбэл анх ороод суухад Deep Freeze програмыг унтраагаагүй байсан, үүнийг мэдэж байсан туршлагатай оюутнууд л хаалгасан. Эндээс үүдэж гарсан хамгийн муу үр дүн нь Дархан хотоос зорьж ирсэн Мөнхбаатарын эхний өдрийн бүх Source устсан. Бид бодолтоо тулгасан ба Мөнхбаатар дор хаяж 130 оноо авах байсан. Энэ бол КтМС-н цэвэр хариуцлагагүй байдал.
Ингээд эхний өдрийн дүн гарахад миний оноо 145 байсан ба 150 авна гэдэгтээ маш итгэлтэй байсан. Өргөдөл бичиж ороод би өөрөө тестийн алдааг олж илрүүлээд комисс хүлээн зөвшөөрч 4 хүүхэд 5 оноо нэмж авсан. Ороогүй байсан бол тэмцээний дүнд том өөрчлөлт орох байсан.

Хоёр дах өдөр:
Мөнхбаатарын бодолтыг сэргээж чадсангүй, ингээд тэдний хариуцлагагүй байдлаас болж бүхэл бүтэн 130 оноо алдаж байр эзлэх ямар ч найдваргүй болсон. Дүн гарлаа, уг нь дор хаяж 100 оноо авна гэсэн итгэлтэй байсан би 40 15 5 оноо авсан байв. 40 оноог бол би хүлээн зөвшөөрнө, 15-г ойлгож болно, 5 оноог огт ойлгосонгүй. Тэд өргөдөл хүлээн авах боломж өгөлгүй хүчээр бүх өргөмжлөлүүдийг бэлдээд бараг хүчээр дүнгийн хурал эхлүүлэв. 15 оноо авсан бодлого тест хэтэрхий сул байснаас Brute Force буюу хамгийн арга барсан аргаар бодсон хүмүүс 50 авч гайхал төрүүлэв.

Тэмцээний дараа Мөнх-Очир бид 2 миний 5 авсан буюу "tr" бодлогын бодолтыг зөв гэдэгт итгэлтэй байсан тул тестүүдийг аваад шалгаж үзтэл ихэнх тест бодлогын нөхцлийг хангаагүй буюу Гурвалжны тэнцэтгэл биш хангахааргүй өгөгдсөн байв. Мэдээж гурвалжин үүсэхгүй бол ямар хариу хэвлэх вэ дээ? Гэтэл зохиогч болон Өсөхбаатар-н бодолтууд хаанаас ч юм хариу олж хэвлээд тэдгээр нь таарсан. Би гурвалжны тэнцэтгэл биш нөхцлийг хангахгүй бол юу ч хэвлэхгүй гэдгийг кодондоо бичсэн. Энэ бодлогоны тест буруу байсан нь хамгийн том алдаа, хэрвээ энэ алдаа байгаагүй бол Би 1-рт байрт орж багаараа дахин цом хүртэх байлаа. Тэд өргөдөл хүлээж авах ёстой байсан, хэрэв хүлээж авсан бол би тэр алдааг дорхноо илрүүлж бүгдийг өөрчлөх байсан.

Бүх юм дууссан болохоор дараа жилийнхдээ л сайн бэлдэе дээ :)

Гэхдээ бид ижилхэн л оролцогчид учраас Өсөхбаатарт баяр хүргэе!

MNPC 2011 - SMCS багийн тэмдэглэл

2011-04-13T13:22:00.007+08:00

Би (SMCS - Э.Хонгор) энд багийнхаа MNPC 2011-т хэрхэн оролцсон тухай бичихээр шийдлээ. Юуны өмнө MNPC 2011 нь Мөнх-Очир бид хоёрын хувьд оролцох боломжтой сүүлийн жил байсан болохоор амжилттай оролцохыг хүсч байсан ба санасандаа хүртэл оролцсондоо таатай байна. Мөн багийн уламжлал ёсоор дахин нэг гишүүн маань солигдсон билээ :p. Багийн шинэ гишүүн маань уг блог-н идэвхтэй админ болох Баасанбат юм. Тэмцээний үеэр олон бодлого байсан болохоор хэн яг ямар бодлого оролдож уншсаныг мартчихаж, багийн ажиллагаа байсан гэж ойлгоорой :).

За ингээд тэмцээнээ эхэлье :). Тэмцээн эхлэв 10 бодлого ирлээ. Бодлогыг хувааж аваад уншив аа, тэгтэл J бодлого N тооны эрэмбээрээ голын тоог ол гэнэ. Шууд STL-н sort ашиглаж бичээд явуултал TLE. N<=10^6 бас multicase 10 ширхэг байсан болохоор амжсангүй. Ингээд шууд хаяад A бодлогыг хартал өгөгдсөн тоонуудын нийлбэрийг ол гэнэ. Ингээд явуулаад 6 дахь минутанд AC. Тэгтэл манайхаас өмнө 2 баг AC авсан байв, J-г хэрэггүй оролдлоо :p. C бодлого N-с хэтрэхгүй хуваарьтай бүх зөв энгийн бутархайг эрэмбэлж гаргах бодлого байв, N жижигхэн байсан болохоор шууд бичээд AC (11 минут). Ингээд тэмцээний дүнг хартал маш бага хугацааны зөрүүгээр нэгт орлоо. Амархан бодлого олохын тулд бүх бодлогыг уншиж их цаг авав, тэгээд I бодлогыг уншиж дуусахад жаахан нуугдмал Bipartite Matching байсныг олоод шууд бичээд AC (41 минут). Дүнгээ хартал бас л тэнцчихсэн, хугацаагаараа арай бага болохоор 1т. Board-с ажиглаад B бодлого хялбар байж магадгүй санагдаад B-г Мөнх-Очиртой цуг жаахан бодсоны эцэст шууд томъёог олоод AC авав (64 минут). Дараагийн бодлого - F, уг бодлого өгүүлбэрээ ойлгосны дараа жижигсэн DP байсныг олов, бичиж байх зуураа дүн хартал дахиад л тэнцчихлээ, MTC-н 1-р багтай үнэхээр ширүүн өрсөлдөж байна даа, ингээд F-ээ дуусгаад AC(75 минут). Ингээд 5 бодлоготой болоод 1 оноогоор холдсон ч удалгүй өрсөлдөгч баг маань 5 бодлоготой болж тэнцэв. Бодлогуудаа уншсаар л, амархан бодогдчих бодлого олдолгүй удав. E бодлого MIS 2D(Maximum Interval Sum) -г олох бодлого, Мөнх-Очиртой хамтраад бичиж байтал арай жаахан удаж магадгүй санагдаад дуусгалгүй өөр бодлого харав. Тэгээд Баасанбатын уншиж байсан H-г DP + BFS гэдгийг харлаа. Маш урт өгүүлбэртэй бодлого байсан болохоор Баска-н тусламжтай хурдан ойлгоод бичив. Bug гарсан болохоор гурвуулаа нийлж тестлэж засаад явуулав. Алдаж магадгүй гэсэн айдастай байсан ч AC авлаа (154 минут). Яг энэ үед манайх 7 оноотой өрсөлдөгч 5 оноотой байсан болохоор жаахан тайвширлаа. Юмаа идэх нь идээд усаа уух нь уугаад бие засах нь заслаа. Ороод иртэл нөгөө баг 6 болчихжээ, яарахгүй бол болохгүй нь. Одоо бодох дутуу гурван бодлого нь D, G, J. J бодлогыг яг баталгаатай бодох арга олоогүй ч эцсийн арга гээд нэг арга олчихсон. D бодлогыг анх хараад ямар ч санаа олсонгүй. Brute Force бичээд жижиг тохиолдлоос зүй тогтлыг олов. Гурвуулаа нийлж байгаад томъёо гаргаад явуултал WA. Итгэлгүй байсан болохоор орхив. Тэмцээний дүнд өөрчлөлт ороогүй байсан болохоор өрсөлдөгч баг манайхыг ялахын тулд дор хаяж 2 бодлого нэмж бодох ёстой ба цаг бага үлдсэн байсан болохоор тайван байлаа, гэхдээ хамаагүй тайвширч болохгүйгээ мэдэж байсан болохоор J-г эцсийн аргаараа үзээд AC авав (228 минут). Одоо л тайвширч болохоор боллоо, гэхдээ D-г эцсээ хүртэл оролдсоор байв. Ингээд манай баг дахин түрүүлж хошой аварга боллоо. Бодлогын анализ дээр зохиогч D-н бодолтоо тайлбарлатал томъёо нь яг таарж байсан ба бодолтоо тулгатал маш жижигхэн алдаа байсан ба манай бодолт зөв болж rejudge хийхэд AC авав (208 минут). Ингээд 9 оноотой гэсэн үг, гэхдээ бусад багуудын аль нь ч бодож чадаагүй болохоор ялгаагүй гэж үзээд манай баг 8 оноотой үлдэхээр шийдсэн.

Бодлого Оролдлого Минут
A 1 6
C 1 11
I 1 41
B 1 64
F 1 75
H 1 154
E 1 170
D 1 203
J 6 228

Багийнхандаа баяр хүргэе!

P.S: Удахгүй бүх бодлогын өгүүлбэрийг оруулах болно.

Монголын Үндэсний Програмчлалын III Олимпиад

2011-04-13T12:04:00.001+08:00

Монголын их дээд сургуулуудын оюутнуудын багуудын хооронд зохион байгуулагддаг Үндэсний Програмчлалын олимпиад 4.9-нд гурав дахь удаагаа амжилттай болж өндөрлөлөө. Тэмцээний дүнгээс дурдвал

1. МУИС - МКС 1-р баг - 8 оноо
Бүрэлдэхүүн : Хонгор, Мөнх-Очир, Баасанбат
2. МУИС - МТС 1-р баг - 6 оноо
Бүрэлдэхүүн : Өсөхбаатар, Жамсрандорж, Мөнхжаргал
3. МУИС - МТС 2-р баг - 6 оноо
Бүрэлдэхүүн : Хуягбаатар, Чинболд, Дөлгөөн
4. ШУТИС - КТМС 1-р баг - 4 оноо
Бүрэлдэхүүн : Амар, Адъяа, Гансүх
5. МУИС - МКС 2-р баг - 4 оноо
Бүрэлдэхүүн : Ганбат, Гончигдорж, Дөлгөөн
6. ШУТИС - КТМС 2-р баг - 4 оноо
Бүрэлдэхүүн : Баярмагнай, Чинбат, ?

Чигчийхэн ба Чимэд ах

2011-02-24T23:17:00.000+07:00

Тавил:
Online-Judge системд оролтын өгөгдлүүд тэст бүр дээр ижилхэн 1 байхад, гаралтын өгөгдлүүдийг тэст бүр дээр ялгаатай буюу 1-ээс N (тэстүүдийн тоо, N < 9) хүртэлх тоонууд байхаар хэвлэ.

Бодолтын санаа:
Шууд тэст дуудах болгонд random-ээр 1-ээс N хүртэлх тоог үүсгээд хэвлэнэ гэвэл 1/2^N хэмжээний магадлалтай болно. Энэ бол боломжгүй шахуу зүйл юм. Иймээс өөр арга олох хэрэгтэй.

Тэст дуудагдах болгонд буюу програм ажиллах болгон өөрчлөгддөг хэдэн зүйл бий. Тэдгээрийн нэг нь цаг хугацаа буюу unixtime. Үүнийг ашиглан бодож болно.
Online-Judge системд i-р тэстийг давсан тохиолдолд i+1 дэхь тэстийг програмд уншуулдаг. Мөн i-р тэстийг шалгаад дууссан бол бараг л шууд i+1 дэхь тэстийг уншуулж эхэлдэг. За энэ хооронд үүсэх хугацааны алдагдлыг хамгийн ихээр бодоход 0.5 секунд гэж үзье. (coder.mn дээр 0.2 секунд байл уу даа?)
1-р тэстийг unixtime-н секундээр T1=X*10+1 дэхь секундэд ажиллуулна гэж үзье. Тэгвэл програм маань гаралтын утгыг (T1 % 10) гэж хэвлэчихээд хугацааг T2=X*10+2 секунд болтол өөр дээрээ delay ажиллуулна. T2=X*10+2 секунд өнгөрөнгүүт програм зогсож, online judge маань дараагийн тэстийг програм руу оруулна. Энэ удаад T2 хугацаа маань хамгийн ихээр бодоход (T2 + 0.5) болж өөрчлөгдөнө. Програм энэ удаад (T2 % 10) гэсэн утгыг хэвлэчихээд дахиад хугацааг T3=X*10+3 секунд болтол delay ажиллуулна. Гэхмэтчилэн хэвлэсээр байгаад бүх тэстийг дуусгана.

Энэ маягаар бодоход шууд нэг удаа бодлогыг илгээгээд ажиллуулах магадлал бага юм. Таны илгээсэн соорс online-judge системд хөрвүүлэгдээд яг ажиллах үед, системийн цаг хугацаа unixtime-н секундээр 10-д хуваахад 1 үлдэгдэл өгж болж байвал бүрэн зөв ажиллаж чадна гэсэн үг.

Тэгэхээр онолын хувьд бол 10 удаа бодолтоо илгээхэд нэг удаад нь бүрэн дүүрэн бодолт хийх магадлалтай ба, хэрвээ та овсгоотой бол шууд нэгхэн илгээгээд удаа unixtime-аар яг 10*X+1 дэхь секундэд програмаа бүрэн зөв ажиллуулах боломжтой юм :)

Баяр хүргэе!

2010-10-25T21:05:00.003+08:00

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

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

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

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

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

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

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

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

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

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

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

2010-10-14T10:43:00.006+08:00

Бодлого
Мод гэдэг нь чиглэлгүй, дурын 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
Дурын оройгоос Түвшний нэвтрэлт хийж хамгийн сүүлд очих навчнаас дахин Түвшний нэвтрэлт хийж хамгийн сүүлд очих навч хүртлэх ирмэгүүдийн тоо хариу болно.

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

2010-10-05T14:26:00.000+08:00

Тавил:
Тойрог дээр 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

2010-10-03T22:27:00.000+08:00

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

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

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

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

2010-10-03T22:20:00.001+08:00

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

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

Stripes

2010-10-03T22:16:00.000+08:00

Тавил:
Тэгш өнцөгт координатын системд зурагт үзүүлсэн шиг судлуудыг үүсгэсэн бол өгөгдсөн тэгш өнцөгт дотор хэдэн ширхэг хар нүд байгааг ол. 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) функцийн утгыг олох нь маш хялбархан юм. Доорх зурагт дүрсэлсэний дагуу улаан хүрээтэй хэсгийн утгыг, бас цэнхэр хүрээтэй хэсгийнхийг тус тусад нь олоод л болчихно.

Дундаж

2010-10-03T21:56:00.001+08:00

Тавил:
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) юм. Гэхдээ дундаж тохиолдолд үүнээс хамаагүй хурдан ажиллана.

Квадрат

2010-10-03T21:37:00.000+08:00

Тавил:
Өгөгдсөн 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)

2010-08-27T10:58:00.000+08:00

Яагаад ч юм өмнө нь тэмдэглэж авсан дээр маань өглөө 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

2010-08-20T11:47:00.003+08:00

Бодлого 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

2010-08-20T11:33:00.002+08:00

Бодлого 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 дахь чихэрээ авав.

Дуудалт	Буцаасан утга	Тайлбар
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

2010-08-19T13:51:00.002+08:00

Бодлого 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

2010-08-19T13:47:00.003+08:00

Бодлого 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

2010-08-19T13:40:00.002+08:00

Боодлого 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

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

IOI2010 Day 1 Бодлого 1

2010-08-19T13:31:00.005+08:00

Бодлого 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 Энэ удаад баталж чаджээ.

Дуудалт	Буцаасан утга	тайлбар
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)

2010-08-15T01:47:00.001+08:00

Энэ удаа манайхаас доорх хүмүүс оролцжээ.
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)

2010-08-04T20:58:00.000+08:00

За ёстой бөөн адал явдал гэхээс өөр юу гэхэв. Тэмцээн болтол түр гараад ирьюүү гээд гарчихаад ирсэн чинь тэмцээн эхэлснээс бараг 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)

2010-07-29T01:00:00.000+08:00

Энэ удаад манайхаас бүүр олон хүн орсон ба шинээр хэд хэдэн хүн нэмэгдсэн байна. 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)

2010-07-18T01:48:00.002+08:00

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

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 )

2010-05-13T11:43:00.005+08:00

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

Qualficiation Round:

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

Elimination Round :

Khongor (Round 1)

TCO 2010 Qualification Round 1 (Diary)

2010-05-03T17:29:00.003+08:00

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)

2010-04-20T20:50:00.002+08:00

Өнгөрөгч 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-р олимпиад

2010-04-16T19:48:00.005+08:00

SMCS баг

2010-04-08T09:56:00.005+08:00

Олимпиадад нийт 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

2010-04-08T09:50:00.004+08:00

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-н бодлогууд - Улс

2010-04-08T09:48:00.002+08:00

Улс
Улс нь 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-н бодлогууд - Болхи схем

2010-04-08T09:45:00.004+08:00

Болхи схем
Болхи схем өгөгджээ. Түүний бүтэц нь зангилаанууд болон тэдгээрийг холбосон холбогчуудаас тогтоно. Хоорондоо параллель 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

2010-04-03T21:40:00.006+08:00

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

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

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

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

2010-03-08T11:26:00.009+07:00

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

2010-02-28T12:06:00.005+07:00

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

2010-02-12T14:28:00.006+07:00

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

Үржвэр нь 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) болж өгөгдсөн хугацаанд хангалттай амжна.

Муруй зам:

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

Зарлал

2010-01-28T13:50:00.005+07:00

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

Хөзөр

2009-10-27T22:47:00.001+07:00

Тавил:
N хөзөр байгаа ба K-р хөзрийн 2 тал дээр K-1 ба K гэсэн 2 тоо бичсэн. M ширхэг хөзөр аван аль хөзөр дээрх нэг тоог нь тэмдэглэж аваад л буцааж тависаар гар дахь хөзрөө дуусгасан бол тэмдэглэсэн тоонууд өгөгдсөнөөр зөв тэмдэглэгдсэн эсэхийг тогтоо.
Эх бодлого: Хөзөр
Бодолт:
Хөзрийн нэг тал нь тэмдэглэгдсэн бол нөгөө тал нь тэмдэглэгдэх ёсгүй гэдгээс 0, N 2-оос бусад тоонууд дээд тал нь 2 удаа тэмдэглэгдэж болно.
Тэмдэглэлд бичигдсэн K тоо боломжит дээд ширхэгээрээ (0 болон N нь 1, 1 удаа бусад нь 2 удаа) тэмдэглэгдчихсэн бол K+1 дугаартай хөзрөөс тоо дуудахгүй гэсэн үг буюу K+1 тоог тэмдэглэсэн байх боломж 1-ээр цөөрнө гэсэн үг. Энэхүү цөөрсөн боломж нь K+1 тоог тэмдэглэсэн тооноос цөөхөн байвал алдаатай байна гэсэн үг. (K = for 0-ээс N-1 хүртэл) Ямар ч алдаа гараагүй бол зөв тэмдэглэгдсэн болно.

DP problems

2009-09-29T22:15:00.009+08:00

http://www.spoj.pl/CSMS - н зарим бодлогуудыг хуваахаар шийдлээ. Эхлээд DP (Dynamic Programming) ашиглан бодож болох зарим бодлогуудыг жагсаая.
CSMS0002, CSMS0041, CSMS0043, CSMS0084, CSMS0104, CSMS0106, CSMS0111, ABR1009, CSMS0007, CSMS0032, CSMS0034, CSMS0064, CSMS0067, IOI9622, TIM1012, TIM1537, TOP0001, TSEREG

Сериал

2009-09-29T21:53:00.001+08:00

Тавил:
Нэгэн компаний үйлдвэрлэсэн програмын сериалууд хоорондоо зөвхөн тэмдэгтүүдийн байрлалыг солисноороо ялгагддаг байна. Жинхэнэ сэриал нэг ширхэг мэдэгдэж байгаа бол сэжиглэгдэж байгаа сериалуудыг жинхэнэ мөн эсэхийг ялга.
Эх Бодлого: Сериал
Бодолт:
Жинхэнэ сэриал болон сэжиглэгдэж байгаа сэриал 2-ынхоо аль алиных нь тэмдэгтүүдийг эрэмбэлнэ. Тэгээд үүссэн эрэмбэт сериалууд нь хоорондоо тэнцүү бол уг сэжиглэгдэж буй сэриал жинхэнэ, тэнцүү биш бол хуурамч гэсэн үг.

Фүжи Инфокснэт компаний нэрэмжит програмчлалын 3-р олимпиад

2009-09-26T22:42:00.010+08:00

Фүжи Инфокснэт компаний нэрэмжит оюутны програмчлалын олимпиад 3 дахь жилдээ энэ сарын 26-ны өдөр ШУТИС-ийн КтМС дээр явагдаж өнгөрлөө. Олимпиадын дүн:

1. ШУТИС - КТМС Амгаланбаатар
2. МУИС - МКС Алмабек
3. ШУТИС - КТМС Шагай
МУИС - МТС Мөнхжаргал
ШУТИС - КТМС Гансүх
МУИС - МТС Жамсрандорж.

Энэхүү олимпиадад 3 бодлого ирсэн ба тус бүр 20, 15, 10 онооны бодлогууд байв. Бодлогуудын өгүүлбэрийг доор сийрүүлэн нийтэллээ.

Бодлого №1

N*M матрицийн нүднүүд дээр тодорхой тооны будаа овоолсон байх бөгөөд өгөгдсөн цэгээс нэгэн хулгана будаануудыг матрицийн аль нэг цэг дээр овоолохоор болжээ. Хулгана нэг удаад К-аас илүү тооны будаа зөөвөрлөж чадахгүй ба хулгана нь дурын нэг цэг дээр бүх будааг цуглуулахын тулд хамгийн багадаа ямар зам туулах хэрэгтэйг тооцоолон олно уу. Хулганы эхний байрлал Х, Ү өгөгдсөн ба матриц дээрх тоонууд нь будааны хэмжээг илэрхийлсэн болно. Хулгана нь тухайн байрлалаас 4 зүгт хөдлөх боломжтой.

Жишээ оролт:

3,3,4,0,0
0,3,0
1,0,5
0,0,4

Жишээ гаралт:

7

Эхний мөрийн эхний 2 тоо нь матрицийн хэмжээс. Дараа нь К буюу хулганы зөөвөрлөж чадах будааны тоо. Дараа нь Х, Ү буюу хулганы эхний байрлал

Бодлого №2:

Эхэнд өгөгдсөн олон хувьсагчтай илэрийллийг бусад олон хувьсагчтай илэрхийллүүдтэй тэнцүү эсэхийг шалгах.

Жишээ оролт:

(a-b)*2
2*a-2*b
a-2*b+a
4*a+3*b

Гаралт:

YES
YES
NO

Бодлого №3:

N ширхэг тэгш өнцөгтийн байрлал болон хэмжээс өгөгдсөн бөгөөд тэдгээр нь хоорондоо тодорхой хэмжээгээр огтлолцоно. Хамгийн олон тэгш өнцөгт огтлолцсон хэсгийн талбайг ол.

Жишээ оролт:

1,11,6,6
2,7,4,6
5,8,5,5

Гаралт:2

Үүнд мөрийн эхний 2 тоо нь тэгш өнцөгтийн зүүн дээд өнцгийн координат. Дараачин 2 тоо нь харгалзан тэгш өнцөгтийн өргөн ба өндөр.

What's happening?

2009-09-21T23:05:00.005+08:00

Хөршүүд

2009-09-17T12:36:00.009+08:00

Энгийн чиглэлгүй граф өгөгдөв. Орой бүр дээр тоо бичигдсэн ба нэг раундад орой бүр дээрх тоо түүнтэй холбогдсон оройнууд дээрх тоонуудын нийлбэр болж өөрчлөгднө. K раундын дараах оройнууд дээрх тоог ол.
Граф-н холболтыг илэрхийлэх матриц-г A, орой дээр бичигдсэн тоонуудыг 1*N матриц гэж үзээд B гэе. Нэг раундын дараа B=B*A болно гэдгийг харахад амархан. Тэгвэл К раундын дараа B=B*(A^K) болно. Эндээс гол асуудал нь A^K -г олох юм. A^K зэргийг O(N^3logK) -д олж болох ба энэ хэсгийг уншигч таньд үлдээе.

Урт факториал

2009-09-16T21:12:00.000+08:00

Тавил:
N эерэг бүхэл тоо өгөгдсөн бол 1*2*3*...*X тоо яг N оронтой байх бүх Х тоог ол. N-ийн хамгийн их утга 150000 байна.
Эх өгүүлбэр: Урт Факториал
Бодолт:
Өмнө дурдсан авсаархан аргыг ашиглавал дурын K! тооны оронгийн тоог Log10(1)+Log10(2)+...Log10(K)+1 гэж олж болно.
Мөн X! тооны оронгийн тоо нь эрэмбэлэгдсэн дараалал учир хоёртын хайлт хийж болно. Тиймээс 1-ээс N_MAX=150000 хооронд хоёртын хайлт хийж Х-г олно. X>=4 үед X ганц утгатайгаар олдох нь бараг л тодорхой билээ

Пифагорын гурвал

2009-09-15T21:40:00.024+08:00

Бодлогын дугаар: ABR0554

n натурал тоо өгөгдөв. Тус бүрийнх нь утга n-ээс хэтрэхгүй байх бүх натурал пифагорын гурвалыг буюу
a^2 + b^2 = c^2 ба
a ≤ b ≤ c ≤ n нөхцлүүдийг хангах бүх натурал тоон гурвалуудыг ол.

Энэ бодлогын хувьд өгүүлбэр, зорилго нь их энгийн хэрнээ хугацааны хувьд ярвигтай. Элдэв "дундын машин" ажилладаггүй Pascal, C/C++ гэх мэт дунд түвшний хэл дээр бодож Submit-лах нь тохиромжтой. Доор Python хэл дээрх эх кодыг нийтэллээ. Гэхдээ энэ кодыг шууд илгээхэд АС авахгүй шүү Python амжихгүй :P Алгоритмыг нь харж аваад for давталт ашиглаж Pascal, C/C++ дээр бичих нь тохиромжтой ;)

Алгоритмийн талаар тайлбар өгүүлэх нь:

Бодлогын өгөгдөл ёсоор
a ^ 2 + b ^ 2 = c ^ 2 үүнээс цаашлан задлаад
a ^ 2 = c ^ 2 - b ^ 2 = ( c - b ) * ( c + b ) = k гэе.

Одоо а тоог ямар нэг x , y тооны үржвэр хэлбэрээр тавигддаг гэж үзье / * тоог ямар ч тохиолдолд 2 тооны үржвэр хэлбэрт тавиж болно. Анхны тоо байх тохиолдолд ч a = a * 1 гэсэн үржвэр хэлбэрт тавьж болно * /.

a = x * y гэдгээс

k = x * ( x * y ^ 2) / * энэ тохиолдлыг эх код дээр
x = j, x * y ^ 2 = k / j гэж авсан байгаа.*/

( x * y ^ 2 + x ) % 2 == 0 байгаа үед

a ≤ b ≤ c ≤ n нөхцлийг хангах

b = ( x * y ^ 2 ) / 2
c = ( x * y ^ 2 + x ) / 2

болно. Баталгааг хийхээс бага зэрэг залхуурав.

Авсаархан шийдлүүд - 1

2009-09-13T15:05:00.002+08:00

Зарим бодлогыг зарим үйлдэл, функцүүдийг ашиглан хялбарханаар шийдэж болох юм. Тийм зарим бодлогуудаас үзье.

Бодлого 1: K тооны N зэрэг хэдэн оронтой вэ? (1<K, N<1000)
Шийдэл: K^N тооны оронгийн тоо нь Log10(K^N)+1 буюу N*Log10(K)+1 гэсэн үг.
C хэл дээрх бодолтын хэсгээс бичвэл:
printf("%d", (int)(N*Log10(K))+1);
Жич: K, N нь нэлээн том тоо болчихвол Log10(K)-ын нарийвчлалаас хамаараад алдаатай хариу гарах юм. Тиймээс (1<K, N<1000) гэдгийг анхаарна уу.
Уг санааг ашиглан бодож болох бодлогууд:
Uva - 10219

Бодлого 2: 2N+1 (10^6<N) ширхэг тоо өгөгдсөн ба зөвхөн нэг тоо л сондгой ширхэг өгөгдсөн (бусад нь бүгд тэгш ширхэг гэсэн үг) бол тэрхүү тоог ол.
Шийдэл: XOR үйлдлийг ашиглавал их амархан бодогдоно. Бүх тоонууд дээрээ эхнээс нь XOR үйлдлийг хийхэд гарах тоо нь бидний хайсан хариу юм.

Цэрэг

2009-09-12T22:43:00.012+08:00

Тавил:
Эгнэж жагссан цэргүүдээс дайнд оролцох цэргүүдийг сонгохдоо аль ч хоёр зэрэгцээ цэргийг 2-ууланг нь сонгохгүй байхаар шийджээ. Тэгвэл N (2<N<10^9) цэргээс сонголт хийж болох нийт боломжийн тоог ол.
[Эх бодлого]

Бодолт:
Динамик програмчлал ашиглан бодъё.
Сүүлийн цэргийг сонгох эсвэл сонгохгүй байх гэсэн 2 боломж бий...
1. Хэрвээ сонгоогүй бол түүнээс өмнөх цэргүүдийг сонгох боломжийн тоотой нь тэнцүү: F(N-1)
2. Харин сонгосон гэж үзвэл зэрэгцээ 2 цэргийг 2-уулангсонгож болохгүй учир түүний өмнөх цэргийг заавал алгасах ёстой. Тиймээс сүүлчийн цэргийг сонгосон тохиолдлын тоо нь: F(N-2)-той тэнцүү. Бас нэг мартаж болохгүй онцгойдуу тохиолдол байгаа нь зөвхөн сүүлчийн цэргийг дангаар нь сонгож болох ганц хувилбар юм. Өөрөөр хэлбэл сүүлчийн цэргээс өмнөх бүх цэргийг сонгохгүй гэсэн үг. Энэ тохиолдол нь F(N-2)-т багтахгүй юм. Тиймээс F(N-2)+1 болно.
Тэгэхлээр: F(N)=F(N-1)+F(N-2)+1 (*) болно.

Бодолт ингээд л болчихгүй. Учир нь N-н авч болох дээд утга нь 10^9 орчим. Тэгэхлээр (*) томьёогоор бодвол Log(N) хугацаа буюу 1 секундэд лав амжихгүй. Тиймээс жаахан сайжруулъя.
(*) томьёо нь бараг л алдарт Фибоначийн тооны аналитик загвар байгаа биз? Тиймээс энэ томьёогоор жаахан оролдвол F(N)=Fib(N+2)-1 болохыг түвэггүй мэдчихнэ. (Fib(N) - N-дүгээр фибоначийн тоо) Иймээс Fib(N)-г хурдан олох арга хайя.

F(N) функцийг бодвол Фибоначийн тоо нэлээн судлагдсан учир Wikipedia жаахан ухахад л:
Fib(2N) = Fib(N)^2 + 2*Fib(N)*Fib(N+1)
Fib(2N+1) = Fib(N)^2 + Fib(N+1)^2 (**)
гэсэн аятайхан томьёог олж болно. (**) Томьёог ашиглан Fib(N+2)-г Log2(N) буюу Log(N) хугацаанд бодно.

Mini Judge :D

2009-08-19T11:08:00.014+08:00

Нэтээр тэнэж яваад http://scarky.com гэдэг сайт оллоо. Энэ сайт нь жижигхэн бодлого дэвшүүлж түүнийгээ өөрийн сайт дээр тавих боломжтой юм байна. За туршилтын энэ бодлогыг оролдож үзнэ үү. Хугацааны хязгаарлалт сайн алга 2-3 сек байж магад.
&amp;amp;amp;amp;amp;amp;lt;br&amp;amp;amp;amp;amp;amp;gt;

Програмчлалын 19-р олимпиадын бодлогууд

2009-05-19T22:44:00.016+08:00

Оюутны улсын олимпиадын бодлогууд.

run

neon

uguudei

cirpix

OneMad

mem

Нийлбэрт задлах боломжууд

2009-04-15T09:00:00.004+08:00

Тавил :
Өгөгдсөн N тоог 1..N тоонуудын нийлбэрт хичнээн янзаар задлаж болох вэ?
1+2+1,1+1+2. Энэ 2 нийлбэрийг ижил гэж үзэх учраас бодлогыг үл буурах тоонуудын нийлбэрт задлах бодлого гэж ойлгож болно.
s[i,j]-р i тоог задлах боломжуудын дотроос хамгийн сүүлийн тоо нь j байх боломжийн тоог тэмдэглэе.
s[i,j]=Σs[i-j,k] (k=1..j)
Ингээд бодлогын хариу
Σs[n,i] (i=1..n)

Ball

2009-01-23T18:35:00.002+07:00

Хоосон эсвэл ханаас бүтсэн NхN хэмжээтэй хөлгийн хоосон нүдэнд бөмбөг байрлана. Мөн хөлгийгтойроод хана байгаа. Хөлгийг цагийн зүүний эсрэг, эсвэл цагийн зүүний дагуу эргүүлнэ. Эргүүлэхэд бөмбөг татах хүчний дагуу доошоо унана. Унахдаа хана байвал нэвтэлж чадахгүй ханан дээр тогтоно.
К удаа эргүүлсний дараа хөлөг ямар байдалтай байхыг харуул.
( 1<=N<=1000 ) , ( 1<=K<=500 000 )
Зөвхөн бөмбөгний хувьд бодолт хийе. Өөрөөр хэлбэл K үйлдлийн дараа бөмбөг хаана байрлах вэ? Гэдгийг тогтооё. Жишээ нь цагийн зүүны дагуу эргүүлнэ гэвэл бөмбөгний баруун талд орших хамгийн ойрхон ханыг олно гэсэн үг юм.
Хөлгийн элемэнт бүрд хамгийн ойр орших зүүн, баруун, дээд, доод ханын координатыг массивт хадгалаад бодвол хялбар бодогдно.
O(n^2+k);

Олимпиад

2008-12-16T20:43:00.002+07:00

Өнгөрсөн хагас сайнд буюу 12.13 нд фүжи инфокс нэт компаний нэрэмжит II олимпиад болж өнгөрлөө. Их ч олон оюутан орлоо. Олимпиадын дүнг танилцуулья.
1. МУИС-н МТС-н оюутан Батчунаг
2. МУИС-н МКС-н оюутан Золбаяр
МУИС-н МТС-н оюутан Гантулга
3. МУИС-н МКС-н оюутан Хасан
МУИС-н МТС-н оюутан Мөнгөншагай
USI-н оюутан Буянбат
Тусгай байр :
МУИС-н МКС-н оюутан Хонгор
КТМС-н оюутан Шагай
КТМС-н оюутан Адъяа
За олимпиадын дүн нэг иймэрхүү. Бодлогуудыг www.spoj.pl/CSMS/ сайт дээрээс үзэж болно.

Квадрат тэгшитгэл

2008-12-07T20:23:00.005+07:00

Квадрат тэгшитгэлийн шийдийг ол. a*x*x+b*x+c=0
Оролт:
Эхний мөрөнд шийдийн тоо: N (1<=N<=1000)
Дараагийн N мөрөнд тоонууд an, bn, cn тоонууд (an тэгээс ямагт ялгаатай байна) сул зайгаар тусгаарлагдан өгөгдөнө. a, b, c тоонууд бодит тоонууд бөгөөд ямар ч тохиолдолд таслалаас хойш 3 орны нарийвчлалтай өгөгдөнө. Тухайлбал: 5-г 5.000 гэж бичнэ. Шийдийг хэвлэхдээ таслалаас хойш 3 орны нарийвчлалтай хэвлэж гаргана.
Хязгаарлалт : -10^6 < a, b ,c<10^6
Эх өгүүлбэр

Бодолт
Уул нь энгийн л бодлого. Гол асуудал бодит тооны нарийвчлал.
a*x^2+b*x+c=0
1000*a*x^2+1000*b*x+1000*c=0
Уг хоёр тэгшитгэл ижил үр дүн үзүүлнэ. Одоо бодоход амархан биз.

Шадар гурван квадрат

2008-11-06T21:52:00.007+07:00

Тавил:
4xN тэгш өнцөгтийг зурагт дүрсэлсэн хэлбэртэй 3 квадратаар (эргүүлж болно) илүү гаргалгүй, давхардуулалгүй, дунд нь нүд үлдээхгүй дүүргэх нийт боломжийн тоог ол.
Эх өгүүлбэр: Шадар гурван квадрат
Бодолт:
N mod 3 != 0 үед хариу нь 0 байх нь тодорхой.
N = 3*K гэвэл.

11111...
11111...
11111...
11111...

хэлбэртэй 4x3K хэмжээтэй дүрсийг

10
11

дүрсээр хувааж болох хувилбарын тоог F(n) гэе.

00111...
00111...
01111...
01111...

хэлбэртэй 4x3K+6 хэмжээтэй дүрсийг

10
11

дүрсээр хувааж болох хувилбарын тоог G(n) гэе.

Тэгвэл:
F(k) = 4*F(k-1) + 4*G(k-2) + 2*F(k-2);
G(k) = 2*F(k-1) + 6*G(k-1);

F(0) = 1; F(1) = 4;
G(0) = 0; G(1) = 2;
гэсэн рекурсив функц олдоно. Эндээc F(k) нь хариу болно.

Нүх

2008-10-03T21:42:00.004+08:00

Тавил
0,1 гээс бүрдэх массивт агуулагдах зөвхөн тэгээс бүрэлдэх хамгийн том квадратын хэмжээг ол.

Бодолт
f(x,y) функцээр зүүн доод булан нь (x,y) байх хамгийн том квадратын талыг тэмдэглэе.
Хэрвээ (x,y) нүд 1 бол f(x,y)=0
үгүй бол f(x,y)=min(f(x-1,y-1),f(x,y-1),f(x-1,y))+1
болно.
Бүх x,y-гийн хувьд f(x,y)-ийг бодож олоод хамгийн ихийг нь олвол тэр нь хариу болно.

Факториалын сүүлийн тэг биш цифр

2008-09-11T20:33:00.009+08:00

Өгсөн n натурал тооны факториалын хамгийн арын тэг биш цифрийг ол.
Жишээ 1:
Оролт: 5
Гаралт: 2 // 5!=120 -> 2
Жишээ 2:
Оролт: 1000000
Гаралт: 4
Эх өгүүлбэр: [Факториал 2]
Энэ бодлогын тухай дахь өөрийнхөө мэдэж байгаа хамгийн сайн алгоритмаа танилцуулъя.
N=1 үед л хариу сондгой тоо гарна. Иймд N=1 үед хариу:1. Харин бусад тохиолдолд нь:
1. 1*2*3*4*6*7*8*9 (5 болон 0-г орхисон) үржвэрийг сонирхвол сүүлийн тэг биш цифр нь 6 байгаа. Энэ бол бодлогын маань гол түлхүүр.
2. 6-г ямар ч тэгш цифрээр үржүүлсэн тэр тэгш цифрээр нь төгссөн тоо гардаг.

N0 = N - (N MOD 10) гэж тэмдэглэе (тооны сүүлийн цифрийг тэг болгосон гэсэн үг)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 ... N0
гэсэн дараалын 10-т болгон дахь (1, 2, 3, 4, 6, 7, 8, 9) гэсэн цифрүүдээр төгссөн тоонууд нь 6-гаар төгсөх учир (2) - ээс үндэслэн эдгээрийг орхичихож болно.
Тэгэхлээр дараах тоонууд үлдэнэ:
5 10 15 20 25 30 35 40 45 ... N0 N0+1 ... N
Ингээд N0 болон түүнээс өмнөх тоонуудыг 5-д хуваачихвал 1 2 3 4 5 ... гэх мэт цуваа үүснэ...
Тэгэхлээр бүдүүн тоймоор бол:
F(n) = ( 5^(n/5) * F(n/5) * (N0+1 * ... * N) тооны сүүлийн тэг биш цифр) гэсэн рекурсив гарна.

Тэгээд 5^k гэсэн илэрхийлэл нь тооцоог хүндрүүлэх тул:2^n зэргийг үржүүлээд хуваагаад өгчихвөл 10^k/2^k зэрэг болох ба энэ нь 16/2=8 байдагаас *6/2=8 (сондгой тоог тооцохгүй!) гэж үзэж болно. Иймэд 5^k => 10^k / 2^k => 8^k гэж болно. Мөн 8^(k+4) = 8^k * 4096 гэдгээс
8^(k+4) mod 10 = 8^k mod 10 гэж гарна.

Иймд
F(n) = 8^(n/5 mod 4) * F(n/5) * (N0+1 * ... * N); гэсэн рекурсив гарах ба энэ нь бодолтонд хангалттай.
N0+1 -ээс N хүртэл (N mod 10) тоо байгаа учраас (N0+1 * ... * N) илэрхийллийг яаж л бол яаж хялбарчилж болно.
Жишээ бодолт:
n = 123 үед
123! == 5^14 * 14! * (121 * 122 * 123) == 8^14 * 14! * 6 == 14! * 4;
4*14! == 4 * 5^2 * 2! * (11*12*13*14) == 4 * 8^2 * 2 * 4 == 6;

Алгоритмийн шинжилгээ: O(log5(N))

Булийн функц

2008-09-10T16:20:00.006+08:00

Эрдэмтэн Буль өөрийн судалгаандаа логикийн үнэн худлыг ашигласан функц зохиож ашиглахаар шийджээ. Энэхүү функц нь тодорхой тооны аргумент авдаг ба түүнд харгалзах үнэн-1 эсвэл худал-0 гэсэн үгийг хэвлэдэг байжээ. Функц болгон нь өөрийн дугаартай байдаг. Жишээ нь: 141-р функц гэвэл 141=10001101B байна. Доорх жишээнд бүр тодорхой үзүүлье.

x1 | x2 | x3 | f
0 | 0 | 0 | 1
0 | 0 | 1 | 0
0 | 1 | 0 | 1
0 | 1 | 1 | 1
1 | 0 | 0 | 0
1 | 0 | 1 | 0
1 | 1 | 0 | 0
1 | 1 | 1 | 1

Хэрвээ функцийн аргументаар f(0,1,0) гэвэл энэ нь үнэн болно. Харин f(1,1,0)=0. Та дараах программыг бичих ёстой. Оролтын эхний мөрөнд тестийн тоо байрлах ба дараагийн мөрөнд функцэд харгалзах аргументууд ба мөрийн сүүлд функцийн дугаар байна. Гаралтанд зөвхөн 1 эсвэл 0-үүдийг оролтынх нь дарааллаар бичиж гаргана (A[i]). Аргументуудын тоо нь дөрвөөс хэтрэхгүй (j<5>
Оролт:

n
x1 x2 ... xj F
...

Гаралт:

A1
A2
...
An

Жишээ оролт:

3
1 0 1 141
0 0 0 1
1 1 15

Жишээ гаралт:

0
1
1

Тайлбар: Хоёрдох жишээ оролтонд дараах үнэний хүснэгт үүснэ. Х-ийн {0,0,0} утганд харгалзах функцийн утга нь 1 байна.

x1 | x2 | x3 | f
0 | 0 | 0 | 1
0 | 0 | 1 | 0
0 | 1 | 0 | 0
0 | 1 | 1 | 0
1 | 0 | 0 | 0
1 | 0 | 1 | 0
1 | 1 | 0 | 0
1 | 1 | 1 | 0

Бодлогын эх : Булийн функц

Бодолт

зөвхөн нэг тестийн хувьд авч үзье. x1,x2..xn г 2 тийн тооллын системд өгөгдсөн гэж үзээд аравтын тооллын системд шилжүүлээд K гэж тэмдэглэе. Тэгвэл бодлогын хариу нь F н 2тийн тооллын систем дэхь бичлэгийн ардаасаа K+1 дахь цифр болно. Хэрвээ K+1 дахь цифр байхгүй бол 0 гэсэн үг болно.

Байрлал

2008-09-10T16:12:00.005+08:00

Тавил:
Тэмдэгтүүдийн дараалал өгөгджээ. (Тэмдэгтүүд бүгд хоорондоо ялгаатай) Тэгвэл уг тэмдэгтүүдээс цагаан толгойн дарааллаар сэлгэмэл үүсгэхэд уг тэмдэгтийн дараалал хэддүгээр гишүүн бэ?
Жишээ:
Оролт: bza:
Гаралт: 4
//(abz,azb,baz,bza,zab,zba)
Эх өгүүлбэр: Байрлал

Бодолт:

i = Оролтын эхнээсээ i дахь үсэг // 1-ээс n хүртэл;
order[i] = (i-дахь үсгийн араас байрлалтай үсэгнүүдээс цагаан толгойн дарааллаар i-аас өмнө орших үсэгнүүдийн тоо) + 1;

Хариу = 1 + order[1]*(n-1)! + order[2]*(n-2)! + order[3]*(n-3)! + ... order[n-1]*1!;

Баталгаа:
i дахь үсгийн ард (n-i) үсэг байгаа ба тэдгээр нь (n-i)! сэлгэмэл үүсгэнэ. Мөн i дахь үсгийн өмнө order[i] ширхэг үсэг байгаа ба тэдгээр нь ардаа тус бүр (n-i) янзын өөр цуваа залгаатай байгаа учраас комбинаторик дахь үржвэрийн дүрмээр order[i]*(n-i) байгаа юм.
Тэгээд мэдээж i маань 1-ээс n хүртэл утга авах ба i=n үед order[i]*0! = 0 байх нь ойлгомжтой билээ.
Дээр нь тоог 1-ээс эхэлж дугаарладаг учраас 1-г нэмж өгөөд болно.

Update: 2 дахь мөрийн эхний өгүүлбэрийн ард "(Тэмдэгтүүд бүгд хоорондоо ялгаатай)" гэж нэмж бичив.

Жимс

2008-09-10T16:12:00.003+08:00

Бяцхан сармагчин жимс цуглуулахаар явж байв. Тэрээр байгаа чулууны баруун урд, эсвэл зүүн урд чиглэлийн чулуу уруу л шилжиж чадна. Чулуу болгонд тодорхой хэмжээний жимс байх бөгөөд эцсийн шатанд сармагчиний авч чадах хамгийн их жимсний тоог ол.
Input
N: Эхний мөр нийт шилжилтийн тоо. a(i,j), 1 < = j < = i < = N Чулуу болгон дээр байгаа жимсний тоо 0 < = N, a(i,j) <= 200 Output Цуглуулж чадах хамгийн их жимсний тоо Example Input: 3 0 3 1 1 2 2 Output: 5
Бодлогын эх: Жимс

Бодолт
Эхлээд N-1 дэх мөрийг авч үзье. Тэгвэл a[n-1,i] дээр max(a[n,i],a[n,i+1]) ийг нэмье.
Дараа нь N-2 дэх мөрийг авч мөн уг үйлдлийг хийнэ. Энэ алхмыг үргэлжлүүлсээр 1 дэх мөр хүртэл хийнэ. Ингээд a[1,1] нь анхны бодлогын хариу болно.

Өмнөх үг

2008-09-10T16:06:00.000+08:00

Энэхүү блогийг нээж байгаа залуучууд нь анх Online Judge систем бүхий сайтуудад бодлого бодож байгаад танилцсан бөгөөд хүмүүст хэрэг болж магадгүй хэмээн сурсан мэдсэн жаахан зүйлсээсээ нийтлэж байхаар шийдлээ.
Бидэнд үргэлж тусалж дэмжиж байдаг Чимэдээ ахын блогноос санаа аван энэхүү блогийг нээлээ.
Мөн Монгол хэл дээр Online Judge системээр дамжуулан тэмцээн уралдаан болдог дараах сайтуудыг ажиллуулдаг хүмүүст баярлаж талархаж явдаг шүү.
http://www.coder.mn
http://www.spoj.pl/CSMS
http://www.spoj.pl/CHAMKA