C. Даалуу

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

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

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

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

Завсарлагааны үеэр бид амрахаар шийдсэн ба даалуу тоглосон. Бидний даалууны хайрцаг хоосон байсан тул багшийн даалуунуудыг зээлэхээр шийдсэн.

Багш бидний хүсэлтэд хурдан хариу өгсөн. Тэр $nm$ даалууг ширээн дээр $n × 2m$ тэгш өнцөгт хэлбэрээр тавьсан ба $n$ мөр бүрт $m$ даалууг хөндлөнгөөр нь өрсөн. Даалуу бүрийн хагас бүр нь тоо (0 эсвэл 1) агуулна.

Бидний гайхсан харцны хариуд багш инээмсэглээд: "Даалууны өрөлтийг "$n × 2m$ хэмжээтэй матриц гэж үз. Матрицийн багана бүрийн хувьд уг баганад байгаа тоонуудын нийлбэрийг ол. Тэгээд ийм нийлбэрүүд дундаас хамгийн их утгатайг нь ол. Та нар матриц дахь даалуунуудыг хамгийн их нийлбэр боломжит хамгийн бага байхаар дахин эрэмбэлэж чадах уу? Даалуунуудыг босгох хориотой буюу тэд бүгдээрээ хэвтээ байх ёстой, гэсэн ч даалуунуудыг 180 градусаар эргүүлж болно. Шагналд нь би та нарт өөрийн бүх даалууг өгнө".

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

Оролт

Эхний мөрөнд бүхэл тоон утгууд $n$, $m$ ($1 ≤ n, m ≤ 10^{3}$) байна.

Дараагийн мөрүүдэд багшийн матрицын тайлбар байна. Дараагийн $n$ мөр бүрт $m$ даалуу байна. Нэг даалууны тайлбар нь даалууны зүүн ба баруун хагаст байх цифрүүдийг илэрхийлэх зайгаар тусгаарлагдаагүй хоёр бүхэл тоон утга (0 эсвэл 1) байна.

Гаралт

Үр дүнд нь үүсэх даалуунуудын матрицыг дараах форматаар хэвлэ: тус бүрдээ зайгаар тусгаарлагдсан $m$ даалуу агуулсан $n$ мөр.

Хэрвээ хамгийн тохиромжтой хэд хэдэн шийдэл байвал алийг нь ч хэвлэж болно.

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

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

Оролт
2 3
01 11 00
00 01 11
Гаралт
11 11 10
00 00 01
Оролт
4 1
11
10
01
00
Гаралт
11
10
01
00

Тэмдэглэл

Эхний жишээний хариултыг авч үзье. Бүх багануудын дундаас хамгийн их нийлбэр нь $1$-тэй тэнцүү байна (багануудын тоо нь $6$ байх ба $3$ биш). Мэдээж хамгийн их нийлбэр $1$-с бага байж чадахгүй учир энэ матриц хамгийн тохиромжтой хариулт мөн.

Даалуунуудыг $180$ градус эргүүлж болно гэдгийг сана.

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