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

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

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

Муруй зам:

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