Codeforces Round #803 (Div. 2)
2 өдрийн дараа |
Codeforces Round #804 (Div. 2)
8 өдрийн дараа |
D. R2D2 ба робот арми
хугацааны хязгаарлалт 2 секунд
санах ойн хязгаарлалт 256 мегабайт
оролт стандарт оролт
гаралт стандарт гаралт
Нэг эгнээ жагссан $n$ тооны робот байв. Робот бүр $m$ ширхэг $a_{1}, a_{2}, ..., a_{m}$ бүхэл тоонуудаар тодорхойлогддог ба $a_{i}$ бол энэ роботын механизмд байгаа $i$-р төрлийн эд ангийн тоо юм. R2-D2 (Artoo-Detoo буюу Starwars киноны дүр) хамгийн урт дараалсан роботуудын дарааллыг устгахыг хүссэн. Түүнд $m$ ширхэг зэвсэг байгаа бөгөөд $i$-р зэвсгээр бүх роботоос нэгэн зэрэг $i$-р төрлийн (хэрвээ роботод энэ төрлийн эд анги байхгүй бол ямар ч нөлөө байхгүй) нэг эд ангийг устгах боломжтой.
Роботын бүх эд ангиуд устгагдсан тохиолдолд түүнийг устсан гэж үзнэ. R2-D2 хамгийн ихдээ $k$ буудалт хийж болно. R2-D2 хамгийн урт дараалсан роботуудын дарааллыг устгахын тулд ямар ямар төрлийн зэвсгээр тус бүр хэдэн удаа буудах вэ?
Оролт
Эхний мөрөнд $n, m, k$ ($1 ≤ n ≤ 10^{5}$, $1 ≤ m ≤ 5$, $0 ≤ k ≤ 10^{9}$) гурван бүхэл тоо байна. Эдгээр нь харгалзан роботуудын тоо, эд ангиудын төрлийн тоо болон боломжтой буудалтын тоо юм.
Дараагийн $n$ мөрүүдэд роботуудыг тодорхойлно. Мөр бүр $m$ ширхэг $a_{1}, a_{2}, ..., a_{m}$ ($0 ≤ a_{i} ≤ 10^{8}$) бүхэл тоонуудыг агуулах ба $a_{i}$ нь харгалзах роботын $i$-р төрлийн эд ангийн тоог илэрхийлнэ.
Гаралт
Зайгаар тусгаарлагдсан $m$ ширхэг бүхэл тоонууд хэвлэх ба $i$-р тоо нь хамгийн урт дараалсан роботуудын дэд дарааллыг устгахын тулд роботыг $i$-р төрлийн зэвсгээр буудах тоо юм.
Хэрвээ хэд хэдэн шийд байгаа бол тэдгээрийн аль нэгийг хэвлэнэ.
Заавал $k$ удаа буудах шаардлагагүй, түүнээс бага буудаж болно.
Орчуулсан: Даариймаа
Жишээ тэстүүд
Оролт
5 2 4 4 0 1 2 2 1 0 2 1 3
Гаралт
2 2
Оролт
3 2 4 1 2 1 3 2 2
Гаралт
1 3
Тэмдэглэл
Эхний жишээнд хоёр, гурав, дөрөвдүгээр роботууд устгагдсан.
Хоёрдахь жишээнд нэг, хоёрдугаар роботууд устгагдсан.