DP problems

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

Сериал

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

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

Фүжи Инфокснэт компаний нэрэмжит оюутны програмчлалын олимпиад 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?

Хөршүүд

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

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

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

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

Бодлогын дугаар: 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

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

Бодлого 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 үйлдлийг хийхэд гарах тоо нь бидний хайсан хариу юм.

Цэрэг

Тавил:
Эгнэж жагссан цэргүүдээс дайнд оролцох цэргүүдийг сонгохдоо аль ч хоёр зэрэгцээ цэргийг 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) хугацаанд бодно.