Өнгөрсөн хагас сайнд буюу 12.13 нд фүжи инфокс нэт компаний нэрэмжит II олимпиад болж өнгөрлөө. Их ч олон оюутан орлоо. Олимпиадын дүнг танилцуулья.
1. МУИС-н МТС-н оюутан Батчунаг
2. МУИС-н МКС-н оюутан Золбаяр
МУИС-н МТС-н оюутан Гантулга
3. МУИС-н МКС-н оюутан Хасан
МУИС-н МТС-н оюутан Мөнгөншагай
USI-н оюутан Буянбат
Тусгай байр :
МУИС-н МКС-н оюутан Хонгор
КТМС-н оюутан Шагай
КТМС-н оюутан Адъяа
За олимпиадын дүн нэг иймэрхүү. Бодлогуудыг www.spoj.pl/CSMS/ сайт дээрээс үзэж болно.
Tuesday, December 16, 2008
Sunday, December 7, 2008
Квадрат тэгшитгэл
Квадрат тэгшитгэлийн шийдийг ол. 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
Уг хоёр тэгшитгэл ижил үр дүн үзүүлнэ. Одоо бодоход амархан биз.
Оролт:
Эхний мөрөнд шийдийн тоо: 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
Уг хоёр тэгшитгэл ижил үр дүн үзүүлнэ. Одоо бодоход амархан биз.
Thursday, November 6, 2008
Шадар гурван квадрат
Тавил:
4xN тэгш өнцөгтийг зурагт дүрсэлсэн хэлбэртэй 3 квадратаар (эргүүлж болно) илүү гаргалгүй, давхардуулалгүй, дунд нь нүд үлдээхгүй дүүргэх нийт боломжийн тоог ол.
Эх өгүүлбэр: Шадар гурван квадрат
Бодолт:
N mod 3 != 0 үед хариу нь 0 байх нь тодорхой.
N = 3*K гэвэл.
Тэгвэл:
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) нь хариу болно.
4xN тэгш өнцөгтийг зурагт дүрсэлсэн хэлбэртэй 3 квадратаар (эргүүлж болно) илүү гаргалгүй, давхардуулалгүй, дунд нь нүд үлдээхгүй дүүргэх нийт боломжийн тоог ол.Эх өгүүлбэр: Шадар гурван квадрат
Бодолт:
N mod 3 != 0 үед хариу нь 0 байх нь тодорхой.
N = 3*K гэвэл.
11111...хэлбэртэй 4x3K хэмжээтэй дүрсийг
11111...
11111...
11111...
10дүрсээр хувааж болох хувилбарын тоог F(n) гэе.
11
00111...хэлбэртэй 4x3K+6 хэмжээтэй дүрсийг
00111...
01111...
01111...
10дүрсээр хувааж болох хувилбарын тоог G(n) гэе.
11
Тэгвэл:
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) нь хариу болно.
Friday, October 3, 2008
Нүх
Тавил
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)-ийг бодож олоод хамгийн ихийг нь олвол тэр нь хариу болно.
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)-ийг бодож олоод хамгийн ихийг нь олвол тэр нь хариу болно.
Thursday, September 11, 2008
Факториалын сүүлийн тэг биш цифр
Өгсөн 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))
Жишээ 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))
Wednesday, September 10, 2008
Булийн функц
Эрдэмтэн Буль өөрийн судалгаандаа логикийн үнэн худлыг ашигласан функц зохиож ашиглахаар шийджээ. Энэхүү функц нь тодорхой тооны аргумент авдаг ба түүнд харгалзах үнэн-1 эсвэл худал-0 гэсэн үгийг хэвлэдэг байжээ. Функц болгон нь өөрийн дугаартай байдаг. Жишээ нь: 141-р функц гэвэл 141=10001101B байна. Доорх жишээнд бүр тодорхой үзүүлье.
Хэрвээ функцийн аргументаар f(0,1,0) гэвэл энэ нь үнэн болно. Харин f(1,1,0)=0. Та дараах программыг бичих ёстой. Оролтын эхний мөрөнд тестийн тоо байрлах ба дараагийн мөрөнд функцэд харгалзах аргументууд ба мөрийн сүүлд функцийн дугаар байна. Гаралтанд зөвхөн 1 эсвэл 0-үүдийг оролтынх нь дарааллаар бичиж гаргана (A[i]). Аргументуудын тоо нь дөрвөөс хэтрэхгүй (j<5>
Оролт:
Гаралт:
Жишээ оролт:
Жишээ гаралт:
Тайлбар: Хоёрдох жишээ оролтонд дараах үнэний хүснэгт үүснэ. Х-ийн {0,0,0} утганд харгалзах функцийн утга нь 1 байна.
Бодлогын эх : Булийн функц
Бодолт
зөвхөн нэг тестийн хувьд авч үзье. x1,x2..xn г 2 тийн тооллын системд өгөгдсөн гэж үзээд аравтын тооллын системд шилжүүлээд K гэж тэмдэглэе. Тэгвэл бодлогын хариу нь F н 2тийн тооллын систем дэхь бичлэгийн ардаасаа K+1 дахь цифр болно. Хэрвээ K+1 дахь цифр байхгүй бол 0 гэсэн үг болно.
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 гэсэн үг болно.
Жимс
Бяцхан сармагчин жимс цуглуулахаар явж байв. Тэрээр байгаа чулууны баруун урд, эсвэл зүүн урд чиглэлийн чулуу уруу л шилжиж чадна. Чулуу болгонд тодорхой хэмжээний жимс байх бөгөөд эцсийн шатанд сармагчиний авч чадах хамгийн их жимсний тоог ол.
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] нь анхны бодлогын хариу болно.
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] нь анхны бодлогын хариу болно.
Байрлал
Тавил:
Тэмдэгтүүдийн дараалал өгөгджээ. (Тэмдэгтүүд бүгд хоорондоо ялгаатай) Тэгвэл уг тэмдэгтүүдээс цагаан толгойн дарааллаар сэлгэмэл үүсгэхэд уг тэмдэгтийн дараалал хэддүгээр гишүүн бэ?
Жишээ:
Оролт: bza:
Гаралт: 4
//(abz,azb,baz,bza,zab,zba)
Эх өгүүлбэр: Байрлал
Бодолт:
Хариу = 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 дахь мөрийн эхний өгүүлбэрийн ард "(Тэмдэгтүүд бүгд хоорондоо ялгаатай)" гэж нэмж бичив.
Тэмдэгтүүдийн дараалал өгөгджээ. (Тэмдэгтүүд бүгд хоорондоо ялгаатай) Тэгвэл уг тэмдэгтүүдээс цагаан толгойн дарааллаар сэлгэмэл үүсгэхэд уг тэмдэгтийн дараалал хэддүгээр гишүүн бэ?
Жишээ:
Оролт: 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 дахь мөрийн эхний өгүүлбэрийн ард "(Тэмдэгтүүд бүгд хоорондоо ялгаатай)" гэж нэмж бичив.
Өмнөх үг
Энэхүү блогийг нээж байгаа залуучууд нь анх Online Judge систем бүхий сайтуудад бодлого бодож байгаад танилцсан бөгөөд хүмүүст хэрэг болж магадгүй хэмээн сурсан мэдсэн жаахан зүйлсээсээ нийтлэж байхаар шийдлээ.
Бидэнд үргэлж тусалж дэмжиж байдаг Чимэдээ ахын блогноос санаа аван энэхүү блогийг нээлээ.
Мөн Монгол хэл дээр Online Judge системээр дамжуулан тэмцээн уралдаан болдог дараах сайтуудыг ажиллуулдаг хүмүүст баярлаж талархаж явдаг шүү.
http://www.coder.mn
http://www.spoj.pl/CSMS
http://www.spoj.pl/CHAMKA
Бидэнд үргэлж тусалж дэмжиж байдаг Чимэдээ ахын блогноос санаа аван энэхүү блогийг нээлээ.
Мөн Монгол хэл дээр Online Judge системээр дамжуулан тэмцээн уралдаан болдог дараах сайтуудыг ажиллуулдаг хүмүүст баярлаж талархаж явдаг шүү.
http://www.coder.mn
http://www.spoj.pl/CSMS
http://www.spoj.pl/CHAMKA
Subscribe to:
Comments (Atom)