MDT1 - Madotsuki Pattern
Madotsuki is the main character of the surreal adventure game Yumenikki. The poor girl ended her life after discard all of her properties that have been found in the dream. Every year there are some small celebrations among people. The most symbolic sign of Madotsuki is the pattern on her clothes ...
(image taken from github.com/madotsuki)
You have been given a n*m design. Each element is one of the following character '1', '0', '?'. You can freely choose each '?' to become '0' or '1', to maximizate the number madotsuki pattern in the design.
which the madotsuki pattern is somethings like this:
101
010
Remark
010
101
is not a madotsuki pattern.
Input
(Multiply test cases, for each test case)
n m ( n <= 1000, m <= 10)
[n*m '0', '1' or '?']
Output
For each test case, output the maximum answer, and how many design can reach the answer in total. Since the answer can be very huge, you only need to output it after mod 1,000,000,007.
Example
Input:2 42 4 ???? ???? 4 6 ?????? ?1010? ?0101? ??????
Output: 1 8 6 4
hide comments
cschuerc:
2017-01-26 21:00:24
How can I know when I should stop scanning the input, if the number of test cases is not given? Is there a maximum number of test cases? |
|
:D:
2013-01-27 16:55:57
Yes, Alex's description is correct. I also tested the problem and everything seems to be ok. Last edit: 2013-02-07 08:16:25 |
|
:D:
2013-01-27 11:53:19
Thanks for removing the picture. You can still attach some other artwork. I saw there's a lot of it on net. Just be sure it's nothing drastic or controversial. |
|
xiaodao:
2013-01-27 02:53:57
Thanks to Alex Anderson. Maybe the sample data can give you some explaintion. Sorry for my poor English /w\ ...
|
|
Alex Anderson:
2013-01-27 02:53:57
I think it is pretty clear what it means. Each ? could be 0 or 1. Suppose there are K question marks. Then there are 2^K different possible ways you could set up the board.
|
|
Ehor Nechiporenko:
2013-01-27 02:53:57
To Author, could you please clarify problem statement. Maximum answer is understood, but what does mean "how many design can reach the answer in total"?
|
Added by: | xiaodao |
Date: | 2013-01-25 |
Time limit: | 3s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |
Resource: | Own Problem |