АЛГОРИТМЫН ЦАГААН ТОЛГОЙ (SPOJ)

2020-03-17 00:00:00 RGB7843 - Хамгийн цөөн Swap by Bataa
RGB7843 - Хамгийн цөөн Swap aldaatai testiig zassan tul dahin ilgeene uu.

2018-10-09 00:00:00 Чансаа by Bataa
Зөв бодсон бодлогын тоогоор эрэмбэлдэг боллоо. Чансаагаа хараарай.

2013-05-25 10:14:26 Хүлцэл by Bataa
www.spoj.com\RGBC4 site дээр UVa сайтны хялбар бодлогуудаар онлайн тэмцээнээ 2013 оны 5-р сарын 31-ны 19:00-22:00 цагийн хооронд амжилттай зохиолоо. Тэмцээнд оролцсон, мөн санал шүүмжээ ирүүлсэн бүх хүмүүст баярлалаа. Нийт 16 оролцогчийн 7 нь өгөгдсөн 7 бодлогоо бүтэн бодсон байна. Баяр хүргэе.
Хүндэтгэсэн
Багш Ц.Баттогтох

2013-05-20 10:35:44 Бямба гараг бүр онлайн олимпиад by Bataa

“Бямба гараг бүр онлайн олимпиад”

UVa (SPAIN) онлайн сайтаас өдөр бүр бодлого бодоцгооё. Хөнгөнөөс хүнд рүү.
Энэ 7 хоногийн бодлогууд нь хялбар бодлогууд байх /шугаман, салаалсан, тодорхой давталтын энгийн бодлогууд/ ба бодлого тус бүрийг 7 минутанд бодож байвал сайн.
Бямба гараг бүрийн 16:00-19:00 цагт тухайн 7 хоногт зарлагдсан бодлогуудаас сонгон онлайн олимпиад зохиох болно. Орчуулгыг зөвхөн онлайн олимпиадад тавих болно.
Энэ 7 хоногийн бодлогууд :
UVa 00272, UVa 01124, UVa 10550, UVa 11044, UVa 11172, UVa 11364, UVa 11498,
UVa 11547, UVa 11727, UVa 12250, UVa 12279, UVa 12289, UVa 12372, UVa 12403.
Амжилт хүсье.

Хүндэтгэсэн
Алгоритм баг
Багш Ц.Баттогтох

2013-04-20 19:10:13 "Онлайн олимпиад 3" анализ by Bataa

“Олимпиад 3”

http://spoj.com/RGBC3 2013.04.17 20:00-23:00
Анализыг "Шинэ Монгол" ахлах сургуулийн 12-р ангийн сурагч Гантөмөрийн Золжаргал.

A. Үсэг дахиад

Асуудалгүй бодлого байсан болов уу. Тэмдэгт мөрөө эхнээс нь шалгаад явчихвал болно. Үсэг бүр дээр өмнө нь гарсан бол ans++; тэр үсэгээ гарсан гэж тэмдэглээд болоо.

B. Үлдэгдэл

Математик тооцооллоор O(1)-д хариуг олох боломж байж магадгүй (бодолт хийхээс залхуурсан болно. Хэхэ) . Бидний сонирхож буй хариу болох тоо маань 0-1699 -н хооронд байх нь ойлгомжтой. Иймд энэ хооронд гүйлгэж шалгаад, mod17=a ; mod100=b байх эсэхийг шалгахад л болно. 17*100 = 1700 байгаа нь дээрх бодлогыг хэрэглэх боломжыг олгож байна.

C. Бүхэл цэгүүд

Жишээ тест дээр өгсөн 3 Т/Ө-г байгуулаад үзээрэй. Бидний бодлогын хариу болох цэгүүд маань зүүн дээд координатуудын хамгийн баруун, доод цэг болон баруун доод координатуудын хамгийн зүүн, дээд цэгээр хязгаарлагдсан Т/Ө байх болно. Дээрх 2 цэгийн координатыг олвол бодлого ерөнхийдөө бодогдох болно. :) Цаасан дээр зураад үзвэл алгоритмийн санаа гарчих байсан.

D. Тоо хуваагдаад л

