Мэдээлэл зүйн улсын олимпиад, сурагчидын 2 дугаар өдрийн бодлогын бодолтууд

Бүх оролцогчидод баяр хүргье. Мундаг байсан шүү та нар.



Өөрийн бодолтоо анализын хамт сонирхуулая:



1-р бодлого:

Өгүүлбэр: Утгаараа мянгаас хэтрэхгүй N (N<=10^6) ширхэг тоон дараалал өгөгдсөн. Q (Q<=10^1) ширхэг хүсэлтэнд хариулах ба энэ нь дээрх дарааллын A, B индэкс завсарт байрлаж байгаа тоонууд дунд хамгийн их давтагдсан, хамгийн бага давтагдсан мөн нийт хичнээн ялгаатай тоо байгааг олох юм байна. Жишээнээс тодорхой форматыг нь харна уу

input:

10

5 5 5 5 6 4 1 2 20

3

mn 1 10

mx 1 10

ct 1 10

output:

1

5

7



Анализ:

Миний хувьд энэ бол хоёр дахь өдрийн хамгийн хүнд бодлого. Гэхдээ, нийт хүсэлтийн тоо хамгийн ихдээ 10, утгаараа тоонууд нь мянгаас бага гэхээр хүсэлт болгонд A-аас B дунд гүйгээд тоолчиж болно. Тоолохдоо a[1000] урттай массив авж байгаад i гэсэн тоо орж ирвэл a[i]++ нэмээд байна гэсэн үг. Хүсэлт болгонд A=1, B=10^6 байж болох тул O(N)-д хариулна. Нийт бодолтын үнэлгээ O(Q*N) буюу 10-н сая үйлдэл хангалттай 0.3 секундэд амжиж байгаа юмшиг байна.

O(M*Q*logN) бодолт сонирхоё, мөн бичихэд маш хурдан нь.

1...M ширхэг массив авая. Тухайн k дугаар дахь массив бүрт уг к тоо маань хэд хэд гэсэн индекст байрлаж байгааг нь хадгалчия. Яг орж ирсэн дарааллаар нь массивын араас нь элементээ нэмээд явахад эрэмблэгдсэн массив үүснэ. Тэгвэл одоо хүсэлт A B орж ирэхэд бүх массив дотор хоёртын хайлт хийнэ. Ойлгомжтой болгохын үүднээс зөвхөн макс-г нь олоё. lower_bound(left, right, k) функц нь к дахь массивт (left, right) завсарт багтах тоонуудын хамгийн багых нь дугаарыг олно.

upper_bound(left, right, k) нь уг завсарт багтах тоонуудаас хамгийн ихийх нь дугаарыг олно.

Одоо ингээд dif = upper_bound(left, right, k)-lower_bound(left, right, k) - г бүх k-н хувьд минимумчилна гэсэн үг.

source - хоёртын хайлтыг чөлөөтэй бичдэг байх хэрэгтэй шүү!



Бодлого 2:

Өгүүлбэр: дараах байдлаар нийлбэрийг задласан юм байна. Аль нэгэн нийлбэр нь өгөгдөхөд доорх нийлбэрийг нь ол.

Анализ: нийлбэр үүсгэж байгаа гишүүдийг нь эхнээс нь массивт хийцэн гэж үзье. Зөрөө нь хоёроос их байх хамгийн эхний дараалсан хоёр гишүүний олъё k, k+1 гэе. Уг хоёр гишүүн хүртлэх гишүүдийн нийлбэрийг мэднэ гэж үзье. Одоо к дахь гишүүнээ нэгээр нэмэгдүүлээд уг хоёр гишүүн хүртлэх гишүүдийн нийлбэрийг бүх гишүүдийн нийлбэрээс хасая diff гэе. Одоо бид diff-г аль болох урт мөн хамгийн эхний гишүүн нь k дахь гишүүнтэй тэнцүү байхаар задлана гэсэн үг. Бодолтоос дэлгэрэнгүй харна уу.

source

Бодлого 3:

Зөвхөн N ширхэг 1 байхад хэд гэсэн тоог гаргаж авч чадах вэ? N*(N-1)/2

Зөвхөн M ширхэг -1 байхад хэд гэсэн тоог гаргаж авч чадав вэ? M*(M-1)/2

Одоо тэгвэл N ширхэг 1 мөн M ширхэг -1 байхад хэд гэсэн тоог гаргаж авч чадах вэ?

