1777A - Everybody Likes Good Arrays! - 800
2 min read
On This Page
1777A - Everybody Likes Good Arrays! (greedy, math, 800)
- You have an array of numbers, and you want to make it “good.” A good array is one where every pair of adjacent numbers has different parity (one is even, and the other is odd).
- You can do this by performing operations on pairs of adjacent numbers with the same parity (both even or both odd), and replacing them with their product.
- Loop through the array
- Check the parity of the current element and the previous element
- If the parity is the same, perform the operation and increment the operation counter
- Repeat steps 2 and 3 until the end of the array
- Return the operation counter
def solve(n, ar): res = 0 i = 0 while i < len(ar) - 1: if ar[i] % 2 == ar[i + 1] % 2: ar[i] = ar[i] * ar[i + 1] del ar[i + 1] res += 1 else: i += 1 return res
- Check how many times the parity changes in the given array.
- The number of operations needed is the difference between the original length of the array and the count of parity changes.
def solve(): n = int(input()) ar = list(map(int, input().split())) # Count the number of times the parity changes in the array last_parity = None parity_count = 0 for x in ar: if x % 2 != last_parity: parity_count += 1 last_parity = x % 2 # The result is the difference between the original length and the count of parity changes res = n - parity_count print(res) for _ in range(int(input())): solve()