Here is the link to the contest. All problems are from Codeforces' problem set.
To determine if each access key is secure, we need to validate it against three specific rules. First, all digits (if present) must appear before any letters. That means the transition from digits to letters can happen only once, and once it does, no digit should appear afterward. For example, "123abc" is valid, but "a1b2" is not.
Second, the digits must be in non-decreasing order. This means that as we read through the digits from left to right, each digit must be greater than or equal to the previous one. For example, "1125" is valid, but "132" is not, because "3" comes before "2", which violates the order.
Third, the letters must also be in non-decreasing order. Just like the digits, the sequence of letters must be sorted in alphabetical order or stay the same. For instance, "abc" and "aabbcc" are valid, but "acb" is not.
To implement this, we iterate over the string character by character. We can maintain two variables: one for tracking the last digit and one for the last letter we’ve seen. If the current character is a digit, we check that it is not less than the last digit. If it is a letter, we check that it is not less than the last letter. Additionally, if we have already seen a letter and encounter a digit afterward, we immediately mark the access key as invalid.
By applying these checks for each test case, we can determine whether a given access key is secure. If all conditions are satisfied, we output "YES"; otherwise, we output "NO". This approach is efficient and works well within the given constraints.
t = int(input())
for _ in range(t):
n = int(input())
key = input()
last_digit = '0'
last_letter = 'a'
seen_letter = False
is_secure = True
for ch in key:
if ch.isdigit():
if seen_letter:
is_secure = False
break
if ch < last_digit:
is_secure = False
break
last_digit = ch
else:
if ch < last_letter:
is_secure = False
break
last_letter = ch
seen_letter = True
print("YES" if is_secure else "NO")
Jean wants to make as many hikes as possible. Each hike requires exactly $$$k$$$ consecutive days of good weather, meaning the weather values must be all zeros during those $$$k$$$ days.
Suppose we identify a continuous block of days where the weather is good (all zeros), and the block length is $$$len$$$. This means Jean has $$$len$$$ consecutive days suitable for hiking.
Each hike takes $$$k$$$ days, and after each hike, Jean must take a rest day before starting another hike. This means every hike plus its mandatory rest day consumes $$$k + 1$$$ days, except for the last hike in the block, which does not require a rest day afterward.
To handle this last hike exception neatly, we imagine adding an imaginary rest day at the end of the block, making the effective block length $$$len + 1$$$.
With this imaginary day included, the entire block can be divided into chunks of length $$$k + 1$$$, where each chunk represents one hike plus its rest day.
Therefore, the maximum number of hikes that fit in the block is calculated by: $$$\text{hikes_in_block} = \left\lfloor \frac{len + 1}{k + 1} \right\rfloor$$$, where the keyword "floor" means rounding down to the nearest integer.
If the weather array contains multiple such blocks separated by rainy days (days with 1), we apply this formula to each block independently.
Finally, the sum of hikes from all blocks will be the maximum number of hikes Jean can make.
This approach efficiently accounts for both the length of consecutive good weather days and the mandatory rest days, allowing us to quickly compute the maximum hikes possible in the entire period.
t = int(input())
for _ in range(t):
n, k = map(int, input().split())
a = list(map(int, input().split()))
hikes = 0
length = 0
for day in a:
if day == 0:
length += 1
else:
hikes += (length + 1) // (k + 1)
length = 0
hikes += (length + 1) // (k + 1)
print(hikes)