N*(N-1)/2 + M*(M-1)/2 - N*M.

S өгөгдөхөд S=N*(N-1)/2 + M*(M-1)/2 - N*M байх M-г ол гэсэн бодлого. N, S-г мэдэж байгаа тул квадрат тэгшитгэл бодоод M-г олно. Гарсан хоёр язгуурын аль нь манай хариу болж болох бол? бодоод үзээрэй.

source



За нэг иймэрхүү. Надад эхний өдрийн бодлогууд олдвол ингээд анализ хийчиж болох л байх.

Зөвлөгөө

Хүнд бодлого бодохын ач тус байхгүй



Хорвоо дэлхийн бүх бодлогуудыг түвшингээр нь 1, 2, ..., N гээд дугаарлая (N мэдээж төгсгөлгүй жижиг тоо, өө бишээ том тоо, гэхдээ тэр төгсгөлгүй том тоо чинь төгсгөлгүй том тоон ширхэг төгсгөлгүй том тооны хажууд төгсгөлгүй жижиг тооштэй? парадоксуу эсвэл харьцангуйн онол уу? за тэр яахав). Дугаар нь том тусмаа хүнд бодлого гэж үзье. Би өмнөх постын төгсөлд бичсэнчлэн ямар нэгэн бодлогонд 24-н цаг зарцуулаагүй л бол хүнд гэж бууж өгөх хэрэг байхгүй.



-xx-: 24-н цагийн дараа бодож чадсангүй, яах уу дурак аа?

-Baska-: kk цагаа л дэмий үрлээдээ хө.

-xx-: ямар хогийн хариулт вэ?



Манай 10-н жилийхэн, оюутнууд өөрсдөө нэгэнт хүнд бодлого барьж аваад байдаг болохоор би аргаа бараад ингэж зөвлөсөн юм. Яс юман дээрээ тэр 24-н цагтаа эргэлзээтэй сэдвүүдээ бататгаад эсвэл амархан санагдах бодлогуудаа бодсон бол тэр хүнд бодлого бодох хугацаагаа арай наашлуулах л байсан байх. Ер нь бол бүх зүйл явж явж рефлэкс байдаг шиг санагдаад байгаа, бодит амьдрал дээр ч тэр. Хэн асар их тооны бодлого бодно тэр хүн хурдтай сэтгэж хурдан бодно. Олимпиадын үеэр шинэ юм сурна гэж байхгүй, юу чаддагаа л хийдэг газар, чаддаг зүйлээ хэдэн мянга давтаж байж өөрийн болгож авна ингэж байж тэрийгээ хэрэгтэй газар нь хийж чадна.



-xx-: Олимпиадад хэн түрүүлж чаддаггүй вэ?

-: бодлогыг амархан гэж орхисон нөхдүүд л цагаа тулахаар чадах юмаа хийж чадаагүйд л байдагштээ.