Миний бодолт лав хялбар рекурс. Эхний орон дээрээ 0-9 хүртэлх цифр дундаас бүх өмнө нь ороогүй бүх цифрээ шалгаж үзээд, оронгийн тоонд хуваагдаж байгаа эсэхийг шалгана. Хэрэв дээрх нөхцөл биеэлж байвал хойно нь дахин цифр залгаж шалгах замаар ажиллана. Шалгалт бүр дээр шалгаж буй тоо маань өмнө нь олсон хариунаас их эсэхийг шалгаад, ихийг нь хадгалаад явахад рекурс дуудалт дууссаны дараа хамгийн их тоо маань хадгалагдан үлдсэн байх болно.

E. Үржигдэхүүн нийлбэр

Эхлээд яг ямар хэлбэрийн үржигдэхүүнд задлахаа бодоцгооё. A=n*m гэж задалсан ба m=m1*m2 гэж задалж болдог гэж үзье. Иймд A=n*m1*m2 гэсэн задаргаа боломжтой болно. Эхний тохиолдолд sum=n+m ; 2-дох үед sum=n+m1+m2 байна. m=m1*m2 бол m > m1+m2 (m1, m2 != 1) байдаг. Иймд бид A тоог аль болох олон тооны үржвэрт задалсан тохиолдолд нийлбэр маань багасах нь харагдаж байна. Тэгэхээр A-г анхны тоон үржигдэхүүнд задлаад, нийт үржигдэхүүний нийлбэрийг олох хэрэгтэй гэсэн үг. :D .. Анхаарах нөхцөл нь A тоо 1, эсвэл анхны тоо байх үед ans=A+1 байна.

F. Үлдэх нь

Сонирхолтой бодлого байлаа. Оролтын хязгаарлалт хангалттай том байсан тул ямар нэг массив, эсвэл төстэй өгөгдлийн бүтэц ашиглах санаа лав олоогүй. (би мэдэхгүй. :( )... Яг тоглоомын дүрмийг дагаж тоглодог код бичиж, цөөн хэдэн өгөгдөл өгсний дараа хариу болох тоо маань цөөхөн хэд байгаа бөгөөд, n-с хамаарч байгаа нь харагдсан. :) … Энэ Анализтай хавсаргасан F_test програм n<10000 үед тоглолт хийж, хариуг гаргаж байгаа. Зүй тогтлыг нь олохдоо ашиглаарай. :) . Амархан зүй тогтол байгаа учраас тайлбарлалгүй үлдээе.

G.Бутархай

Бид ямар нэг n/m бутархайг нийлбэрт задлахдаа дурын q/p (n/m > q/p) бутархайг нийлбэртээ авч болох нь харагдана. Баталгаа нь нээх хэцүү биш байх аа. Хэд хэдэн хуваарь өгөөд туршиж үзэхэд болно. Иймд манай бодлогын нөхцөлд байгаа x= 1/3 – г шалгах.. гэх мэтээр. Бодолтын санаа нь амархан ч, яг кодоо бичихэд зарим нэг асуудал гарч магадгүй л юм (над дээр лав толгой эргүүлмээр хэдэн асуудал байсан.) Гол хэцүү нь бутархай тоонуудыг алдаагүй +/- чадахгүй учраас салангид байдлаар сэтгэх хэрэгтэй болсонд оршино.

H. Цифрүүдийн нийлбэр тоо

Хий гэсэн үйлдлийг нь хийгээд явчихад л болчихсон. Бараг хамгийн амархан бодлого байсан байх шүү. Хэхэ. Гол анхаарах юм нь анхны өгөгдөл нэлээн урт байх тул тэмдэгт мөр ашиглах хэрэгтэй байсан. Цааш нь while(sum>9){ bla bla} . Done.

2013-04-19 07:28:44 Онлайн 1 олимпиадын анализ by Bataa

“Олимпиад 1”

http://spoj.com/RGBC1 2013.4.8 15:00-18:00

Анализыг "Шинэ Монгол" ахлах сургуулийн 12-р ангийн сурагч Гантөмөрийн Золжаргал.

A. Гурван тооны ХБЕХ
2 тооны хамгийн бага ерөнхий хуваагдагчыг Евклидийн алгоритм ашиглаж олвол

ХБЕХ(a,b)= a*b/XИЕХ(a,b)
болно. :) LCD1-г олох функц нь GCD2-г олохоос амархан тул энийг ашиглав. K= ХБЕХ(a,b) гэвэл бодлогын хариу Ans = ХБЕХ(c,K) байна.

B. Хагас дугуй

