Internet Problem Solving Contest

• Easy input data set – M1
• Hard input data set – M2
• A machine-readable list of all lands

Hello and welcome to a brief excursion into the wondrous world of the trading card game Magic the Gathering. In this episode we will look at mana and at lands: the cards that produce it.

Problem overview

Mana is the “currency” used to cast spells in the game. The canonical way to produce mana is by having some lands on the battlefield. In each turn of the game, each of those lands can be tapped once to produce some mana. (At any moment, each land that is on the battlefield is either untapped, meaning it can still be used this turn, or tapped, meaning it has already been used this turn.)

As the input to your program you will be given two sets of land cards: untapped lands that are already on the battlefield and lands that are still in your deck.

Your task is to tap the lands in such a way that you 1. don’t die, and 2. produce at least the specified amount of mana of each type.

Below, we will explain in detail how everything works. Note that all the cards shown below will be given to you in a machine-readable format.

Mana

There are five colors of mana: white, blue, black, red, and green. Their symbols are shown below, in this order.

In text, we use the letters W, U, B, R, and G to denote the five colors of mana. Note that U (as in “blUe”) is used for the blue color – this is because both “blue” and “black” start with the same letter.

In addition to the five mana colors, there is also colorless mana. In pictures its associated symbol is a grey circle that contains a diamond, as shown below. We use the letter C to represent colorless mana.

All mana produced by lands is of one of the six types mentioned above.

In mana requirements there is a seventh possibility: generic mana. A requirement of generic mana can be paid using mana of any type. For example, if a spell requires three generic mana, we can satisfy this requirement by producing 2 blue and 1 colorless mana.

Generic mana requirements will be described using digits 1-9. For example, we can write “2WWU” to denote that a spell requires 2 generic, 2 white, and 1 blue mana. We can also write “1C” to denote that a spell requires 1 generic mana and 1 mana that has to be colorless.

Note that we interpret each character of a mana cost separately. For example, “99” is 9+9 = 18 generic mana, not 99 generic mana.

Land types used in this problem

In this section we will describe some of the multitude of land cards that are played in Magic.

Basic land types and basic lands

Each color of mana has an associated basic land type. These are Plains (W), Island (U), Swamp (B), Mountain (R), and Forest (G).

The simplest type of a land is a basic land. Its name is the same as the corresponding basic land type. Whenever tapped, a basic land produces one mana of the corresponding color. For example, the beautiful Forest land shown below on the left produces a single G mana when tapped. If you have three untapped Forests on the battlefield, you can tap all three of them to produce GGG (i.e., three green mana).

Multicolored lands

The other two pictures above show lands that are capable of producing multiple colors. When you tap the Mystic Monastery, you get to choose whether it should produce U, R, or W. Similarly, you can tap the Bayou for either B or G.

There is one additional technical difference between these two example lands. Mystic Monastery does not have any basic land type: it is a non-basic land. Bayou has two basic land types: it is both a Swamp and a Forest. This distinction will become important soon.

Fetch lands

The Wooded Foothills land shown above is an example of a fetch land. This land doesn’t produce any mana. Instead, when you tap it, you lose one life and something good happens. The loss of life will be addressed later. The good thing that happens is that you get to search your deck of cards (formally, the library: the cards you haven’t drawn yet) for any single land card that has one of the listed basic land types. You then throw away the fetch land and you replace it by the land you have selected from your library.

For example, the Wooded Foothills can be used to fetch a basic Mountain or a basic Forest (if you have some of them in your library). The Bayou also counts as a Forest. This means that you can use your Wooded Foothills to fetch a Bayou from your library.

Even though the Mystic Monastery can produce R, it is not a Mountain. Hence, you cannot use the Wooded Foothills to fetch a Mystic Monastery.

The fetch lands themselves do not have any basic land types. Thus, you cannot use a fetch land to fetch another fetch land.

Shock lands

The Steam Vents, shown in the left picture below, are an example of a shock land. If you already have an untapped Steam Vents on the battlefield, it’s great for you: you can tap it for either U or R. However, by default this land comes into play tapped. This means that you cannot use it on the turn when it enters the battlefield. In order to be able to use it right away, you have to pay 2 life. (This is called a “shock” because of a spell of that name that deals 2 damage.) If you pay the 2 life, you’ll get the land untapped and you can immediately tap it for one of the two colors it can produce.

