Problem B - Master Mind Helper

Master Mind was invented around 1970/71 by Mordecai Meirowitz, an Israeli Postmaster/Telecommunications expert. His idea was at first turned down by many of the leading toy companies, but he persisted, and took it to the International Toy Fair at Nuremberg in February 1971, where he showed it to a small English company, Invicta Plastics Ltd. The small Leicester based company bought up the entire intellectual property rights to the game, and under the guidance of its founder Mr. Edward Jones-Fenleigh, refined it, and released it in 1971/72. It was an immediate hit, and went on to win the first ever Game of the Year Award in 1973. It also received a Design Centre Award, and the Queen's Award for Export Achievement. So, for sure you have heard about this game, right?

Its idea is simple: you have to break the secret color code combination that is a sequence of a number of colored pegs. You make guesses and receive feedback about your guesses, namely, the number of correct colors on correct places, and the number of correct colors on wrong places. For example, imagine a game with 9 colors and 4 positions. Let's say that the secret code is blue, blue, yellow, red. At the start you don't know what the code is and you make a guess: blue, green, green, yellow. The info you would receive would be that you have 1 correct color in the correct position (the first blue peg) and one correct color on a wrong place (the yellow peg, which is not on the correct position). See figure 1 to better understand this idea. The objective of the game is to guess the secret code, using as few guesses as possible.

Figure 1 - Explanation of a guess feedback

We are interested in a particular property of this game. Knowing a guess and its feedback, how many combinations of colors are consistent with the answer? For example, imagine a game with 9 colors and 3 positions. We make the guess blue, red, green and receive the info 1 correct color on correct place and 2 correct colors on wrong places. How many combinations are consistent whit this? In other words, how many possible secret codes are there that would give this answer? In this case, there are exactly 3 secret codes with this feedback for this particular guess: code 1 - blue, green, red; code 2 - green, red, blue and code 3 - red, blue, green. Your task is precisely to discover this kind of numbers.

The Problem

Given a guess and its feedback, your task is to write how many secret codes are consistent with that info. In this particular problem we will only be interested in 9 color mastermind games, with 2 to 5 positions. In order to simplify, we will represent colors as numbers, starting with 1 and ending with 9. Blue will be number 1, red will be 2 and so on (note that it does not matter which color is assigned to each number; the important thing is that a different number represents a different color).

Input

The first line of input will contain a single integer N, indicating the number of test cases that follow (1 ≤ N ≤ 30).

Then follow exactly N lines, each containing one test case consisting of three parts separated by single spaces. Each case starts with a valid guess, in a form of a string of digits (remember that the colors are coded with digits 1 to 9). This string can have from 2 to 5 digits. Then follows the feedback received in the form of two integer numbers: the first one represents the number of correct colors on correct places, and the second one represents the number of correct colors on wrong places.

Output

For each test case you must output a line containing a single integer representing the number of possible secret codes that would give that feedback for that particular guess. Remember that there are always 9 different colors and that the size of the secret code must be equal to the size of the guess.

Example Input

5
1234 2 2
111 1 0
567 0 1
91543 5 0
91543 0 5

Example Output

6
192
234
1
44

---

2005 Programming Contest of Porto University
Round 2, 28 of September of 2005
 
(Author: Pedro Ribeiro - DCC/FCUP)

---

這題給與一個猜測數字，然後會給定 ?A?B，
詢問可能答案有多少個。

猜的數字不會有 0，窮舉所有可能去計算之。

這題解的人很少，真是莫名其妙，不是很明白。

#include <stdio.h>
#include <string.h>
int main() {
    int testcase;
    char s[10], s2[10], format[20] = "%0?d";
    int A, B;
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%s %d %d", s, &A, &B);
        int len = strlen(s);
        int c = 1, i, j;
        for(i = 0; i < len; i++)
            c = c*10;
        format[2] = len+'0';
        int ret = 0;
        for(i = c/10; i < c; i++) {
            sprintf(s2, format, i);
            int cnt[10] = {}, ta = 0, tb = 0;
            int err = 0;
            for(j = 0; j < len; j++) {
                cnt[s2[j]-'0']++;
                if(s2[j] == '0')
                    err = 1;
            }
            if(err) continue;
            for(j = 0; j < len && ta <= A; j++) {
                if(s[j] == s2[j]) {
                    ta++;
                    cnt[s[j]-'0']--;
                }
            }
            if(ta != A) continue;
            for(j = 0; j < len && tb <= B; j++) {
                if(s[j] != s2[j]) {
                    if(cnt[s[j]-'0']) {
                        tb++;
                        cnt[s[j]-'0']--;
                    }
                }
            }
            if(ta == A && tb == B)
                ret++;
        }
        printf("%d\n", ret);
    }
    return 0;
}