Limits 1s, 512 MB

Last night, Nitu came across the following pseudo-code. She understood that this method would take two integer values and a list of integers as input. She decided to implement this method in her preferred programming language and tried calling it with various sets of values. However, she encountered performance issues with her implementation for certain input values, as it did not execute within the expected timeframe. Can you assist her in implementing this pseudo-code?

 1FUNCTION CountLuckyNumbers(l, r, forbidden_list)
 2    # Initialize a counter for lucky numbers
 3    count_lucky_numbers = 0
 4
 5    # Loop through the range from l to r (inclusive)
 6    FOR i FROM l TO r
 7        # Convert the current number to a string
 8        current_number = CONVERT_TO_STRING(i)
 9        
10        # Initialize a flag to determine if the number is allowed
11        is_allowed = TRUE
12
13        # Check if the current number contains any of the forbidden numbers
14        FOR EACH forbidden IN forbidden_list
15            # Convert the forbidden number to a string for comparison
16            forbidden_string = CONVERT_TO_STRING(forbidden)
17
18            # If the current number contains the forbidden number as a substring,
19            # Set the flag to false and exit the loop
20            IF current_number CONTAINS forbidden_string
21                is_allowed = FALSE
22                BREAK
23            END IF
24        END FOR
25
26        # If the current number is allowed, increment the lucky number count
27        IF is_allowed
28            INCREMENT count_lucky_numbers BY 1
29        END IF
30    END FOR
31
32    # Return the count of lucky numbers
33    RETURN count_lucky_numbers
34END FUNCTION

Input

The input begins with an integer, TT (1T100)(1 \leq T \leq 100) indicating the number of test cases.

For each test case:

  1. The first line contains an integer, NN (1N100)(1 \leq N \leq 100) which represents the size of the forbidden list.

  2. The subsequent NN lines contain integers, each representing an element in the forbidden list. Each of these elements falls within the range 11 to 101810^{18}.

  3. Finally, there is a line containing two integers, ll and rr where both ll and rr are within the range of 11 to 101810^{18}.

Output

For each test case, please provide a single line of output in the following format: Case #X: Y\texttt{Case \#}X\texttt{: }Y.

Here, XX represents the test case number, and YY represents the result returned by the pseudocode.

Sample

InputOutput
1
2
3 6
1 10
Case #1: 8

Submit

Login to submit.

Statistics

61% Solution Ratio
Asif17rEarliest, 8M ago
NadiimFastest, 0.1s
NadiimLightest, 5.1 MB
NadiimShortest, 2076B
Toph uses cookies. By continuing you agree to our Cookie Policy.