D. 2048

хугацааны хязгаарлалт 1 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

R2 компанийн программистууд 2048 тоглох дуртай. Нэг өдөр тэд уг тоглоомын хялбаршуулсан хувилбар болох мөрөнд буй $2^{k}$-г өөрсдөө зохиохоор шийдсэн.

Нэгж квадратуудаас тогтох (квадрат бүрийн талын урт нь мөрийн өндөртэй тэнцүү) нэг чиглэлтэй хязгааргүй урт мөр байна гэж төсөөл. Квадрат бүр нэг бол хоосон эсвэл ямар нэг тоо агуулж чадна.

Анхандаа бүх квадрат хоосон байсан. Хязгааргүй нэгж кубуудын нэг бүр нь 2 эсвэл 4 тоог харуулна. Тэгээд тоглогч товч дээр нэг дарахад гарч ирсэн тоо мөрийн эхлэлрүү хөдлөж эхэлнэ. $x$ тоо мөрийн эхлэлрүү хөдлөж байна гэж үзье, тэгвэл тэр дараах нөхцөлд зогсоно:

  1. мөрийн хамгийн эхний квадрат дээр ирэх
  2. эсвэл өмнө нь $y$ $(y ≠ x)$ тоотой байсан квадрат дээр ирэх. Гэвч $x$ тоо нь өөртэй нь адилхан тоотой квадрат дээр ирвэл хоёр тоо хоорондоо нэмэгдэж $2x$ болно. Шинэ тоо $2x$ үргэлжлүүлэн мөрийн эхлэлрүү ижил дүрмээр хөдлөнө.

Тоо хөдлөх үйл явцын эцсийн зогсолтын дараа төгсгөлгүй квадратууд шинэ тоо болох 2 эсвэл 4-тэй болох ба үйл явц үргэлжилнэ. Хөдлөх стратегийг илүү ойлгохын тулд жишээний тэмдэглэлүүдийг уншина уу.

Би таныг 2 болон 4 тоонууд харагдаж буй дарааллаас бүрэн хамаарах тоглоомын үйл явцыг бүрэн ойлгосон гэж бодож байна. Тоглоомонд буй 2 болон 4 тоотой дарааллыг авч үзье. Хэрвээ дараалалд $2^{k}$-с их эсвэл тэнцүү тоотой ядаж нэг квадрат байвал уг дарааллыг хожлын дараалал гэж авч үзнэ.

Тоглоомын зорилго бол $n$ тоотой хожлын дараалал үүсгэх. Гэвч бүх зүйл амар биш дарааллын зарим тоонууд өмнө нь тодорхойлогдсон байна. Танд 0, 2, 4 тоонуудаас бүдрсэн дараалал өгөгдөнө. Хожлын дараалал үүсгэхэд дарааллын 0 бүрийг 2 эсвэл 4 тоогоор солих хэдэн зам байгааг тоол.

Оролт

Эхний мөрөнд хоёр бүхэл тоон утга $n$ ба $k$ $(1 ≤ n ≤ 2000; 3 ≤ k ≤ 11)$ байна. Дараагийн мөрөнд $n$ бүхэл тоон утгын дараалал байх ба эдгээрийн нэг бүр нь 0 эсвэл 2 эсвэл 4 байна.

Гаралт

Хожлын дарааллыг үүсгэхэд тэгүүдийг 2 эсвэл 4 тоонуудаар солих боломжийн тоог илэрхийлэх нэг ширхэг бүхэл тоон утгыг хэвлэ. Уг тоо маш их байж болох учир $1000000007$ $(10^{9} + 7)$ тоонд хуваагаад үлдэгдлийг хэвлэ.

Орчуулсан: Г.Мэндбаяр

Жишээ тэстүүд

Оролт
7 4
2 2 4 2 2 2 2
Гаралт
1
Оролт
1 3
0
Гаралт
0
Оролт
2 3
0 4
Гаралт
1
Оролт
5 4
2 0 0 4 4
Гаралт
2

Тэмдэглэл

Эхний жишээн дээр авч үзье. Анх мөр дараах байдалтай харагдана:

$2$ $ -> $ $4$ $ -> $ $8$ $ -> $ $8 2$ $ -> $ $8 4$ $ -> $ $8 4 2$ $ -> $ $16$.

Тоглоомыг илүү сайн ойлгохын тулд $http://gabrielecirulli.github.io/2048/$ эндээс жинхэнэ тоглоомыг харж болно. Дээр тодорхойлогдсон мөр дээрх тоглоом нь жинхэнэ тоглоомоос бага зэрэг ялгаатай(жинхэнэ тоглоом дээр хоёр тоо нэмэгдэх үед тэд хөдөлгөөнөө үргэлжлүүлдэггүй). Болгоомжтой байхгүй бол тоглоом донтуулах аюултай ба тэмцээнд тийм ч их цаг байхгүй шүү!

Сэтгэгдлүүдийг ачааллаж байна...