B. Ханойн Цамхаг

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

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

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

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

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

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

  1. Нэг үйлдлээр зөвхөн нэг дискийг шилжүүлэх боломжтой
  2. Аливаа баганы хамгийн дээд талын дискийг авч, өөр нэг баганы багц дискний дээр тавихыг "нэг үйлдэл" гэнэ. Энэ нь аливаа багц дискний зөвхөн орой дээрх дискийг л шилжүүлэх боломжтой гэсэн үг юм.
  3. Дискийг шилжүүлэхдээ өөрөөс нь жижиг дискний дээр тавихыг хориглоно.

Жишээлбэл, гурван дисктэй цамхагийг долоон үйлдлээр шийдвэрлэх боломжтой. Үнэндээ n ширхэг диск бүхий Ханойн Цамхагийн бодлогын хамгийн бага үйлдлийн тоо нь $2^n - 1$ байдаг. Дэлгэрэнгүйг (c) Wikipedia-аас харна уу.

SmallY -ийн бодлого нь алдарт Ханойн Цамхагийн бодлоготой тун төстэй юм. Ханойн Цамхагийн хувьд шилжүүлэх үйлдлийн тоо хамгийн бага байхыг шаарддаг бол, SmallY -ийн бодлогонд үйлдэл бүрт тодорхой зардал гарах учир, та хамгийн бага өртгөөр нь шилжүүлэх хэрэгтэй. SmallY -ийн бодлогонд анх бүх диск (n ширхэг) нэгдүгээр багананд байрлана. i дугаар баганаас j дүгээр $(1 ≤ i,j ≤ 3)$ баганаруу диск шилжүүлэхэд $t_{ij}$ нэгж зардал зарцуулагдана. Бодлогын зорилго нь нэгдүгээр баганааас бүх дискнүүдийг гуравдугаар баганаруу шилжүүлэх явдал юм.

Танд хүснэгт $t$ болон бүхэл тоо n өгөгдөнө. Та $n$ диск бүхий SmallY -ийн бодлогыг бодож, шаардагдах хамгийн бага зардлыг тооцох хэрэгтэй.

Оролт

Эхний гурван мөрөнд, тус бүр гурван бүхэл тоо байна. Энэ хүснэгт $t$ юм. $i$ -р мөрний $j$ -р тоо бол $t_{ij}$ юм $( 1 ≤ t_{ij}≤ 10000; i ≠ j)$. Түүний дараа нэг мөрөнд бүхэл тоо $n$ - дискний тоо) $( 1 ≤ n ≤ 40)$ өгөгдөнө.

Бүх оролтын хувьд $t_{ii} = 0 (1 ≤ i ≤ 3)$ байх болно.

Гаралт

SmallY -ийн бодлогын хариу болох хамгийн бага зардал нэг ширхэг бүхэл тоог хэвлэнэ.

Орчуулсан: footman

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

Оролт
0 1 1
1 0 1
1 1 0
3
Гаралт
7
Оролт
0 2 2
1 0 100
1 2 0
3
Гаралт
19
Оролт
0 2 1
1 0 100
1 2 0
5
Гаралт
87
Сэтгэгдлүүдийг ачааллаж байна...