## Task Description

We are going to simulate the 3-SAT problem. There are some lights and a sequence of locks. Each lock has three sensors triggered by the lights. If a lock has at least one sensor being triggered, it will be unlocked. Each sensor has a non-zero integer $k$ which means that the sensor is triggered by the $\vert k\vert $-th light. If $k$ is positive, the sensor will be triggered when the light is on; if $k$ is negative, the sensor will be triggered when the light is off. Please refer to the following figure.

First, please design an object for the locks.
You can store any information you need in the object.
We will use `init`

function to initialize your structure.
The `int lockSeq[][3]`

is the sequence of locks with three sensors on each lock, and `int n`

is the number of locks.
`init`

function will return a pointer of your object.
Remember to use `malloc()`

in your `init`

function.
Then, please write a function `numUnlocked`

.
Given the status of lights and the object of locks, you have to count the number of unlocked locks.
Lights are stored in `bool lights[]`

where 1 is on and 0 is off for the light.
`int m`

is the length of `lights[]`

.
Note that the status of the light 1 is stored in `lights[0]`

.
These are templates of the structure and function APIs in `lock.h`

.
You should implement the functions in the other file `lock.c`

.

`typedef`

`struct`

`locks {`

` `

`/* design yourself */`

`} Locks;`

`Locks* init(`

`int`

`lockSeq[][3], `

`int`

`n);`

`int`

`numUnlocked(Locks *locks, `

`bool`

`lights[], `

`int`

`m);`

You can use this main function (`mainForNumUnlocked.c`

) to test your functions and structure:

`#include <stdio.h>`

`#include <stdbool.h>`

`#include "lock.h"`

`#define SENSORNUM 3`

`int`

`main() {`

` `

`int`

`m, n;`

` `

`scanf`

`(`

`"%d%d"`

`, &m, &n);`

` `

`bool`

`lights[m];`

` `

`int`

`lockSeq[n][SENSORNUM];`

` `

`for`

`(`

`int`

`i = 0; i < m; i++) {`

` `

`int`

`tmp;`

` `

`scanf`

`(`

`"%d"`

`, &tmp);`

` `

`lights[i] = (tmp == 1);`

` `

`}`

` `

`for`

`(`

`int`

`i = 0; i < n; i++) {`

` `

`for`

`(`

`int`

`j = 0; j < SENSORNUM; j++) {`

` `

`scanf`

`(`

`"%d"`

`, &lockSeq[i][j]);`

` `

`}`

` `

`}`

` `

`Locks *locks = init(lockSeq, n);`

` `

`printf`

`(`

`"%d\n"`

`, numUnlocked(locks, lights, m));`

` `

`return`

`0;`

`}`

Second, given a sequence of locks, you have to find out the status of lights which has the maximum number of unlocked locks.
If there are different statuses having the same maximum number, you should choose the one with the *lowest* power consumption.
The power consumption from the first to the $m$-th light is $1, 2, 4,..., 2^{m-1}$.
You should implement this in your own main function, and you can use the functions provided by TAs.

## Compile

`gcc -std=c99 lock.c mainForNumUnlocked.c`

`gcc -std=c99 lock.c main.c`

## Note

For function testing, we will test your function using main function above.
If you only want to check whether your `lock.h`

and `lock.c`

is correct, you still have to upload the `main.c`

.
You can use the following as your `main.c`

.

`int`

`main() {}`

For finding the status, we will only use your `main.c`

.
`lock.c`

and `lock.h`

we used were *written by TA*.
That is, you can still use the functions and structure without implementing the them in `lock.c`

and `lock.h`

.
To test your `main.c`

only, you can upload the `lock.h`

template above, and upload the following `lock.c`

.

`#include <stdbool.h>`

`#include "lock.h"`

`Locks* init(`

`int`

`lockSeq[][3], `

`int`

`n) {}`

`int`

`numUnlocked(Locks *locks, `

`bool`

`lights[], `

`int`

`m) {}`

## Subtasks

- 30 points:
`init`

and`numUnlocked`

function testing - 70 points: finding the status of light to unlock most locks

## Input Format

For function testing, the first line has $m$ and $n$. $m$ is the length of lights and $n$ is the number of locks. The following line has $m$ 0’s or 1’s representing the status of lights. Each of the following $n$ lines has three integers representing three sensors of a lock.

For finding the status of lights, the first line has $m$ and $n$. $m$ is the length of lights and $n$ is number of locks. Each of the following $n$ lines has three integers representing three sensors of a lock.

- $1\leq m\leq 20$
- $1\leq n\leq 100$

## Output Format

For function testing, the output is an integer of the return value of function `numUnlocked`

.

For finding the status of lights, the first line has $m$ characters (0 or 1) representing the status of lights. The second line is the number of unlocked locks of that status. The third line is the power consumption.

## Sample Input 1 (function testing)

`5 3`

`1 0 0 1 0`

`-1 2 4`

`-2 -5 1`

`-4 3 5`

## Sample Output 1

`2`

## Sample Input 2 (function testing)

`7 7`

`0 1 0 0 0 1 1`

`6 7 -5`

`4 7 -3`

`-6 -2 4`

`3 -1 5`

`2 -6 2`

`6 -1 -3`

`3 -2 5`

## Sample Output 2

`5`

## Sample Input 3 (finding light status)

`5 3`

`-1 2 4`

`-2 -5 1`

`-4 3 5`

## Sample Output 3

`00000`

`3`

`0`

## Sample Input 4 (finding light status)

`6 7`

`2 5 4`

`3 1 -1`

`3 2 6`

`4 5 3`

`1 6 -5`

`5 2 1`

`-2 1 6`

## Sample Output 4

`111000`

`7`

`7`