The prison of your city has *n* prisoners. As the prison can't accommodate all of them, the city mayor has decided to transfer *c* of the prisoners to a prison located in another city.

For this reason, he made the *n* prisoners to stand in a line, with a number written on their chests. The number is the severity of the crime he/she has committed. The greater the number, the more severe his/her crime was.

Then, the mayor told you to choose the *c* prisoners, who will be transferred to the other prison. He also imposed two conditions. They are,
 -  The chosen *c* prisoners has to form a contiguous segment of prisoners. -  Any of the chosen prisoner's crime level should not be greater then *t*. Because, that will make the prisoner a severe criminal and the mayor doesn't want to take the risk of his running away during the transfer. 
Find the number of ways you can choose the *c* prisoners.
The first line of input will contain three space separated integers *n* (1 ≤ *n* ≤ 2·10<sup class="upper-index">5</sup>), *t* (0 ≤ *t* ≤ 10<sup class="upper-index">9</sup>) and *c* (1 ≤ *c* ≤ *n*). The next line will contain *n* space separated integers, the *i*<sup class="upper-index">*th*</sup> integer is the severity *i*<sup class="upper-index">*th*</sup> prisoner's crime. The value of crime severities will be non-negative and will not exceed 10<sup class="upper-index">9</sup>.
def count_ways_to_choose_prisoners(n, t, c, crime_levels):
    count = 0  # Initialize the count of valid segments
    current_count = 0  # Initialize the count of consecutive prisoners with crime <= t

    for i in range(n):
        if crime_levels[i] <= t:
            current_count += 1
        else:
            current_count = 0

        if current_count >= c:
            count += 1

    return count

# Read input
n, t, c = map(int, input().split())
crime_levels = list(map(int, input().split()))

# Calculate and print the result
result = count_ways_to_choose_prisoners(n, t, c, crime_levels)
print(result)
Now, you can use this code to read the input and find the number of ways you can choose the c prisoners based on the given conditions.




User
give me another solution

ChatGPT
Sure, here's another solution using Python that avoids iterating through the list more than once:

python
Copy code
def count_ways_to_choose_prisoners(n, t, c, crime_levels):
    count = 0  # Initialize the count of valid segments
    current_count = 0  # Initialize the count of consecutive prisoners with crime <= t

    for i in range(n):
        if crime_levels[i] <= t:
            current_count += 1
        else:
            current_count = 0

        if current_count == c:
            count += 1

        if current_count > c:
            count += 1  # Count additional valid segments

    return count

# Read input
n, t, c = map(int, input().split())
crime_levels = list(map(int, input().split()))

# Calculate and print the result
result = count_ways_to_choose_prisoners(n, t, c, crime_levels)
print(result)
This solution still iterates through the list once, but it increments the count whenever it finds a segment of c consecutive prisoners with crime levels less than or equal to t. If it encounters a segment longer than c, it increments the count accordingly to account for the additional valid segments.





