|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|5 초||512 MB||16||8||8||50.000%|
You own a milkshake shop. There are N different flavors that you can prepare, and each flavor can be prepared "malted" or "unmalted". So, you can make 2N different types of milkshakes.
Each of your customers has a set of milkshake types that they like, and they will be satisfied if you have at least one of those types prepared. At most one of the types a customer likes will be a "malted" flavor.
You want to make N batches of milkshakes, so that:
Find whether it is possible to satisfy all your customers given these constraints, and if it is, what milkshake types you should make.
If it is possible to satisfy all your customers, there will be only one answer which minimizes the number of malted batches.
For each test case, there will be:
All of these numbers are separated by single spaces.
2 5 3 1 1 1 2 1 0 2 0 1 5 0 1 2 1 1 0 1 1 1
Case #1: 1 0 0 0 0 Case #2: IMPOSSIBLE
In the first case, you must make flavor #1 malted, to satisfy the first customer. Every other flavor can be unmalted. The second customer is satisfied by getting flavor #2 unmalted, and the third customer is satisfied by getting flavor #5 unmalted.
In the second case, there is only one flavor. One of your customers wants it malted and one wants it unmalted. You cannot satisfy them both.