[problem:430380A]
Try Binary Search.
Use binary search to find the position of the smallest name larger than the given name.
from sys import stdin
n = int(stdin.readline().strip())
queue = list(stdin.readline().strip().split())
q = int(stdin.readline().strip())
for _ in range(q):
left, right = 0, n - 1
val = stdin.readline().strip()
best = len(queue)
while left <= right:
mid = (left + right) // 2
if queue[mid] < val:
left = mid + 1
else:
best = mid
right = mid - 1
print(best)
from sys import stdin
import
n = int(stdin.readline().strip())
queue = list(stdin.readline().strip().split())
q = int(stdin.readline().strip())
for _ in range(q):
left, right = 0, n - 1
val = stdin.readline().strip()
print(bisect_right(queue, val))
[problem:430380B]
Given a choice of dividers which one would give you the most outlets and how much.
Given a choice of dividers the one with the maximum value of outlets would have the most outlets, if we say the chosen divider has ai outlets and we initially have s outlets after using the divider we would have s + ai — 1 since we have to use one of the existing outlets. Until we have enough outlets repeat this.
testcases = int(input())
for i in range(testcases):
students, m = map(int, input().split())
dividers = list(map(int, input().split()))
dividers.sort(reverse=True)
outlets = 2
dividers_used = 0
while dividers_used < m and outlets < students:
outlets += dividers[dividers_used] - 1
dividers_used += 1
if outlets < students:
print(-1)
else:
print(dividers_used)
[problem:430380C]
Try to see the different kinds of ways of using the elevator and stairs.
There are 2^4 ways of arranging elevators and stair moves. Out of these arrangements, there are only some that make sense.
These are a different kind of arrangements: e, e, s, s; e, s, s, s; s, e, e, e...
Out of these configurations we can see that once we start using the elevator it doesn't make sense to go back to the stairs since if the elevator is less efficient than the stairs you shouldn't take the elevator but if not you should continue using the elevator since going back to the stairs wouldn't give you any better time. So the configurations you have to check are: use stairs only, walk to the elevator then use it, and use the elevator only.
t = int(input())
for i in range(t):
wt, et, ef = list(map(int, input().split()))
# stairs, walk then elevator, use elevator only
print(min(wt * 4, wt * (ef) + et * (4 - ef), et * (ef + 4)))
[problem:430380D]
Find a way to count subarrays with a sum less than some value x.
To find subarrays with a sum less than some value x we will use a sliding window, we expand our window until adding the next element would make its sum exceed x then we can be sure there are len(sliding window) subarrays with sum less than x since all the numbers are positive. To find subarrays with a sum between l and r, find the number of subarrays with a sum less than r + 1 and l then the answer would be the difference.
n, start, end = map(int, input().split())
nums = list(map(int, input().split()))
def sub_arrays_with_sum_less_than(target):
runningSum = answer = left = 0
for right in range(len(nums)):
runningSum += nums[right]
while runningSum >= target:
runningSum -= nums[left]
left += 1
answer += right - left + 1
return answer
print(sub_arrays_with_sum_less_than(end + 1) - sub_arrays_with_sum_less_than(start))
[problem:430380E]
Think of merge sort.
We can notice that single-elimination bracket and merge sort have a similar process. We can leverage our knowledge in implementing the simulation for the game. But we have other rules, namely, we say a player has a possibility of moving forward if either there is a player with a lower rating or with absolute diff less than k. So if we can plug the check for winning possibility we can successfully simulate the game and find our possible winners.
from sys import stdin, stdout
# Reading input values from standard input
n, k = map(int, stdin.readline().split())
arr = list(map(int, stdin.readline().split()))
# Function to recursively solve the problem
def solve(i, count, k):
# Base case, when only one element is left in a sub-array
if count == 1:
return [i]
# Divide the sub-array into two halves and solve each recursively
left = solve(i, count // 2, k)
right = solve(i + (count // 2), count // 2, k)
# Merge the two sorted halves while checking the difference between elements
merged = []
l_ptr = r_ptr = 0
left_min, right_min = arr[left[0]], arr[right[0]]
while l_ptr < len(left) and r_ptr < len(right):
if arr[left[l_ptr]] <= arr[right[r_ptr]]:
if right_min - arr[left[l_ptr]] <= k:
merged.append(left[l_ptr])
l_ptr += 1
else:
if left_min - arr[right[r_ptr]] <= k:
merged.append(right[r_ptr])
r_ptr += 1
# Add any remaining elements from left or right halves while checking the difference between elements
while l_ptr < len(left) and right_min - arr[left[l_ptr]] <= k:
merged.append(left[l_ptr])
l_ptr += 1
while r_ptr < len(right) and left_min - arr[right[r_ptr]] <= k:
merged.append(right[r_ptr])
r_ptr += 1
# Return the merged and sorted sub-array
return merged
# Print the sorted and transformed sub-array obtained by calling the solve() function
print(*sorted(map(lambda x: x + 1, solve(0, 2**n, k))))
[problem:430380F]
Try to see how to check if an index can be a start for a new bus.
Any multiple of 6 greater than 6 can be described as a linear combination of 12 and 18.
Find the sum of a subarray with size 12 that started at 0 or 6 * b + 1, b being a positive integer.
from sys import stdin
t = int(stdin.readline().strip())
for _ in range(t):
n = int(stdin.readline().strip())
nums = list(map(int, stdin.readline().split()))
prefix_sums = []
running_sum = 0
for num in nums:
running_sum += num
prefix_sums.append(running_sum)
# To avoid having to check if i - 1 is out of bounds
prefix_sums.append(0)
# The best we can do is to take the first 12
best = prefix_sums[min(n - 1, 11)]
for i in range(12, n, 6):
# Check if the next 12 is better than the current best
best = min(best, prefix_sums[min(i + 11, n - 1)] - prefix_sums[i - 1])
print(best)
[problem:430380G]
Try to see what kinda pairing creates optimal time.
The optimal matching starts by considering the smallest 2 ^ n — 1 as a base and changing the elements to be paired, then moving the window by 2 ^ n — 2, 2 ^ n — 3... and so on. The element determining the session time will be the largest among the elements in the current window and we can run the 2 ^ n — 1 then 2 ^ n — 2 then 2 ^ n -3... session for each window respectively.
n, k = list(map(int, input().split()))
nums = sorted(list(map(int, input().split())), reverse=True)
curr = 1 << n
total = 0
while k > 0:
curr //= 2
total += min(k, curr) * nums[curr]
k -= min(k, curr)
print(total)
Auto comment: topic has been updated by a2sv (previous revision, new revision, compare).
Nice! Thanks for taking the time to write the solutions for the problems :) Much appreciated.