დროის ლიმიტი: 1 წმ
მეხსიერების ლიმიტი: 256 მეგაბაიტი
შემავალი მონაცემები: stdin
გამომავალი მონაცემები: stdout
წყარო: GEOI, 2010, რეგიონული, X კლასი
ქალაქის მერიის შენობას მისი სიძველის გამო ერთ-ერთი კედელი დაუზიანდა. მერიის კედლები მოპირკეთებულია ერთეულოვანი სიგრძის გვერდის მქონე კვადრატული ფილებით. დაზიანებული კედლის კოდირებული გამოსახულება წარმოადგენს 0-ებისა და 1-ებისაგან შედგენილ ცხრილს, რომელიც m რაოდენობის სტრიქონისა და n რაოდენობის სვეტისაგან შედგება.
ქვემოთ მოცემულია ამ კედლის გამოსახულების მაგალითი, სადაც 0-ებით დაზიანებული ფილებია გამოსახული, ხოლო 1-ებით კი – დაუზიანებელი ფილები:
1110000111
1100001111
1000000011
1111101111
1110000111
ქალაქის მერიამ კედლის შეკეთებისათვის გამოაცხადა ტენდერი, სადაც ხარჯების მინიმიზაციის მიზნით ჩადებულია პირობა, რომ კედლის დაუზიანებელი უბნები ხელუხლებლად უნდა დარჩეს, ხოლო დაზიანებულ უბნებზე ვერტიკალურად უნდა განთავსდეს k (k=1,2,3,…,მ) სიმაღლის და ერთეულოვანი სიგანის ახალი ფილები.
დაწერეთ პროგრამა, რომელიც მერიის დაზიანებული კედლის მოცემული სტრუქტურისათვის იპოვის მის შესაკეთებლად საჭირო k (k=1,2,3,…,მ) სიმაღლის და ერთეულოვანი სიგანის ფილების მინიმალურ რაოდენობას.
შესატანი მონაცემები: პირველ სტრიქონში მოცემულია ორი მთელი დადებითი m და n რიცხვი (1 ≤ m,n ≤ 200) – დაზიანებული კედლის განზომილებები. მომდევნო მ რაოდენობის სტრიქონი წარმოადგენს კედლის კოდირებულ გამოსახულებას. თითოეულ მათგანში ჩაწერილია n რაოდენობის სიმბოლო (0 ან 1).
გამოსატანი მონაცემები: უნდა ჩაიწეროს კედლის შესაკეთებლად საჭირო ფილების აღწერა. მისი თითოეული სტრიქონი უნდა შეიცავდეს ერთი ჰარით გამოყოფილ ორ მთელ k და p რიცხვს, სადაც კ ფილის სიმაღლეა, ხოლო p კი ამ სიმაღლის ფილების მინიმალური რაოდენობა. ფაილში ფილები დალაგებული უნდა იყოს მათი სიმაღლეთა ზრდის მიხედვით. გამოსატან მონაცემთა ფაილი არ უნდა შეიცავდეს k სიმაღლის ისეთ ფილებს, რომელთათვისაც p=0.
შესატანი მონაცემები
5 10 1110000111 1100001111 1000000011 1111101111 1110000111 დაკოპირება
გამოსატანი მონაცემები
1 7 2 1 3 2 5 1 დაკოპირება