## TLE '17 Contest 3 P3 - Fax's Thanksgiving Dish

View as PDF

Points: 10 (partial)
Time limit: 2.0s
Java 3.0s
Python 3.0s
Memory limit: 256M
Java 512M
Python 512M

Authors:
Problem type
Is that spaghetti and bok-choi???

Fax McClad, Croneria's most meticulous bounty hunter, is going to prepare a dish for Thanksgiving! Fax prepared a turkey last year, so this year, he will cook something different.

There are different food items, numbered from to . There are different recipes. A recipe consists of a non-empty list of items that need to be combined to produce a target item. Only one unit of each item in the list is required, and the target item will not be in the list. Additionally, no two recipes will have the same target item, each item will appear at most once as a required item in a recipe, and item will not appear as a required item.

Fax wants to have one unit of item as his dish. For each item , he currently has units of that item.

Dankey Kang, Fax's enemy, wants to ruin Fax's Thanksgiving, so he will steal some food items from Fax so that he cannot have item . What is the minimum number of items that Dankey Kang must take?

#### Constraints

110There is exactly item, i.e.,
225 for all
325
440None

#### Input Specification

The first line will contain integers and .

Each of the next lines will contain one recipe. A recipe is one line long and follows this format:

• The first integer is the target item.
• The second integer is the number of required items.
• The remaining integers are the required items.

The last line will contain integers. The integer in this line is .

#### Sample Input 1

8 3
1 2 4 5
4 2 2 3
5 2 6 7
1 2 1 1 3 0 0 10

#### Sample Output 1

3

#### Explanation for Sample Output 1

Dankey Kang can steal item , item , and item . Afterwards, Fax cannot have item by following the recipes.

It is not possible to ruin Fax's Thanksgiving by stealing items. For example, if Dankey Kang stole item and item , the food list will become 0 2 1 0 3 0 0 10. Fax can follow the second recipe, and then the first recipe, to produce item .

#### Sample Input 2

3 2
2 1 3
3 1 2
0 0 1

#### Sample Output 2

0

• commented on Dec. 2, 2017, 3:54 a.m. edit 2

The problem is a little unclear. What is the meaning of "each item will appear at most once as a required item in a recipe"? Can an item appear in two recipes? Can there be a cycle, such as item 2 requires item 3 and item 3 also requires item 2?

• commented on Dec. 2, 2017, 4:02 a.m.

Each item cannot appear in two recipes. Each item will only have at most one recipe, and can only belong to at most one recipe.

• commented on Dec. 2, 2017, 4:53 a.m.

Can there be a cycle, such as item 2 requires item 3 and item 3 also requires item 2? A cycle seems satisfy all the conditions you mentioned. Thanks

• commented on Dec. 2, 2017, 1:58 p.m.

If there were to be a cycle, it is evident that it wouldn't have any effect on the final solution, since neither of the cycled ingredients would actually be part of a recipe to create item one, due to the fact that each item can belong to at most one recipe.

• commented on Dec. 2, 2017, 6:20 p.m.

Thanks a lot. Now I understand that no cycles are reachable from item 1.

• commented on Dec. 2, 2017, 6:12 a.m. edited

Edit: In that case, I have no idea what I'm talking about lmao

• commented on Dec. 2, 2017, 6:29 p.m. edited

No, it is possible to have cycles, but cycles do not impact the final solution. Please see aeternalis1 comment. Not sure if system test cases include cycles.