ბიზნეს-პროექტი

დროის ლიმიტი: 1 წმ

მეხსიერების ლიმიტი: 64 მეგაბაიტი

შემავალი მონაცემები: stdin

გამომავალი მონაცემები: stdout

წყარო: GEOI, 2010, დასკვნითი, XI-XII კლასი


სილანდიაში(კოლონია მთვარეზე) ეკონომიკური აღმავლობის უზრუნველსაყოფად გადაწყვიტეს მიწის ნაკვეთების გაყიდვა. ეს გარკვეული ექსპერიმენტია, ვინაიდან პირველი ტენდერია რომელზეც სახელმწიფო მფლობელობაში არესებულ მიწას მიჰყიდიან ბიზნესმენებს ჯალანდიიდან(კოლონია მარსზე). პრეზიდენტის ბრძანებით მოინიშნა NxM ზომის მართკუთხა ნაკვეთი, რომელიც დაყოფილია 1x1 კვადრატებად. სამწუხაროდ, ნაკვეთში ზოგიერთი კვადრატი გამოუსადეგარია, ანუ დიდი რაოდენობის ქვებით არის დაფარული. 
ბიზნესმენს სურვილი აქვს იყიდოს ისეთი მართკუთხედის ფორმის ნაკვეთი, რომელიც შემოღობილია ბუნებრივი მესერით(ყველა სასაზღვრო კვადრატი ქვებითაა დაფარული), ხოლო მესრის შიგნით მოთავსებულ ნაკვეთზე მინიმუმ K გამოსადეგი კვადრატია. ეკონომიკის სამინისტროს აინტერესებს თუ რამდენი შესაძლო ნაკვეთი არსებობს პრეზიდენტის მიერ მონიშნულ მიწაზე, რომელიც შეიძლება მიჰყიდონ ბიზნესმენს. სილანდიაში პროგრამისტები ჯერ კიდევ გამოუცდელები არიან, ამიტომ თქვენ, როგორც საქართველოს საოლიმპიადო პროგრამირების მომავალს დაგევალათ ამ ამოცანის გადაჭრა.
 
    შესატანი მონაცემები: შესატან მონაცემთა ფაილის პირველ სტრიქონში მოცემულია ჰარებით 
გამოყოფილი სამი მთელი რიცხვი: N, M და K (2 ≤ N, M ≤ 300, 1 ≤ K ≤ MN). 
შემდეგ  N სტრიქონში აღწერილია პრეზიდენტის მიერ შერჩეული მიწის ნაკვეთი.  თითოეულ მათგანზე მოცემულია M ცალი დიდი ლათინური სიმბოლო ‘X’ ან ‘O’, სადაც ‘X’ აღნიშნავს გამოუსადეგარ კვადრატს, ხოლო ‘O’ - სამეურნეო საქმიანობისათვის გამოსადეგ კვადრატს.
ტესტების 50%-ში N,M ≤ 100.
 
    გამოსატანი მონაცემები: გამოსატან მონაცემთა ფაილის ერთადერთ სტრიქონში უნდა 
ჩაიწეროს ერთი მთელი რიცხვი -  ყველა იმ განსხვავებული მიწის ნაკვეთების რაოდენობა, რომელიც შეიძლება იყიდოს ბიზნესმენმა.  ორი ნაკვეთი განსხვავებულად ითვლება თუ ისინი განსხვავდებიან ზედა მარცხენა კუთხის მდებარეობით, სიგრძით ან სიგანით.

 




მაგალითები

შესატანი მონაცემები
5 5 1 XXXXX XXXXX XXOXX XXXXX XXXXX დაკოპირება
გამოსატანი მონაცემები
16 დაკოპირება

შენიშვნა

გადავნომროთ სტრიქონები ზემოდან ქვემოთ და სვეტები მარცხნიდან მარჯვნივ. ბიზნესმენისთვის სასურველია ყველა მართკუთხედი, რომლის მარცხენა ზედა კუთხე არის ერთ-ერთი შემდეგი კვადრატებიდან: (1,1), (1,2), (2,1), (2,2).  მარჯვენა ქვედა კუთხე კი უნდა იყოს შემდეგი სიმრავლიდან: {(4,4), (4,5), (5,4), (5,5)}. სულ არის მართკუთხედის შერჩევის 16 გზა.