Эхлээд цэг маань тойргийн төвөөс дээш орших эсэхийг шалгах хэрэгтэй. y1>y0 байна. Хэрвээ тийм бол байвал тойргийн төв ба цэгийн хоорондох зай нь радиусаас бага эсэхийг шалгахад бодлого бодогдоно. Анхаарах зүйл нь зайг олохдоо язгуур авснаас (x1-x0)^2+(y1- y0)^2 <= r*r гэж шалгавал зүгээр. Бутархай тоо ашиглахгүй байвал зүгээр.

C. Кенгуру

Иймд кенгеру сүүлийн үсрэлтээр 2^T метр үсэрсэн гэвэл өмнөх бүх үсрэлтийн нийлбэр хамгийн ихдээ (2^T-1) байх боломжтой. Тийм болохоор кенгеру сүүлийн үсрэлтээ N-д хамгийн бага, 2-н зэрэгт хэмжээтэй хийнэ. Мэдээж баруун чиглэлээр. (N-с их хэмжээтэй үсэрвэл хэзээ ч очих ёстой цэг дээрээ очиж чадахгүйг хялбар баталж болох байх). Ингээд эндээс өмнөх бүх үсрэлт нь +/- чиглэлтэй хийгдэх бөгөөд, хойноос нь хөөж бодвол олдоно. Үсрэлт бүрийн дараа эхлэл цэгээс холдох тул бодолт хийхдээ эхлэл цэгрүү аль болох дөхүүлээд байхад болно. Жишээ нь : Эхлэл цэгээс +8м зайтай байвал сүүлийн үсрэлтийг “+” -р хийсэн, -5м зайтай байвал сүүлийн үсрэлтийг “-”-р хийсэн гэх мэт.. 1м үсрэлт хийсэн тэмдгийг тооцсоны дараа эхлэл цэг дээр биш байвал “Impossible” . Үсрэлт болгоны чиглэлийг нэг массивт хадгалчихвал дараа нь хэвлэхэд амар болно.

D. Шилжилтүүдийн хамгийн их

Жишээгээр үзвэл: Анх “123” гэж тэмдэгт өгсөн бол “123123” болгож залгаж байгаад эхнээс нь яг 3 урттай тэмдэгтүүд тасалж аваад байвал 123,231,312 гээд хэрэгтэй тэмдэгт мөрүүд шууд гарч ирнэ.. Мөн string бүтэцтэй өгөгдлийг утгаар нь харьцуулж болдог.

string a;
string b;

if(a>b) printf(“a > b”);

Энэ харьцуулалт яг тоо харьцуулж байгаа мэт ажиллана. :) Хэрвээ энэ нөхцөл биелэлэв тэр стрингээ өөр нэг газар хадгалчихвал болчихно.

1 LCD – largest common denominator. ХБЕХ
2 GCD – greatest common divisor. ХИЕХ

E. Хаалт зөв эсэх