In this problem, the shock will matter when using a fetch land. You may note on the card that the Steam Vents count as both an Island and a Mountain. Hence, they can be fetched by an appropriate fetch land such as our old friend the Wooded Foothills. However, if you decide to use the Wooded Foothills to fetch a Steam Vents and then you want to use the Steam Vents in the same turn, you have to pay a total of 3 life: 1 for the fetch land and another 2 to get the Steam Vents untapped.

Pain lands

The Battlefield Forge, shown above, is an example of a pain land. When you tap it, you get to choose one of three options: either it produces 1 colorless mana, or you lose 1 life and it produces R, or you lose 1 life and it produces W.

Bounce lands

The last card shown above is Azorius Chancery, an example of a bounce land. Bounce lands (also known as Karoos) have an effect that happens when they enter the battlefield. In this problem that effect does not matter. You can simply treat a bounce land as an especially cool land that produces two mana when tapped! For example, whenever you tap an Azorius Chancery, you will get both a W and a U.

Note that pain lands and bounce lands do not have any basic land types. Therefore, they cannot be fetched by fetch lands.

City of Brass and Gemstone Mine

Up until this point each item in our list was a category of lands. In this problem we will have multiple cards from each of those categories – for example, different fetch lands, each with its own two basic land types.

From now on, each card we mention will be a single specific card.

The two different five-color lands we are going to use in this problem are City of Brass and Gemstone Mine (both shown below). For the purpose of this problem we will assume that each Gemstone Mine does have a mining counter. In human words: if you have a Gemstone Mine, you can tap it to produce a single mana of any color for free, and if you have a City of Brass, you can tap it to produce a single mana of any color but you have to pay 1 life for this action. (The mana produced by either of these lands must be a mana of one of the five colors. These lands cannot produce colorless mana.)

Urza’s Tron

The last three lands we are going to use produce colorless mana. Individually, each of them produces C (i.e., one colorless mana). However, if you have at least one copy of each of them on the battlefield, they produce more! In that situation, each copy of Urza’s Mine and each copy of Urza’s Power Plant produces CC when tapped, and each copy of Urza’s Tower produces CCC.

All five lands we just mentioned are non-basic lands that cannot be fetched.

Life

At the beginning of the game you have 20 life. Whenever your life total drops to 0 or below 0, you lose the game. Each test case will specify your current life total.

Problem specification

You will be given a situation during your turn. You have some amount of life left. You have some lands on the battlefield and some lands in your library. All lands on the battlefield are currently untapped. If you have some fetch lands on the battlefield, you can use them to fetch some appropriate cards from your library to the battlefield.

You are going to cast a large spell. You are given the mana requirements for this spell. Your program should determine whether it is possible to tap the lands in such a way that you don’t die and the mana produced will satisfy the requirements.

Note that you are allowed to produce more mana than you need.

For example, if your goal is to produce “2WWU” and you tap your lands in such a way that they produce “CWWGUU”, you satisfied the requirements: you have the two white and one blue, and you can use any two of the three remaining mana to pay the two generic mana.

For another example, if your goal is to produce “RG” and you produce “CCCCCCCGG”, you failed: even though you produced 9 mana, none of it is red.

Input specification

The first line of the input file contains an integer t specifying the number of test cases. Each test case is preceded by a blank line.

Each test case starts with a line containing a number x: the number of land cards on the battlefield. Then, x lines follow, each containing the name of one card.

The test case continues with a line containing a number y: the number of land cards in your library. Then, y lines follow, each containing the name of one card.

Finally, there are two lines. The first of them contains your current life total (between 1 and 20, inclusive), and the second contains a nonempty string over [1-9CWURBG]: the specification of amounts and types of mana you should produce.

Capitalization and spaces in card names are used consistently everywhere. There are no extra spaces before or after a land name.

You may assume that the total number of lands (on the battlefield and in the library together) is at most 34.

In the easy subproblem M1, you may additionally assume that there are no fetch lands on the battlefield and no lands in your library.

Output specification

For each test case, output a single line with the string “YES” if the lands can be tapped accordingly, or “NO” if they cannot.

Be very very glad you do not have to produce a complete log of actions if the answer is YES. And while we are at it, be glad that we left out filter lands, tainted lands, and many other land types that would make this problem computationally much harder. By the way, did you know that Magic the Gathering is Turing-complete? ;)

Card specification

In order to make the implementation more pleasant, we will provide you with a machine-readable file m_lands.txt containing the descriptions of all the land cards that can appear in the inputs.

