Extreme set - MarisaOJ: Marisa Online Judge

Extreme set

Time limit: 2000 ms
Memory limit: 256 MB
Consider a set $A$ consisting of $n$ strings, each string of length $m$ and consisting of only the characters `0`, `1` or `*`. With a string, we can transform to get a binary string by replacing each character `*` in the string into a character `0` or `1`. Transform $n$ strings of set $A$ to obtain binary string set $B$ with the smallest value. Transform $n$ strings of set $A$ to obtain the set of binary strings $C$ with the largest value. Requirement: Given $n$ strings, find a way to transform $n$ strings to get the set of binary strings $B$ with the smallest value and the set of binary strings $C$ with the largest value. ### Input - The first line contains two positive integers $n,m$ $(m \le 100)$ - The following $n$ lines, each line consists of a string of length $m$ consisting of only the characters `0`,`1` or `*` describe $n$ strings of set $A$. ### Output - The first line is an integer that is the cardinality of the set $B$; Next is $n$ binary string describing the way to transform each string in order to obtain the set $B$, the outputs are separated by exactly one space; - The second line is an integer that is the value of the set $C$; Next is the binary string describing tje way to transform each string in order to obtain the set $C$, the outputs are separated by exactly one space. ### Example Input: ``` 4 3 *** 01* 001 *1* ``` Output: ``` 2 001 010 001 010 4 000 010 001 111 ``` ### Scoring: There are $20$ test, each values $5.0$ points. Denote $s_B,s_C$ as the values of sets $B,C$ the students can find and the judge's answers are $w_B,w_C$,then the scoring for each test is: $2.5$ $\times$ $min \\{1,(\dfrac{w_B}{s_B})^5)\\}$ + $2.5$ $\times$ $min \\{1,(\dfrac{s_C}{w_C})^5)\\}$ ### Subtask - Subtask 1 ($50 \\%$) : $n \le 10$ - Subtask 2 ($50 \\%$) : $n \le 1000$
Topic
Others
Heuristic
Rating 2100
Source Tin học trẻ
Solution (0) Solution