Шууд тоолчихвол болно. Илэрхийллийн эхнээс тоолоод “)” хаалтын тоо нь “(“ хаалтын тооноос олон байх үед цааш үргэлжилнэ. Илэрхийллийг шалгаж дууссаны дараа нийлбэр нь тэнцүү байх ёстой.

for(a=0;a if(mas[a]==')') cnt++;
if(mas[a]=='(') cnt--;

if(cnt<0) ans=0;
}
if(cnt!=0) ans=0;
else ans=0;

2013.04.10

2013-04-14 04:59:26 Онлайн 3 олимпиад by Bataa
Оролцогчдын хүсэлтээр онлайн 3-р олимпиадын эхлэх цагийг хойшлуулж 2013 оны 4-р сарын 17-ны 20:00-23:00 цагийн хооронд 8 бодлоготойгоор www.spoj.com/RGBC3 дээр явуулав.
Бүх бодлогоо амжилттай бодсон Б.Говьхүү, Г.Золжаргал, Мөнхбаатар нартаа баяр хүргэе. Алгоритм багаас зохион байгуулж буй онлайн олимпиадад Г.Золжаргал 3 дахь удаагаа бүх бодлогоо хугацаанаас нь өмнө амжилттай бодлоо. Дэвшигдсэн бодлогууд : RGB7260, RGB7270, RGB7271, RGB7340, RGB7350, RGB7677, RGB7710, RGB....
Удахгүй онлайн 4 олимпиадыг зарлана. Энэхүү олимпиадаас эхлээд оролцогчид олимпиад дууссанаас 24 цагийн дараагаас эхлэн бие биенийхээ бодолтыг үзэх боломжтой болно. Амжилт хүсье.
Алгоритм баг.
Багш Ц.Баттогтох

2013-04-14 04:36:33 Улсын олимпиадын 2-ын даваа by Bataa
2013 оны 4-р сарын 11-ны өдөр болсон улсын олимпиадын 2-ын даваа буюу аймаг, нийслэлийн аварга шалгаруулах багш, сурагчдын олимпиадад ирсэн бодлогууд.
Багш нарт : RGB7178 , RGB7373 ,RGB7583 .
Алгоритм баг.
Багш Ц.Баттогтох

2013-04-11 14:26:04 Онлайн 2 олимпиадын дүн by Bataa
"Алгоритмын цагаан толгой" сайт хэрэглэгчдийн дунд 2 дахь онлайн олимпиад 2013 оны 04-р сарын 10-ны 15.00-18.00 цагийн хооронд www.spoj.com/RGBC2 сайт дээр 9 бодлогоор амжилттай болж өнгөрлөө. Тэмцээнд 42 багш, сурагчид оролцлоо. Г.Золжаргал дахин бүх бодлогыг бодож аваргалаа. 2-р байрт Баярхүү 8 бодолтоор, 3-5-р байранд silent, George_teller, Khongor нар 6 бодолтоор тус тус шалгарлаа. Баяр хүргэе.
Онлайн 2 олимпиадад дэвшигдсэн бодлогууд : RGB7176, RGB7177, RGB7372, RGB7390, RGB7552, RGB7582, RGB7680, RGB7193, RGB7376.
Удахгүй 3 дахь тэмцээнийг зарлана.
Алгоритм баг.
Багш Ц.Баттогтох

2013-04-08 11:27:06 Онлайн 1 олимпиадын дүн by Bataa
"Онлайн олимпиад 1" 2013 оны 4-р сарын 8-ны 15:00-18:00 цагийн хооронд www.spoj.com/RGBC1 сайт амжилттай болж өндөрлөлөө.
Тэмцээнд оролцсон нийт 25 оролцогчдоос, дэвшигдсэн 5 бодлогыг 5-ууланг нь хугацаанаас нь өмнө бодож түрүүлсэн Г.Золжаргалд баяр хүргэе. Мөн оролцсон нийт багш, сурагчиддаа баярлалаа. Дараагийн тэмцээнд нь амжилт хүсье.
Анхдугаар тэмцээнд дэвшигдсэн бодлогууд : RGB7175, RGB7192, RGB7290, RGB7316, RGB7590 болно.
Алгоритм баг.
Багш Ц.Баттогтох

2013-04-08 08:43:37 Үндэсний дээд сургуулийн ЕБС олимпиад 2013 он by Bataa
Үндэсний дээд сургуулийн нэрэмжит ЕБС-ийн сурагчдын 2013 оны олимпиадын бодлогууд.
RGB7374,RGB7375, RGB7460.
Алгоритм баг.
Багш Ц.Баттогтох

2013-04-06 11:11:00 Нийслэлийн дүүргийн ЕБС-ийн 2013 оны олимпиад by Bataa
Нийслэлийн ЕБС-ийн дүүргийн 2013 оны олимпиадын бодлогууд.
RGB...
"Алгоритм" баг.
Багш Ц.Баттогтох

2013-01-06 14:35:15 Талархлын хариу by Bataa
RGB7 сайтад бодлого бодож байгаа алгоритм програмчлалын бодлого сонирхогч, эхлэн суралцагсдыг дэмжих зорилгоор бодлогуудыг ангилж оруулахаар зориглон оролдож байгааг маань хүлээн авна уу? Тухайлбал :
  RGB70.. Шугаман алгоритмын
  RGB71.. Салаалалтын
  RGB72.. Параметрт давталтын
  RGB73.. Нөхцөлт давталтын
  RGB74.. Давхар давталтын
  RGB75.. Массивын
  RGB76.. Динамик програмчлалын
  RGB77.. Графын
гэх мэт бүлгүүдэд хуваагдана. Бүлэг бүр 100 бодлоготой байх юм.
Бүлгүүд нь дотроо бүхэл тоон, бодит тоон, тэмдэгт, олимпиад төрлийн гэх дэд бүлгүүдэд хуваагдана.
Жишээ нь : RGB7170, RGB7171 бодлогууд нь салаалалт бүлгийн олимпиад төрлийн бодлогууд болно.

Санал бодлоо gipsymn@yahoo.com ирүүлнэ үү.

Хүндэтгэсэн
Багш Ц.Баттогтох