A. Garland
B. Detective Book
C. Points on Plane
def solve(): n = int(input())
def check(k):
return (k + 1) ** 2 >= n
l = 0
r = 10**9
ans = float("inf")
while l <= r:
mid = (l + r) // 2
if check(mid):
ans = min(mid,ans)
r = mid - 1
else:
l = mid + 1
print(ans)for _ in range(int(input())): solve()
<spoiler summary="Code2">
import math
def solve(): n = int(input())
ans = math.isqrt(n-1) print(ans)
for _ in range(int(input())): solve()
</spoiler>
### [D. Good String](https://codeforces.net/gym/558367/problem/D)
<spoiler summary="Tutorial">
Let's analyze when the string is good. Suppose it is t1t2…tk
.
The cyclic shifts of this string are tkt1t2…tk−1
and t2t3…tkt1
. We get the following constraints for a good string: tk=t2
, t1=t3
, t2=t4
, ..., tk−2=tk
, tk−1=t1
. If the string has odd length, then all characters should be equal to each other; otherwise, all characters on odd positions should be equal, and all characters on even positions should be equal.
Now, since there are only 10
different types of characters, we can brute force all possible combinations of the first and the second character of the string we want to obtain (there are only 100
of them) and, for each combination, greedily construct the longest possible subsequence of s
beginning with those characters in O(n)
.</spoiler>
<spoiler summary="Code">
def solve(s, x, y): res = 0 for c in s: if int(c) == x: res += 1 x, y = y, x if x != y and res % 2 == 1: res -= 1 return res
for _ in range(int(input())): s = input() ans = 0 for x in range(10): for y in range(10): ans = max(ans, solve(s, x, y)) print(len(s) — ans) ```
E. Playlist
The problem is about choosing up to k songs from a playlist, where each song has a length and a beauty. The goal is to maximize the pleasure of listening, which is calculated as the sum of the selected song lengths multiplied by the smallest beauty among those songs.
The intuition behind this problem is to maximize the total pleasure by carefully balancing two things: the total length of the songs you choose and the beauty of those songs. Since pleasure depends on both, the trick is to first focus on beauty because it acts as a multiplier. Higher beauty means we get a bigger boost in pleasure, so it makes sense to start by considering the most beautiful songs first.
However, we also need to manage the total length of the songs we pick, since adding longer songs can increase the total pleasure. But we can only select up to k songs, so if we reach the limit, we should drop the shortest song to keep the sum of lengths as large as possible. This way, we get the best combination of beauty and length to maximize the pleasure.
We can solve this problem by first sorting the songs in descending order of beauty, so we prioritize songs with higher beauty values. As we process each song, we maintain a running total of the song lengths using a min-heap. If the number of selected songs exceeds k, we remove the smallest length to keep the total as large as possible. At each step, we compute the pleasure by multiplying the current total length by the beauty of the song we're considering, and we update the maximum pleasure accordingly. This approach ensures we maximize the pleasure by balancing the sum of lengths and the minimum beauty.
- Code by Kalki75
n, k = map(int,input().split())
nums = []
for _ in range(n): t, b = map(int,input().split()) nums.append([t,b])
nums.sort(reverse = True, key= lambda x: x[1])
heap = [] ans = 0 total = 0
for i in range(n): time, beauty = nums[i] total += time
if len(heap) < k:
heappush(heap,(time,beauty))
else:
min_time, min_beauty = heappop(heap)
heappush(heap,(time,beauty))
total -= min_time
ans = max(ans,total*beauty)print(ans) ```
