2015
09-17

Sword

Satoshi, who has strong obsessions with Chinese domestic RPG, will never miss the marvelous game, Gu Jian Qi Tan II, a.k.a., the Legend of Ancient Sword II, because of its gorgeous graphics, picturesque characters and lively design.

Recently, Satoshi has some troubles in the new battle mode of the game, and seeks you for help to solve the problems.

Specifically, in the new instant-action mode, Satoshi can control N roles, and his goal is to kill all M tiny monsters to declare victory. The tiny monsters are too fragile to survive from any skills of any roles. In every second, Satoshi can choose to operate one single role once, or do nothing. However, to make his series of operations magnificent, he would not use same role in any two consecutive seconds, i.e., the role used in i-th second cannot be used in the (i+1)-th second anymore.

For each role, we know the number of skills he/she owns, as well as the LPT (loop time) of each skill, which indicates that the skill could be performed in every LPT seconds starting from the beginning (e.g., if the LPT of a skill is 3, Satoshi could cast the skill at 3s, 6s, 9s, …, so on and so forth). Moreover, the information of whether a skill can reach (touch) a certain monster is also provided (i.e., whether a monster is within the attacking range of a specific skill). Your task is to help Satoshi use the minimum amount time to win the game; ties are broken by preferring fewer number of operations, which is counted by the number of seconds in which Satoshi chooses to operate a role instead of doing nothing.

Note that Satoshi could choose a certain role, and of course no roles, in a specific second. And when he operates a role in a specific second, he can cast all the available skills (subject to the the LPT constraints) if he wants. Time begins with the 1st second.

The integer R in the first line of input indicates the total number of test cases. For each test case, there are two integers N (1 <= N <= 10) and M (1 <= M <= 200) as stated above, in the first line. Then N blocks of input follow. For the i-th block, the first line contains an integer S_i (1 <= S_i <= 300) denoting the number of skills that the i-th role owns. Each of the the next S_i lines in the i-th block has M+1 integers, i.e., the LPT (1 <= LPT <= 6) of the i-th role, and M Boolean values (0/1) where the j-th Boolean value indicates if the j-th monster is within the attacking range of the i-th role.

The integer R in the first line of input indicates the total number of test cases. For each test case, there are two integers N (1 <= N <= 10) and M (1 <= M <= 200) as stated above, in the first line. Then N blocks of input follow. For the i-th block, the first line contains an integer S_i (1 <= S_i <= 300) denoting the number of skills that the i-th role owns. Each of the the next S_i lines in the i-th block has M+1 integers, i.e., the LPT (1 <= LPT <= 6) of the i-th role, and M Boolean values (0/1) where the j-th Boolean value indicates if the j-th monster is within the attacking range of the i-th role.

4

1 1
1
1 1

1 1
1
3 1

2 2
2
1 1 0
2 1 0
1
1 1 0

1 2
3
2 1 0
5 0 1
6 1 1

1 1
3 1
0
5 2

——————————————————————————————

————————吐槽分割线—————————————————

(t, k)行,列时间冲突的约束，以及同一角色不再相邻时间出现的约束。

(m1+sigma(p1…pm2))列，怪物的列重复覆盖。

t, k  能够打的boss  遍历所有完全覆盖的重复覆盖列数的解，求得最小值即可。

1. 以我的角度看小贝和马云的那张照片，左边是小贝，右边是马云，而二叨幻想左边是干爹，右边是男友。真不知道原来二叨口味这么重呢啊。莫非二叨当时在他们后边跟着才会这样感觉？？

2. 一生至少要有那么一次，为了某个人而忘记了自己。不求有结果，不求同行。不求曾经拥有，甚至不求你爱我。只求在最美好的年华里……遇见你。

3. 一生至少要有那么一次，为了某个人而忘记了自己。不求有结果，不求同行。不求曾经拥有，甚至不求你爱我。只求在最美好的年华里……遇见你。

4. 一生至少要有那么一次，为了某个人而忘记了自己。不求有结果，不求同行。不求曾经拥有，甚至不求你爱我。只求在最美好的年华里……遇见你。

5. 一生至少要有那么一次，为了某个人而忘记了自己。不求有结果，不求同行。不求曾经拥有，甚至不求你爱我。只求在最美好的年华里……遇见你。

6. 一生至少要有那么一次，为了某个人而忘记了自己。不求有结果，不求同行。不求曾经拥有，甚至不求你爱我。只求在最美好的年华里……遇见你。

7. 一生至少要有那么一次，为了某个人而忘记了自己。不求有结果，不求同行。不求曾经拥有，甚至不求你爱我。只求在最美好的年华里……遇见你。

8. 一生至少要有那么一次，为了某个人而忘记了自己。不求有结果，不求同行。不求曾经拥有，甚至不求你爱我。只求在最美好的年华里……遇见你。

9. 一生至少要有那么一次，为了某个人而忘记了自己。不求有结果，不求同行。不求曾经拥有，甚至不求你爱我。只求在最美好的年华里……遇见你。

10. 一生至少要有那么一次，为了某个人而忘记了自己。不求有结果，不求同行。不求曾经拥有，甚至不求你爱我。只求在最美好的年华里……遇见你。

11. 一生至少要有那么一次，为了某个人而忘记了自己。不求有结果，不求同行。不求曾经拥有，甚至不求你爱我。只求在最美好的年华里……遇见你。