-xx: Маш энгийн юмыг мартчихсан байдаг штээ? энэ нь би муу гэсэн үг биш :(

-x: чи энгийн юмыг энгийн гэж бодоод хаясан л байхгүй юу.



-xx-: Тэгээд дандаа амархан бодлого бодох ёстой юмуу?

--: Мэдээж чи ном уншдаг болчоод үсэг цээжлэх дасгал хийнэ гэж байхгүй. Амархан бодлого бодох ёстой гэдэг нь К түвшний бодлого бодчоод K+1 түвшнийхийг л бодох хэрэгтэй.



-xx-: Яаж дараагийн түвшний бодлогыг олох вэ? надад багш байхгүй, би ганцаараа..

Энэ ганцаараа гэдэг зүйл яг манайд их түгээмэл ярьдаг шалтгаан. Манайд гэдэг нь мэдээлэл зүй, програмчлалд шүү.


Одоо гэхдээ нэг таатай зүйл нь бодлогын маш олон онлайн сайтууд байна. Бүгд тухайн ямар нэгэн бодлогыг хэдэн хүн бодсон, хэдэн хүн оролдоод хэд нь бодсон гээт статистикууд байгаа. Эдгээрийг нь харж байгаад хамгийн их хүн бодсоноор нь эрэмблээд бодвол арай цэгцтэй цаг хэмнээд маргааш гэхэд нэгнээсээ түрүүлж алхах л байх шүү.



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



10-н жилийхэн надаас бодлого их асууж холбогдож байгаа. Сайн байна, юм хийх гээд л байна гэсэн үг. Гэхдээ бүгдэнд нь нэг дутагдал байна. Дандаа маш хүнд бодлого барьчихсан байдаг. Би зааж өгөөд бодолтыг нь хэлсэн ч бай эндээс үлдэх юм юу л бол. Улсын олимпиадад орох гэж байгаа бол заавал улсын олимпиадын бодлого бодоод байх хэрэг байхгүй. Тэднарыг чаддаг ч байх албагүй. Гол нь чи мэдэх юмаа баталгаатай чаддаг л байх хэрэгтэй.



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



Гэхдээ ичиж санаа зовох зүйлгүй аль болох нээлттэй сайн юм асууцгаагаарай.

За амжилт хүсье.



(Зөвхөн олимпиад тэмцээн, алгоритмд дуртай хүмүүст зориулж энэ постыг бичлээ. Битгий тэгээд тэмцээн уралдаан нэг нэгнийхээ дээр гарах ямар хэрэгтэйн гээд нэгнээ шүүмжлээд байгаарай. Энэ бол шал өөр сэдэв болно)

Тэмцээн 2016 бодолтууд

За тэмцээнд оролцсон бүх оролцогчиддоо их баярлалаа. Сайн байсан шүү та нар бүгдээрэй.



Шууд анализдаа ороё. Мөн C++ код тавьлаа. Аль болох ойлгож мөн хэлнийхээ мэдлэгийг сайжруулах үүднээс ямар асуудлыг яаж шийдэж гэдэг байдлаар код уншаарай. Амжилт



Bodlogo 1

Байж болон хамгийн том тоо 10^9 - г хоёртын тоололруу шилжүүлэхэд 30-н оронтой тоо гарна. Гуравтын тоололд шилжүүлэхэд мөн хамаагүй бага оронтой тоо гарна. Бүх боломжийг шалгахад O(2*30*30) аас ихгүй үйлдэл хийнэ, энэ хугацаандаа хангалттай амжих бодолт. Гол асуудал нь дурын тоо өгөгдөхөд хоёртуу мөн гуравтын тоололруу шилжүүлдэг байх хэрэгтэй.

source



Bodlogo 2

Энэ бас л шууд хэлснийг нь хийхэд болох бодлого. A олонлогоо шууд эрэмблэе. Одоо M тоон дарааллын C урттай дараалалсан гишүүд болгоныг тусад нь эрэмбэлээд A олонлогийн харгалзах дугаартай элементүүдийн зөрүү бүгд тэнцүү байх ёстой. Бодолтын хугацаа O(10*N) = O(N).

source



Bodlogo 3

Рекурс ашиглаад хоёр арлаа 0, 1-ээр ялгаад будчиж чадна. Үүсэх графын хязгаарлалт бага тул шууд бүх хоё 0 1-үүдийн хоорондох зайг олоод хамгийн багыг авчихад болно.

source



Bodlogo 4

Бас л шууд хэлснээр нь хийгээд шалгачина. Нэг асуудал нь тухайн толь дээр хаанаас нь ирснийг мөн ямар толь байвал хаашаа явахыг нь яаж мэдэх вэ? тухайн ямар нэгэн x гэсэн нүдний хувьд чиглэлүүдийг нь дараах байдлаар тодорхойлоё.

  2

3x1

  0

Одоо bounce1[i]=k-аар '/' ингэж тавьсан толинд i чиглэлээс ирэхэд к чиглэлрүү явна гэдэгийг нь тэмдэглэе.  Мөн bounce2[i]=k-аар '\' толинд i чиглэлээс ирэхэд к чиглэлрүү явахыг тэмдэглэе.

Мөн xx[]={1, 0, -1, 0}, yy[]={0, 1, 0, -1} энэ хоёр массивыг ашиглаад x+xx[k], y+yy[k] гэсэн k чиглэлрүү очиж чадна.

source



Bodlogo 5

dictionary дахь үгнүүдийг өөрийх нь байрлалтай нь хамт хадгалаад үгнүүдийх нь хувьд эрэмбэлэе. prefix үг орсон байх үгний хамгийн эхнийхийг нь хоёртын хайлт хийж дугаарыг нь олоод k-г нэмэхэд гарах үгний prefix нь манай хайж байгаа prefix-тэй тэнцүү байна уу гээд шалгачина. Бодолт O(NLogN+q*LogN).

source



Bodlogo 6

Ямар нэгэн түвшинд байгаа (x, y) цэг нь дараагийн түвшиндээ (2*x, 2*y) координадтай болно

source



Bodlogo 7

Энэ бол "two pointers" гэх ангилалд орох сонгодог бодлого. start, end гэх интервал аваад явъя. Тухайн өнгийг одоогийн интервалд хэд орсныг нь мөн тоолно. Бүх өнгө ортол end=end+1 гэе. Одоо start дээр байгаа өнгийг хассан ч бүх өнгө ядаж нэг орсон байвал start=start+1 гээд байя. Одоо end-start манай хариу байж магадгүй тул өмнө олсон хариунаас их бага эсэхийг шалгаад болоо.

source



Дараагийн маш сонирхолтой бодолт бол өнгө болгоны хувьд хамгийн сүүлд олдсон байрлалыг нь хадгалаад явна, A-д хадгалав. Өнгө бүрийн хувьд хамгийн анхны утга нь -INF байг. Одоо бөмбөлөг байгаа цэг бүрийн хувьд эхнээс нь гүйх ба (х цэг) тухайн өнгөний байрлалыг нь шинэчилчээд үүний дараа A-н хамгийн бага утгыг олоод min гэе. x-min манай бодлогын хариу байж магадгүй. Тэгэхээр энэ бодолтын хувьд A-г шинэчлэх мөн хамгийн бага утгыг хангалттай хурдан олж чадвал, heap, O(NLogN)-д бодогдно.

source

Гэвч дээрх хоёр бодолт хоюулаа хамгийн эхний үйлдэл нь цэгүүдээ эрэмбэлэх тул O(NlogN)-г би дурьдсангүй шүү



Bodlogo 8

Энэ бодлогын хариуг бид олохын тулд хоёр зүйлийг минимумчлал ёстой.

1: Аль ч аралд харьяалагдахгүй бүх цэгийн 3-н арал хүртлэх зайнаас хамгийн багыг нь олоё. Үүнийг 3*2500-д олж чадна. Үүнийгээ m1 гэе

2: 1-р арлаас 2-р арал хүртлэх хамгийн богино зайг (1, 2), 2-оос 3-г (2, 3), 1-ээс 3-г (1, 3) гэе. Энэ 3-н аль нэг хоёрын нийлбэр нь мөн манай хариу болж магадгүй, үүнийг m2 гэе. 2500^2-д олж чадна



Бодлогын хариу min(m2, m1).

source



Bodlogo 9

Энэ бол dp. Best[i][j]-ээр i гэсэн тоог 1..j хүртлэх гишүүдийг ашиглан зардал хамгийн бага байлгахыг тэмдэглэе. Тэгвэл Best[i][j] = min(k-A[k])^2+Best[i-k*k][j-1], (1..k k*k<=i)

source



Bodlogo 10

Энэ бодлогыг та бүхнийг өөрсдөө дахин сайн нухаж бодохыг хүсэж байна. Ер нь ямар нэгэн бодлого дээр 24-н цаг суугаагүй л бол хэцүү бодлого гэж хэлэхгүй шүү



За асуух юм байвал комментоор асууж бариараа. Амжилт хүсье.

Тэмцээн 2016

UPDATE: Тэмцээн болох хаяг



https://www.hackerrank.com/mongolian-pupils



За тэгэхээр www.algorithm.mn гэсэн хаягаа авч чадсан тул тэмдэглээд тэмцээн зохиохоор шийдлээ.



Зорилго:

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



Хэзээ:

Энд дарна уу. Улаанбаатарын цагаар шүү



Тэмцээнээ hackerrank дээр зохиох байх, хэдэн өдрөөс линкийг нь тавина. Бодлогуудын хувьд 10-н бодлоготой 5-н цагийн хугацаатай болно. Бодлогын түвшин нь амарханаас хүндрүү байх болно тэгэхээр хамгийн эхний бодлогууд амархан тэгээд хүндрэнэ шүү. Хамгийн хүнд бодлого нь олон улсын мэдээлэл зүйн олимпиадын хамгийн амархан бодлогын түвшинд байх тул тийм ч хүнд тэмцээн болохгүй байх. Улсын олимпиадын өмнөх сорилго гээд ойлгочихоорой.



Шагнал: эхний 5-н байрт шалгарсан монголд байдаг "хүн төрлхтөн"-д доорх подволкыг өгнө өө. Би өөрөө зунаас очиж шагналаа өгөх байх шүү.

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

Мат - 2

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



Миний постуудад бодлогууд ерөнхийдөө амарханаас хэцүүрүү эрэмблэгдэж байгаа шүү.



1799 - Бодит 1<=R<=100 болон бүхэл 2<=n<=100 хоёр тоо өгөгдсөн. R радиустай тойрог дотор зурагт харагдаж байгаа шиг n ширхэг ижил радиустай тойрог хооронд нь ямар ч зайгүй тавих гэж байгаа бол тэр тойргийн радиусын хамгийн уртыг нь ол. Оролт гаралтых нь форматыг өөрсдөө хараад ойлгочоорой.



1401 - 1<=N<=10^9 өгөгдөхөд N! сүүлийн хэдэн орон нь тэг байхыг тоолно уу.



2262 - 1<=N<=10^6 тоо өгөгдөхөд уг тоо a+b гэсэн хоёр анхны тоонд тавигдах эсэхийг ол. Тавигдах бол хоёр тоог N = a + b форматтай хэвлэнэ үгүй бол "Goldbach's conjecture is wrong." гэж хэвлэ. Хэрэв бодлого олон хариутай бол (b-a) хамгийн их байхыг нь хэвлэнэ.



2242 - 3н цэг координат нь өгөгдсөн бол уг гурван цэгийг дайрах тойргийн радиусыг ол. Координатуудын утга саяас хэтрэхгүй.



1654 - Зөвхөн 8 2 6 4 9 7 3 1 5 аас бүрдэх тэмдэгт мөр өгөгдөв. 8-хойд,  7-баруун хойд, 4-баруун , 1-баруун урд, 2-урд, 3-зүүн урд, 6-зүүн, 9-зүүн хойд тус тус илэрхийлэх ба координатын систем дээр аль нэг цэгээс эхлээд тухайн тоонд харгалзах зүгрүү нэг нэг нэгжээр хөдлөж олон өнцөгт үүсгэнэ. Үүсэх олон өнцөгтийн талбайг ол. 5 гэсэн тоо нь хөдлөж дууссныг илэрхийлнэ.



2084 - 1<=n<=100 өгөгдөхөд 1 2 .. 2n-1 2n гэх байдлаар цагийн зүүний дагуу тойрог үүсгэн бичив. Тоо бүрийг яг нэг өөр тоотой харгалзуулан шулуун татав, ингэхдээ шулуунууд хоорондоо огтлолцохгүй. Нийт хичнээн янзаар шулуун татаж болох вэ?



1426 - 1<=n<=200 өгөгдөхөд аравтын бичлэг нь зөвхөн тэг эсвэл нэгээс бүрдэх n=q*m+0 байх m-г ол. Бодлогын хариу 100 оронгоос бага байна.



За амжилт.

Мат

За анхны тооноос эхлье даа.

- N натурал тооны хамгийн бага анхны тоон хуваагч нь түүнээс язгуур авсан sqrt(n)-ээс хэтрэхгүй. Эндээс харвал тухайн тооны язгуур хүртлэх бүх тоон дунд ядаж нэг тоо N-г хувааж байвал энэ тоон анхны тоо биш.

- Дараагийн түгээмэл хэрэглэгдэх бодлого бол N хүртлэх бүх анхны тоог олох.

Монголоор анхны тоон тор гэж нэрлэдэг. Sieve-н алгоритм нь дараах байдлаар ажилдаг.

N хүртлэх бүх тоог анхны тоо гэж үзье. i тоологчоо 2-оос эхлээд N хүртэл гүйлгэе. Ингэхдээ хэрэв тухайн i тоо анхны тоо байвал түүнд хуваагдах өөрөөс нь бусад бүх тоог ахны тоо биш болгоно. i=N үед үлдсэн тоонууд анхны тоонууд байна. Алгоритм ингээд болоо.

Дасгал асуулт: i-г хэд хүртэл гүйлгэхэд хангалттай вэ? Мөн ажиллах хугацааны үнэлгээг олно уу.

- Өгөгдсөн хоёр тооны, a b, хамгийн их ерөнхий хуваагчийг ол. Үүнийг англиар greatest common divisor (gcd) гэнэ. a, b хоёрыг хоюуланг нь хуваадаг хамгийн том тоог ол л гэсэн үг. Brute-force хийж үзье.

a = b*q+r хэлбэрт тавигдана. r тэгээс ялгаатай байвал b r хоёрын gcd нь манай бодлогын хариу болно. Иймээс дараах рекурсив функцыг бичиж чадна. Нэг жишээ ажиллаж үзье.

gcd(2336, 1314) ?

2336 = 1314*1 + 1022

            1314 = 1022*1 + 292

                        1022 = 292*3 + 146

                                    292 = 146*2 + 0

- a, b хоёр тоо байхад gcd(a, b) = x*a + y*b байх x, y хоёр тоо олдно. x, y-г олно уу.

Бодолт: a = q*b + r, r!=0 үед gcd(a, b) = gcd(b, r) = b*x` + r*y` байх x`, y` хоёр тоо олдно гэсэн үг. Тэгэхээр:

r = a-q*b

gcd(a, b) = b*x` + r*y` = b*x` + (a-q*b)*y` = y`*a + (x`-q*y`)*b

эндээс

x = y`

y = x` - q*y`

гэсэн үг. Үүнийг өөрөө сайн хийж харна уу!!

- Модулар алгебра.

Чанар болон онолын зүйл бичилгүй шууд хамгийн хэрэглээтэй бодлого бодолтыг нь бичье.

Энгий алгебрад a!=0 байх a нь дурын b-н хувьд a*b=1 байхаар цор ганц утгатай тодорхойлогддог. Харин модулар алгебрад ийм байх албагүй. Жишээ авч үзье.

a=2, mod 26 үед хариу байхгүй. Дээрх b тэгшитгэл биелэх b тоог a-н урвуу тоо гэж нэрлэдэг.

Дараах тоон олонлогийг авч үзье.

Zn = {x E {0..n-1}: x болон n -үүд харилцан анхных}

Зөвхөн Zn харьяалагдах тоонууд урвуу тоотой байна. Батлаарай!

Урвуу тоог олох бодлого нь x*a + y*b = 1 тэгшитгэлд a = a, b=N тавиад дээрх код хүчинтэй.



- Хятадын үлдэгдэлтэй хуваах теорем.

Маш энгийнээр бол a, b, m, n gcd(n, m)=1 бол x=a(mod m) x=b(mod n) байх x-г ол.

Бодолт:

n^(-1) - г n-н урвуу тоо

m^(-1) -г m-н урвуу тоо

тэгвэл x=a*n*n^(-1) + b*m*m^(-1) байна.



source



За маш энгийн болоод маш товч бичлээ. Асуух зүйлүүдээ комментоор бичээрэй. Дуртай хариулна. Матын бодох бодлогуудыг маргааш тавина. Амжилт.

Хамтдаа хөгжицгөөе

Зав зай арай гайгүй болсон дээрээ хэдэн юм хүүхдүүдэд заагаад өгье гэж хэдэн материал бэлдлээ. Доорх хэдэн сэдэв дээр шаардлагатай онол, алгоритмыг заагаад 8-10н бодлого бэлдсэн байгаа. Шууд онлайн линкийг нь тавих болно, гэхдээ би өөрөө бодлогын өгүүлбэрийг нь орчуулаад блог дээрээ тавина, мөн бодолтын ерөнхий санаа, анализыг нь хэлж өгнө, шаардлагатай гэвэл C++ дээрх бодолтоо тавина.

1. Coding exercise - энд нээх онол шаардахгүй, гэхдээ хоёртын хайлт гэх мэтчилэн арга техникууд хэрэгтэй, гэхдээ зөвхөн анхан шатны мэдлэг л хэрэг болно.

2. Mathematics - Хэрэгтэй мат-уудыг шаардах бодлогууд байх болно. Мэдээж эхлээд өөрөө тайлбарлана.

3. Data Structures - өгөгдөлийн бүтэц

4. Dynamic programming - динамик програмчлал

5. Basic graph algorithms - графын энгийн алгоритмууд

6. Shortest Path algorithms - богино замын алогритмууд

7. String Algorithms

8. Computational Geometry



Бодлогууд бүгд http://poj.org/  - дээр байгаа тул энд бүртгүүлнэ үү.



За шууд эхний сэдэв болох Coding Exercise-руу ороё



Энд онол гэх заагаад байх юм байхгүй байх. Гэхдээ миний блогийг доош нь гүйлгээд C++ STL I, II гэсэн пост мөн бодлогуудын анализуудыг уншчихад гэмгүй.



Доорх бодлогуудыг бодно уу.

1004 - Нэгэн хүний сүүлийн нэг жилийн сар бүрийн орлого өгөгдсөн бол тухайн жилийн орлогын дундажийг олох. Оролт 12 ширхэг бутархай тоо, гаралт бодлогын хариултыг 2 орны нарийвчлалтай  $тэмдэгийн араас шууд хэвлэнэ.

Анализ: Оролтын бүх тоог нэмээд 12т хуваах байх аа.

source

----

1003 - Зурагт үзүүлсний дагуу N хөзрийг хөзрийн урттай тэнцүү урттай тавцан дээр давхарлан унагалгүй байж болох хамгийн уртаар нь дээр дээрээс нь тавив. Ингэхийн тулд хэрэв нэг хөзөр байвал тавцангийн 1/2 хэсэг дээр хөзрөө тавина, хэрэв 2 хөзөр байвал хамгийн доод талын хөзрийг тавцангийн 1/3 дээр, 2дахь хөзрийг 1дэх хөзрын 1/2 дээр тавьснаар 1/2+1/3=5/6 уртыг үүсгэж чадна. Ерөнхий тохиолдолд N хөзөр байхад 1/2+1/3+..+1/(N+1) урт үүсгэж чадна гэж үзье. Тэгвэл с гэх ганц бутархай тоо өгөгдсөн бол ядаж с урт үүсгэхийн талд хамгийн багадаа хичнээн хөзөр хэрэгэй болохыг олно уу.

Оролт нь олон тестээс бүрдэх ба 0.00 үед тест дуусна. Мөн тест бүр [0.01;5.20] байна.

Гаралт нь мөр бүрт тухайн тестийн хариуг нэг мөрөнд хэвлэнэ.

Анализ: с тоо хамгийн ихдээ 5.20 тул бодлогын хариу тийм ч том тоо биш байгаа нь харагдах байх. Тэгвэл шууд К-г 1-ээс авахуулаад тухайн К хөзөр с-ээс их буюу тэнцүү хүртэл урттай байх хүртэл нь шууд хайгаад явчихад болно. Энэ хайлт нь утга бүрийг нэг бүрчилэн шалгаж байгаа тул шугаман хайлт гэж нэрлэж байгаа юм. Код дээр search_linear гэсэн функцыг харна уу. Энэ бодолт шууд давна, бодлогын хязгаарлалт хамаагүй бага байгаа тул O(K). Ерөнхийдөө бодлогыг бодож, тухайн хязгаарлалт, хугацаанд амжуулж л байвал болоо гэсэн бодолтой байх хэрэгтэй. Хамгийн чухал нь юу сурч авав гэдэгээ байнга эргэж харж байгаарай.

Бодолтыг илүү хурдан болгож чадах уу? Хоёртын хайлт ашиглана. Бид К-г хамгийн багадаа 1, хамгийн ихдээ -276 гэдэгийг эхний бодолтыг хийгээд харчиж чадна.

compute_length(N) гэсэн функц нь N ширхэг хөзөр өгөгдсөн үед үүсгэж чадах уртыг нь олдог байг. Тэгвэл бодлого маань c<=compute_length(K) байх хамгийн бага К-г ол гэсэн үг. Тэгэхээр К маань өөрөө 1-ээс 276-н хооронд байж болох тул энэ завсарт хоёртын хайлтыг хийнэ гэсэн үг. O(Log(K)).

source

--

1007 - зөвхөн A C G T гэсэн тэмдэгтүүдээс бүрдэх n урттай m шихрэг тэмдэгт мөрүүд өгөгдсөн. Тэмдэгт мөр бүрийн хувьд К гэсэн тоог бодож олно. Энэ нь ямар нэгэн с тэмдэгт нь хичнээн ширхэг өөрөөс нь урд байрлах ёстой тэмдэгтийн урд байрлаж байгаа вэ гэдэгийг тоолно. Тухайн тэмдэгт мөрийн хувьд бүх тэмдэгтүүдийн хувьд дээрх тоог олоод нэмэхэд гарах утгаар К-г тодорхойлно. Тэгвэл тэмдэгт мөр бүрийн хувьд К-г бодож олоод К-уудын хувьд өсөхөөр эрэмблэ гэсэн бодлого. Жишээг нь сайн харж бодлогоо бүрэн ойлгоно уу.

Анализ: Хамгийн энгийн бодолт бол C++ дээр compare функц үүсгэж эрэмблэх бодлого.

source

Анализ2 К-г ямар нэгэн тоон дарааллын хувьд инверс тоо гэдэг. Бидний өмнөх бодолт маань бүх хосуудыг шалгаж байгаа тул хугацааны үнэлгээ нь квадрат O(N^2). Үүнийг рекурс ашиглан O(NlogN)-д бодож болно. Үндсэн санаа нь

F(S) функц нь S-г эрэмблээд мөн тухайн S-н инверсийг тоолдог гэж үзье, (S.sorted, inverse).

S тэмдэгт мөрийн эхний хагасыг left, үлдсэн тэмдэгт мөрийг right гэе, S=left+right. Хэрэв left, right хоёр хоюулаа эрэмлбэгдсэн бол энэ хоёрыг нэгтгэж эрэмбэлсэн шинэ тэмдэгт мөр үүсгэхдээ K-г тоолчиж чадна. Тэгвэл рекурсик хамаарал буюу бодлогын хариу маань

F(S)=>

-> ll = F(left), rr = F(right)

-> S.sorted = left.sorted+right.sorted.

-> S.inverse = left.inverse+right.inverse+K

-> return (S.sorted, S.inverse)

Анзаарч чадсан бол дээрх алгоритм маань merge_sort байгаа. Тэгэхээр merge_sort ашиглан инверсийг O(NlogN)-д олж чадахнээ. source

Анализ3 Ер нь бол энэ бодлогоны хамгийн хурдан бодолт нь Trie өгөгдөлийн бүтэц ашиглах.

--

2140 - N<10 br="" n="">

Анализ Дараалсан тооны нийлбэрт тавихын тулд хамгийн том тоо нь N/2+1 байх нь ойлгомжтой. Шууд бүх боломжийг нь шалгана уу.

source

--

2136 - Өгөгдлөөс зөвхөн том үсэгнүүдийт тус бүр хэд байгааг тоолоод жишээний гаралт шиг хэвлэ.

Анализ Том үсэгнүүдийг A-0, B-1, .., Z-25 гэж дугаарлая. cnt[26] массив дотор үсэг тус бүр хэдэн удаа орсныг нь тоолоод харгалзах дугаараар нь массивын индекс болгож хадгалана. Энэ санаа маш олон бодлого, алгоритмд ашиглагддаг.

source

--

1504 хоёр тоо өгөгдсөн бол энэ хоёр тооны цифрүүдийг урвуулаад хооронд нь нэмээд гарсан хариуг бас дахин урвуулаад хэвлэ. Аль ч тохиолдолд тоо 0-ээр эхэлсэн байж болохгүй.

Анализ шууд хэлснээр нь хий

source

--

1001 R бодит тоо болон N натурал тоо өгөгдсөн бол R^N-г ол. Хэрэв хариу бүхэл тоо бол цэг тавих хэрэггүй. Мөн хариу урт, ардаа 0 агуулах хэрэггүй

Анализ Залхууралгүй, мөн үнэхээр сурмаар мөн өөрийхөө C++ мэдлэгээ сайжруулж сайн код бичдэг болмоор байвал энэ бодох ёстой. Цаас үзэг бариад өөрийг компьютер гэж бодоод алгоритмыг нь гарга.

source

--

3251 - NxN (N<=100) хэмжээтэй хөлөг өгөгдсөн, нүд бүр B, J, * аль нэг нь байна. Тэгвэл * бусад тэмдэгтүүд ямар нэгэн квадрат дүрсийн 4-н булан болж чадахыг олоод хамгийн том квадратын талын уртыг олно уу. Үүсэж болох квадрат нь заавал x, y тэнхлэгтэй параллел байх албагүй.

Энэ бодлогыг хэр бодохнуу хармаар байна. Бодсон нь доор коммент үлдээж санаа бодол, мөн асуух юмаа асуувал дуртай хариулна. Амжилт



Дараагийн пост Математик байх болно.