Here is a sample of the file, containing all the cards from the above examples. The other cards only differ in their names and colors of mana they produce.

Forest;Forest;G;
Mystic Monastery;;U|R|W;
Bayou;Swamp,Forest;B|G;
Wooded Foothills;;-fetchMountain|-fetchForest;
Steam Vents;Island,Mountain;U|R;--shock
Battlefield Forge;;1|-R|-W;
Azorius Chancery;;WU;
City of Brass;;-W|-U|-R|-B|-G;
Gemstone Mine;;W|U|R|B|G;
Urza's Mine;;1;tron 2
Urza's Power Plant;;1;tron 2
Urza's Tower;;1;tron 3

(Notes: This is a semicolon-separated list. The second field lists the basic land types of each land. The third field contains the alternatives you get to choose from, with the symbol - denoting a loss of 1 life. The last, fourth field is used as an extra note whenever it is needed.)

Notes for MtG players

If you do play Magic the Gathering, here are a few quick notes. In this problem there are no cards in hand, and therefore no ability to play an additional land from your hand to the battlefield. There can be more than four copies of nonbasic lands. For example, a test case with 34 Mystic Monasteries is perfectly valid. The rest of the problem should be faithful to the rules of the actual game.

Examples

Input:

4

3
Forest
Forest
Plains
0
20
GGW

3
Forest
Forest
Plains
0
20
2

2
Wooded Foothills
Forest
1
Steam Vents
7
RG

2
Wooded Foothills
Forest
1
Steam Vents
3
RG

Output:

YES
YES
YES
NO

1. Tap all three lands and you have exactly the mana you need.
2. The requirement is to produce 2 generic mana. Tap any two lands and use the mana they produced.
3. Tap the forest for G. Pay 1 life and use the Wooded Foothills to fetch the Steam Vents. Pay 2 life to get Steam Vents into play untapped. Tap Steam Vents for R. You are still alive with 4 lives left.
4. Here we have too few lives to survive the above sequence of actions.

Input:

4

2
Wooded Foothills
Forest
2
Steam Vents
Mountain
3
RG

4
Steam Vents
Steam Vents
Battlefield Forge
Azorius Chancery
0
1
1RWUU

4
Steam Vents
Steam Vents
Battlefield Forge
Azorius Chancery
0
1
RRWUU

1
Wooded Foothills
4
Forest
Battlefield Forge
City of Brass
Gemstone Mine
20
R

Output:

YES
YES
NO
NO

1. Instead of the Steam Vents we can now fetch the basic Mountain and tap it for R. As we have only paid 1 life for the fetch, we are still alive with 2 lives left.
2. As the Steam Vents are now on the battlefield (and therefore untapped), we can tap the two of them for R and U without losing life. We can also tap the Azorius Chancery for WU and the Battlefield Forge for C (a colorless mana) and use that C as the generic mana we need.
3. Tapping Battlefield Forge for R costs 1 life and that would kill us.
4. We can fetch the Forest but it doesn’t produce R. Even though the other three lands can produce R, they are neither Forests nor Mountains and therefore we cannot fetch them.

Input:

4

1
Wooded Foothills
2
Mountain
Mountain
20
RR

2
Wooded Foothills
Wooded Foothills
1
Mountain
20
RR

4
Urza's Power Plant
Urza's Tower
Urza's Mine
Urza's Tower
0
20
19

3
Tundra
Underground Sea
Volcanic Island
0
20
UUB

Output:

NO
NO
YES
YES

1. Each fetch land can only be used once. In this test case, you can only fetch one of the two Mountains and that is not enough.
2. You can use one of the two fetch lands to fetch the Mountain from your library to the battlefield. Afterwards, there are no Mountains left in your library, so the second fetch land has nothing to fetch.
3. Behold the power of Tron! We were supposed to produce 1+9 = 10 generic mana. And indeed, if we tap all four lands we have, we get 2+3+2+3 = 10 colorless mana.
4. Tundra, Underground Sea, and Volcanic Island are dual lands of the same type as Bayou, but they produce W|U, U|B, and U|R, respectively. In order to tap these lands for UUB we have to tap Underground Sea for black mana and the other two lands for blue mana.

“Magic the Gathering” is a registered trademark owned by Wizards of the Coast LLC (WotC), a subsidiary of Hasbro Inc. WotC does not endorse and has no involvement with the IPSC.