Problem L
Lunchtime Name Recall

Mia is a newly hired administrative assistant. Though Mia was introduced to everyone in the company on her first day, she is forgetful and struggles to remember people’s names. Being too shy to ask for names again, she discovers a way to recall people’s names during lunchtime without asking.

Mia orders lunch for all of her colleagues in each of the next several days. On any day, Mia orders burgers for some of her colleagues and salads for the rest of her colleagues. The number of burgers she orders may vary per day. After placing the order, she sends an email to the colleagues who get a burger for lunch, and also to the remaining colleagues about their salads. Mia has an email list with all her colleagues’ names. She may choose by name who gets a burger and who gets a salad. Mia can see her colleagues as they are eating their lunch. Thus, by observing who turns out to eat a burger in the office and who eats a salad, she may gain some information to help her uniquely identify the names of her colleagues.

For example, suppose there are three colleagues with names Alice, Danielle, and Jennifer, and Mia can order one burger plus two salads on each day. On the first day, if Mia orders a burger for Alice and salads for Danielle and Jennifer, she can then tell who is Alice by observing who eats a burger. On the second day, Mia may order a burger for Danielle and a salad for Jennifer (and a salad for Alice who is already identified). Consequently she can uniquely identify all three colleagues.

What is the maximum number of colleagues that Mia can uniquely identify in the next few days, if she allocates the burger and salad recipients optimally?


The first line of input contains two space-separated integers $n$ ($2 \leq n \leq 30$) and $m$ ($1 \leq m \leq 10$), where Mia has $n$ colleagues and will be ordering lunch for $m$ days.

Each of the next $m$ lines contains a single integer $a$ ($1 \leq a < n$), which is the number of burgers Mia orders on that day. The days are listed in order.


Output a single integer, which is the maximum number of Mia’s $n$ colleagues that she can uniquely identify after $m$ days.

Sample Input 1 Sample Output 1
4 2
Sample Input 2 Sample Output 2
16 3
CPU Time limit 7 seconds
Memory limit 1024 MB
Statistics Show
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in