Observations

The first thing to notice is that this problem gets a lot simpler if you ignore the first question on each card. If Pierre gets the first question wrong on a card, the card is discarded before his next turn begins. So there is always a higher score that would result from getting the first question right and the second question wrong. So you can just assume that the first questions will all be answered correctly – add up their scores as a base score and then focus on which of the second questions he gets wrong.

Exhaustive Search

The problem can be solved with a backtracking search algorithm focusing on the set of second questions on each card. At each step of the search, you have two recursive calls: either you get the next question right (add its value) or wrong (subtract one point). You are looking to return the higher result from these two calls. The main wrinkle is that you have to keep track of how many cards in a row you have solved, to avoid a Tour De Force situation. If you have answered the last ~4~ cards correctly, you can't get the next card right.

This works great for small data sets, but it will bog down with anything above ~30~ or so cards. If you are trying the search using both questions from each card, it will be trickier to get right, and it will bog down above ~20~ or so cards.

A Better Approach

This problem is very well suited to a technique known as "Dynamic Programming". In this approach you keep track of partial solutions in a "memo" array, then at each step in the backtracking, you first check to see if you already have a solution for the next part and if you do, you don't have to continue. This speeds things up considerably and allows you to easily solve problems with ~1000~ question cards.

Can you figure out how to "memoize" this problem to construct an efficient solution? If so, post your ideas to the appropriate forum at compsci.ca.

Other Approaches

It is also possible to make some progress using a "Greedy" approach to the problem. Again, it helps to make the observation that for the maximum score, Bert will get all of the first questions right. The question is, which of the second questions on each card will he get the points for? In one Greedy approach, you start by assuming he gets all the second questions wrong. Then start marking questions as correct in order of most to least points. If adding a card will create a Tour de Force (a streak of ~5~), then don't add that one. Move on to another instead. This approach will get 4 of the test cases wrong on each data set.

Another approach is to start by assuming Bert got all the second questions right. Then start marking questions incorrect in order of least to most points. Continue until there are no more Tour de Force's left in the set of cards. This version of a greedy algorithm does not do as well – it only gets a couple correct on each data set.

Dynamic Programming

With really big problems, backtracking bogs down and won't finish before the end of the universe. So you need a different approach. The technique of memorization used in Dynamic Programming works well here. The basic idea is to keep an array of partial solutions (usually called the "memo" array). Whenever you find a solution to part of the problem, store it in the array. When it is time to recurse, check your memo array first to see if you've already solved this sub-problem. If you have, just return the value you stored in the memo array.

The tricky part is figuring out what to store in the array. One approach that works well here is to have a two dimensional array. If you have previously solved ~x~ cards in a row with no mistakes and you are now looking at card ~y~, store the result of the recursive calls in ~memo[x][y]~. Then at each step in the recursion, look to see if there is anything stored in ~memo[x][y]~. If there is something there, use that number. If not, do the recursion and store the result in ~memo[x][y]~.