• All programs must compile without warnings when using the -Wall and -Werror options

• Submit only the files requested

  Do NOT submit folders or compressed files such as .zip, .rar, .tar, .targz, etc

• Your program must match the output exactly to receive credit.

  Make sure that all prompts and output match mine exactly.

  Easiest way to do this is to copy and paste them

• All input will be valid unless stated otherwise

• Print all real numbers to two decimal places unless otherwise stated

• The examples provided in the prompts do not represent all possible input you can receive.

• All inputs in the examples in the prompt are underlined

  You don't have to make anything underlined it is just there to help you differentiate between what you are supposed to print and what is being given to your program

• If you have questions please post them on Piazza

  Restrictions

• No global variables are allowed

• Your main function may only declare variables, call other functions, and assign

  variables values.

In collectible/trading card games like Magic The Gathering and HearthStone it is important for some decks to draw a specific card by a certain turn. For this problem you will be calculating the probability of drawing at least one copy of a specific card by a given turn.

Here's how our card game will be played

1. You will initially draw N cards from your deck. This is your starting hand

2. The next step is the mulligan. In the mulligan step you select between 0 and N cards to set

   aside. Let the number of cards you choose to set aside be M. You will then draw M more cards from the deck.

1. Note. You cannot redraw the cards you set aside because you set them aside and did not

place them back into the deck

3. You then shuffle those cards back into the deck

4. After the initial draw and the mulligan you draw one card per turn.

So now we want to calculate what are the odds that you will get at least one copy of the card you are looking for by the desired turn. Note that we are actually calculating the probability in this problem and not simulating it.

Probability

The probability that two independent events A and B occurs is P(A) * P(B), where P(A) is the probability of A occurring and P(B) is the probability of B occurring. For example if the P(Sun) is 75% and the P(Wind) is 25% then P(Sun and Wind) = P(Sun) * P(Wind) = .75 * .25 = .1875 = 18.75%

If A and B are disjoint events the P(A or B), at least one of them happening, is P(A) + P(B). Disjoint means they can't happen at the same time. For example if you roll a 6 sided dice once, rolling a 5 and rolling a 2 are disjoint because with one roll you can't roll them both. This would mean that (P rolling a 5 or a 2) = P(Roll a 5) + P(Roll a 2) = 1/6 + 1/6 = 2/ 6 = 1/3

Either an event happens: A or it does not happen A . Since A and A are disjoint this means that P(A or A ) = 1. This can be useful in simplifying calculations. Let's say we wanted to know what the probability of not rolling a 6 is. One way we could figure this out is to enumerate all the other possibilities which are rolling a 1, 2, 3, 4, or 5. This would gives us P(1 or 2 or 3 or 4 or 5) = P(1) + P(2) + P(3) + P(4) + P(5) = 1/6 + 1/6 + 1/6 + 1/6 + 1/6 = 5/6. As an alternative we could have figured out what the probability of rolling a 6 is P(6) = 1/ 6 and used the fact that P(6) + P( 6 ) = 1. Solving for P( 6 ) we have P( 6 ) = 1 P(6) 1 1/6 = 5/6.

Finally there is conditional probability P(A | B). This is the probability that A happens given you know that B has already occurred. Imagine you have 2 dice and you roll them one at a time. Let's say the first dice is a 6. Now we want to find the probability that the sum of your dice is greater than or equal to 10. This would be finding P(sum dice >= 10 | dice 1 = 6). Since we know the first dice is a 6 we know that the only way the sum will be greater than or equal to 10 is if you roll a 4,5 or 6 so P(sum dice >= 10 | dice 1 = 6) = P (Dice 2 = 4, 5 or 6) = P(Dice 2 = 4) + P (Dice 2 = 5) + P(Dice 2 = 6) = 1/6 + 1/6 + 1/6 = 3/6 = 12 = 50%.

Addressing the Problem

Now to apply these rules to the problem at hand. Let's think about when we could draw a copy of the card we are looking for

1. In our opening hand

2. In our mulligan

3. Drawing it on one of our turns

Enumerating all the ways the above could happen is hard so we might think about what are the ways of not drawing any of the copies of the cards we are looking for.

1. We don't draw it in the opening hand

2. We don't draw it in the mulligan

3. We don't draw it on one of your turns

This would mean that the probability of drawing the card is 1 P(Not drawing the card) = 1 P(not draw in opening hand | haven't drawn a copy yet) * P(not draw in mulligan | haven't drawn a copy yet) * P(don't draw it on any turn | haven't drawn a copy yet).

Example Worksheet

Below we are trying to solve the problem where we have a deck of 10 cards. There are 2 copies of the card we are looking for and we are trying to draw it by turn 3. Our hand size is 2 and we decide to mulligan one of them. In the tables below the cards we are looking for are X's and all the other cards are O's. Each step in the table is showing you what happens if we imagine we never draw the card. Write down the probabilities of not drawing the card in the table and then you should help you start to see the pattern

Initial Draw

Description	Hand	Deck	Probability of Not Drawing
Start		OOOOOOOOXX
Draw first card	O	OOOOOOOXX
Draw second card	OO	OOOOOOXX	NA