D. Параллель програмчлал

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

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

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

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

Поликарпус $n$ процессор бүхий компьютертэй. Мөн түүний компьютер $n$ санах ойн үүртэй. Бид процессорууд болон санах ойн үүрүүдийг 1-с $n$ хүртэл дугаарлагдсан гэж үзнэ.

Поликарпус параллель програмын загвартай болох шаардлагатай болсон. $i$ дугаартай санах ойн үүр бүрийн хувьд энэ програм уг үүррүү $n - i$ утгыг бичих ёстой. Өөрөөр хэлбэл үүр бүрийн хувьд та $n$ үүр хүртэлх зайг олох хэрэгтэй.

$i$-р үүрт бичигдсэн утгыг $a_{i}$ гэж тэмдэглэе. Анх $a_{i} = 1$ $(1 ≤ i < n)$ ба $a_{n} = 0$ байна. Бид зөвхөн $i$ процессор л $i$ дугаартай үүрт утга бичиж болно гэдгийг санах хэрэгтэй. Нэг үүрнээс бүх процессор өгөгдөл уншиж болно (нэг үүрнээс хэд хэдэн процессор зэрэг өгөгдөл уншиж чадна).

Параллель програм хэд хэдэн алхмаар ажилладаг. Алхам бүрийн үед бид нэмэгдэх үйлдлийн параллель хувилбарыг ажиллуулна. Нэмэгдэх үйлдлийн параллель хувилбарыг ажиллуулах нь дараах байдлаар явагдана:

  1. Процессор бүр бусад процессороос хамааралгүйгээр санах ойн үүр сонгоно. $i$ процессор $c_{i}$ $(1 ≤ c_{i} ≤ n)$ дугаартай үүр сонгосон гэе.
  2. Бүх процессорууд зэрэг $a_{i} = a_{i} + a_{c_{i}}$ үйлдлийг гүйцэтгэнэ.

Поликарпусд яг $k$ үйлдэлд ажилладаг параллел програмын загвартай болоход нь туслана уу. Ажиллах шаардлагатай үйлдлүүдийг тооцоол. $k$ үйлдлийн дараа бүх $i$ үүрний $a_{i}$ утга $n - i$ тэнцүү байх ёстой.

Оролт

Эхний мөрөнд зайгаар тусгаарлагдсан хоёр бүхэл тоо $n$ ба $k$ $(1 ≤ n ≤ 10^{4}, 1 ≤ k ≤ 20)$ байна.

Өгөгдсөн $n$ ба $k$-н хувьд шаардлагатай үйлдлүүдийн дараалал оршин байна.

Гаралт

$k$ мөрөнд яг $n*k$ бүхэл тоог хэвлэнэ. Эхний мөрөнд эхний нэмэгдэх үйлдлийн $c_{1}, c_{2}, ..., c_{n}$ $(1 ≤ c_{i} ≤ n)$ тоонуудыг хэвлэ. Хоёр дахь мөрөнд хоёр дахь нэмэгдэх үйлдлийн тоонуудыг хэвлэ. $k$-р мөрөнд $k$-р нэмэгдэх үйлдлийн тоонуудыг хэвлэ.

Хэвлэгдсэн үйлдлүүдийн үр дүнд бүх дурын $i$-н хувьд $a_{i}$ утга нь $n - i$ байх ёстой.

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

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

Оролт
1 1
Гаралт
1
Оролт
3 2
Гаралт
2 3 3
3 3 3
Сэтгэгдлүүдийг ачааллаж байна...