Skip to content
TheChatArchiveThe Chat Archive
DeepSeekDeepseek v3.2· deepseekHugging Face Frontier Reasoning Traces

problem Hanako is playing with n (4 ≤ n ≤ 10) cards side by side. Each card has one…

  1. User

    problem

    Hanako is playing with n (4 ≤ n ≤ 10) cards side by side. Each card has one integer between 1 and 99. Hanako chose k cards (2 ≤ k ≤ 4) from these cards and arranged them in a horizontal row to make an integer. How many kinds of integers can Hanako make in total?

    For example, consider that you are given five cards of 1, 2, 3, 13, 21 and choose three of them to make an integer. By arranging 2, 1, and 13 in this order, we can make an integer 2113. Also, by arranging 21, 1, and 3 in this order, the same integer 2113 can be created. In this way, the same integer may be created from a combination of different cards.

    Given the integers written on n cards, create a program to find the number of integers that can be created by selecting k cards from them and arranging them in a horizontal row. input

    The input consists of multiple datasets. Each dataset is given in the following format.

    Each dataset consists of 2 + n rows. The number of cards n (4 ≤ n ≤ 10) is written on the first line, and the number of cards to be selected k (2 ≤ k ≤ 4) is written on the second line. On the 2 + i line (1 ≤ i ≤ n), the integer from 1 to 99 written on the i-th card is written.

    When both n and k are 0, it indicates the end of input. The number of data sets does not exceed 5.

    output

    For each data set, the number of integers that Hanako can create is output on one line.

    Examples

    Input

    4 2 1 2 12 1 6 3 72 2 12 7 2 1 0 0

    Output

    7 68

    Input

    None

    Output

    None

  2. DeepSeek Assistant

    We need to interpret the problem clearly.

    We have n cards, each with an integer between 1 and 99 (inclusive). So each card has a number, which can be one-digit or two-digit. We are to select exactly k cards (2 ≤ k ≤ 4) from these n cards and arrange them in a horizontal row to make an integer. The integer is formed by concatenating the numbers on the selected cards in the order they are placed. That yields some integer (which could have leading digits? Since each card's number is between 1 and 99, it does not have leading zeros, because the smallest is 1. So the integer formed will not start with 0, so it's a positive integer with possibly varying number of digits: each card contributes either 1 or 2 digits. So total digits sum of digit lengths of selected cards.

    We need to count the number of distinct integers that can be formed in this way, considering that different selections or arrangements might produce the same integer. So essentially: from the multiset (or set? Could there be duplicate numbers on cards? Possibly, as the input numbers are integers on each card, and they may be repeated. For example, in sample, they have 1,2,12,1 - so two cards with 1. That matters because cards are distinct, but the numbers may be same. The integer formed depends on the sequence of numbers (from the cards), but if two different sequences yield same concatenated integer, they count as same integer.

    We need to compute the set of all possible integers obtained by selecting k distinct cards (since we choose k cards from the n cards; each card can be used at most once? It says "chose k cards from these cards and arranged them". So we select a set of k cards, and then order them. So each card is used at most once. The cards are distinct even if they have same number. So the selection is from n distinct cards. So we have a list of n numbers (with possible duplicates). Then we consider all permutations of all k-sized subsets, and for each permutation, we concatenate the numbers (as strings) to form an integer. Count distinct resulting integers.

    Constraints: n ≤ 10, k ≤ 4, number of datasets ≤ 5. So we can brute-force generate all possibilities. There are at most C(10,4) * 4! = 210 * 24 = 5040 per dataset if k=4, which is very small. But we need to handle duplicate numbers properly. So we can just generate all permutations of size k from the list of n numbers (considering cards distinct). But careful: If there are duplicate numbers, permutations from different card selections may yield same sequence of numbers (the numbers themselves) and thus same integer. But we can treat the cards as distinct, but when generating the integer we only care about the sequence of numbers. However, due to duplicates, there may be multiple identical sequences from different card combinations. But we just need distinct integers, so we can use a set to store the concatenated string (or integer, but might be large: max k=4 each up to 99 => at most 8 digits, so fits in 32-bit int, but better use string to avoid leading zeros issues? Actually numbers are between 1 and 99, so no zero, so integers fine). But careful: concatenating numbers like 1 and 2 yields "12" which is integer 12. But if we treat as integer, 12 is fine. However, if we have numbers like 12 and 3, concatenation yields 123. So integer representation is fine.

    But we must be careful: For example, selecting cards with numbers 1 and 2 can be arranged as (1,2) -> 12 or (2,1) -> 21. So those are two different integers.

    The sample input:

    First dataset: 4 2 1 2 12 1 Then 0 0? Actually sample input:

    Input

    4 2 1 2 12 1 6 3 72 2 12 7 2 1 0 0

    We need to parse correctly: They show:

    4 2 1 2 12 1 6 3 72 2 12 7 2 1 0 0

    That seems like two datasets? But there's no blank lines. The first dataset: n=4, k=2, then four numbers: 1,2,12,1. Then next dataset: n=6, k=3, numbers: 72,2,12,7,2,1? Actually after the first dataset numbers, the next line is 6, which is n for second dataset. Then k=3, then six numbers: 72, 2, 12, 7, 2, 1. Then 0 0. So sample output: 7 and 68.

    Let's test first dataset manually: n=4, cards: 1,2,12,1 (so two 1's). k=2. We need to count distinct integers formed by selecting two cards and arranging them.

    List all ordered pairs (i,j) with i≠j (cards distinct). Since cards are distinct, even if numbers same, the pairs are considered. But we just need distinct integer results.

    Let's enumerate: cards: A=1, B=2, C=12, D=1.

    All unordered pairs (then order both ways):

    (A,B): (1,2) -> 12; (2,1) -> 21. (A,C): (1,12) -> 112; (12,1) -> 121. (A,D): (1,1) -> 11; (1,1) both orders same because both numbers are 1; but note cards are distinct, but sequence (1 from A then 1 from D) gives "11"; (1 from D then 1 from A) also "11". So integer 11. (B,C): (2,12) -> 212; (12,2) -> 122. (B,D): (2,1) -> 21; (1,2) -> 12. (already have 12,21) (C,D): (12,1) -> 121; (1,12) -> 112. (already have 112,121)

    So distinct integers: 12, 21, 112, 121, 11, 212, 122. That's 7. So output 7 matches.

    Thus brute force generating all permutations of distinct cards works.

    Now second dataset: n=6, k=3, numbers: 72,2,12,7,2,1. So two 2's? Actually numbers: 72, 2, 12, 7, 2, 1 -> two cards with 2. We need to count distinct integers of length 3 numbers concatenated. Output is 68. We can test later.

    Implementation approach: For each dataset, read n, k. If both zero, stop. Then read n numbers into array cards[0..n-1]. We'll generate all permutations of size k from these n indices without repetition. Since n<=10, we can use recursion/backtracking to select k distinct indices, and for each permutation (i.e., we consider order), we compute the integer by concatenation. Alternatively, we can generate all ordered tuples of length k with distinct indices: for i1 in 0..n-1, for i2 in 0..n-1 (i2 != i1), ... up to k. Since k <=4, nested loops feasible. Or use itertools.permutations if using Python.

    We'll accumulate results in a set (use Python set of integers). Then output length of set.

    But careful: The concatenated integer might be large? Max each number up to 99, so two digits. For k=4, max total digits: 4*2=8, so integer fits within 2^31, but safe anyway Python int unlimited.

    Edge cases: Numbers are 1 to 99, no zeros. So no leading zeros, concatenation always gives integer without leading zero. So using integer conversion is safe.

    But note: If we concatenate numbers as strings and then convert to int, we should be careful about potential leading zeros if numbers had zeros; but not here.

    Thus simple.

    Now confirm the second dataset output 68. Let's quickly compute using program or mental? Not necessary.

    So algorithm is straightforward.

    But wait, the problem statement says "Each card has one integer between 1 and 99." So numbers are positive. Also n up to 10, k 2-4.

    Implementation details: Input consists of multiple datasets. Each dataset: first line n, second line k, then n lines each containing an integer. The last line has "0 0". But careful: The sample input shows:

    4 2 1 2 12 1 6 3 72 2 12 7 2 1 0 0

    But after the first dataset numbers (1,2,12,1), there is 6 on next line (n). So it's just reading sequentially.

    Thus we can read lines one by one, treating them as integers. But easier: while True: read n from input (strip, int). Then if n==0: read k as next int; if also 0, break; else? Actually the termination condition is "When both n and k are 0, it indicates the end of input." So we need to read n, then read k. If n==0 and k==0 -> break. But we have to be careful: The input might have n and k on separate lines? In sample, they are on separate lines: first line 4, second line 2, then numbers, then 6, then 3, etc. So yes: n and k each on their own line. So we read n, then read k. If n==0 and k==0, break. Then otherwise, we read n numbers (each on separate line). So loop.

    Now implement.

    Complexity trivial.

    But we need to consider that the number of distinct integers may be large? For n=10, k=4, each card number between 1-99, there are at most 10P4 = 5040 permutations. So set size ≤ 5040, but duplicates reduce. So fine.

    Thus answer.

    Now, could there be any tricky parts about duplicate numbers? We'll treat cards as distinct, but when generating permutations we are selecting distinct indices. So that's correct. If we had duplicate numbers, we may generate the same integer from different index permutations. But we'll store in a set to deduplicate.

    Now, we could also generate combinations of indices and then permutations, but nested loops simpler.

    Pseudo:

    while True: n = int(input()) if n==0: k = int(input()) if k==0: break else: #? But if n=0 and k not zero? According to condition, only when both 0. So likely input ends with both 0. But to be safe, if n==0 but k maybe not zero? But problem says when both are 0. So we should read k first then check. So better: read n, if n==0: read k; if k==0: break; else? But then invalid? But guarantee input ends with "0 0". So we can do: n = int(input()); if n==0: k = int(input()); if k==0: break; else: ??? However, perhaps there is case where n=0 and k not given? Not. So just break. else: k = int(input()) # read n numbers cards = [int(input()) for _ in range(n)] # compute result res = set() # generate permutations # using recursion indices = list(range(n)) # we can use itertools.permutations(indices, k) from itertools import permutations for perm in permutations(indices, k): num_str = ''.join(str(cards[i]) for i in perm) # or directly integer: num = int(num_str) num = int(num_str) res.add(num) print(len(res))

    Note: Python's permutations yields tuples of length k with distinct indices. Good.

    Now test sample.

    But careful: The sample input uses spaces? Actually each number on its own line. So reading line by line works.

    Now let's test with given sample manually using code mental: first dataset yields 7, second yields 68. So fine.

    But we need to consider potential issue: integer concatenation may cause overflow? In Python fine.

    Now think about the condition that "Hanako is playing with n (4 ≤ n ≤ 10) cards side by side." but n could be 4 to 10. Yet the termination condition is n=0, k=0. So okay.

    Now about "The number of data sets does not exceed 5." So small.

    Thus solution straightforward.

    But we might need to consider if we should treat the cards as having numbers that might be two-digit, and concatenation like "12"+"3" = "123", and "1"+"23" = "123". That yields same integer from different card sets. Our set will deduplicate.

    Thus answer.

    Now double-check second dataset: n=6, k=3, numbers: 72,2,12,7,2,1. We'll compute using Python quickly mental? Might be large. But trust output 68.

    Potential pitfalls: The input reading might need to handle trailing whitespace. Use sys.stdin.

    Now, maybe the problem expects to output the number for each dataset on separate line.

    Now, consider performance: trivial.

    Thus we can code.

    But wait: In problem statement: "Given the integers written on n cards, create a program to find the number of integers that can be created by selecting k cards from them and arranging them in a horizontal row." And example of same integer created from different cards is described. So set dedup.

    Thus solution.

    Now, I'll produce final answer.

    But also note: In some competitive programming problems, they may consider that numbers like "01" are not valid because numbers are 1-99, so no leading zeros, fine.

    One more nuance: The numbers on cards are integers; when concatenating, we treat them as strings and form a new integer, but if a number is like 10, concatenated with 2 yields "102" which is 102, correct.

    Thus solution.

    Now implement.

    We'll write a solve() function that reads from sys.stdin.

    Pseudo:

    import sys from itertools import permutations

    def main(): data = sys.stdin.read().strip().split() # But since n and k and numbers are all separate tokens, we can parse sequentially. # However, reading line by line might be simpler: iterate over lines. # But we can use iterator over tokens. # Let's use token approach to avoid issues with newlines. it = iter(sys.stdin.read().strip().split()) out_lines = [] while True: try: n = int(next(it)) except StopIteration: break k = int(next(it)) if n==0 and k==0: break cards = [int(next(it)) for _ in range(n)] # compute res = set() for perm in permutations(range(n), k): num_str = ''.join(str(cards[i]) for i in perm) res.add(int(num_str)) out_lines.append(str(len(res))) sys.stdout.write('\n'.join(out_lines))

    if name == 'main': main()

    Testing with sample:

    Input tokens: ['4','2','1','2','12','1','6','3','72','2','12','7','2','1','0','0']

    Processing: n=4,k=2, cards[4] = 1,2,12,1 -> compute -> output 7; then n=6,k=3, cards[6] = 72,2,12,7,2,1 -> compute -> output 68; then n=0,k=0 -> break. So output lines: 7 and 68. matches.

    Edge cases: When n=0 but k non-zero? Not in input.

    Thus final solution.

    Now, this is straightforward, but the problem might have hidden nuance: The number of cards n is between 4 and 10, k between 2 and 4. So we can brute-force.

    But perhaps the problem expects to use a more clever approach? Not needed.

    Thus answer is as above.

    Now, let's think about potential pitfalls: The numbers can be two-digit, and concatenation could be interpreted as integer. But in Python, converting to int will drop any leading zeros, but there are none. So fine.

    Alternatively, we could store strings as keys, but integer also fine.

    Now, note: The numbers on cards are between 1 and 99 inclusive. So they are at most two digits. But there is no 0, so safe.

    Now, maybe we need to consider that the concatenated integer could have leading zeros if a number like 0? But not.

    Thus final.

    Now, will we have to worry about memory? No.

    Thus final answer.

    Now, I'll produce final output. ```python

    import sys from itertools import permutations

    def main() -> None: tokens = sys.stdin.read().strip().split() it = iter(tokens) out_lines = []

    while True:
        try:
            n = int(next(it))
            k = int(next(it))
        except StopIteration:
            break
    
        if n == 0 and k == 0:
            break
    
        # read the numbers on the cards
        cards = [int(next(it)) for _ in range(n)]
    
        results = set()
        # generate all ordered selections of k distinct cards
        for perm in permutations(range(n), k):
            # concatenate the numbers in the chosen order
            s = ''.join(str(cards[i]) for i in perm)
            results.add(int(s))
    
        out_lines.append(str(len(results)))
    
    sys.stdout.write('\n'.join(out_lines))
    

    if name == 'main': main()