https://www.acmicpc.net/problem/1024
initial
I tried solving via 2 pointer like so
n, m = map(int, input().split())
lst = [i for i in range(1, n // 2 + 1)]
left, right = 0, 1
check = int(1e6)
ans = []
total = lst[0] + lst[1]
while left < right and right <= len(lst):
if total < n and right < len(lst):
right += 1
total += lst[right]
elif total == n:
if right - left + 1 < check:
ans = [i for i in range(lst[left], lst[right] + 1)]
check = len(ans)
total -= lst[left]
left += 1
else:
total -= lst[left]
left += 1
right += 1
if len(ans) == 0:
print(-1)
else:
print(*ans)
not sure how to make it work
solution
this is a arithmetic sum sequence. We get sum s and how many terms in that sequence to make that sum (n) from the input. We want to find a, the first term in the subsequence and if arithmetic sum formula fits, we print out the range from a to a+(n-1)d.
We are gonna iterate from n to 101 (not from 1 cuz the subequence length has to be at least n) and see if a is indeed an integer. We can check if it is an integer by numerator modulo denominator and if it is 0 and if it is greater or equal to -1 (cuz it has to be non negative), then we pring out from a+1 to a+i+1).
[I dont get it] when will a be -1? and Why do we have to do a+1 instead of from a? a is not 0-indexed so why?? i get that when a=-1, a+1 will make it 0 but when will a become -1 in the first place? and why +1??
s, n = map(int, input().split())
for i in range(n, 101):
a = s - i * (i + 1) / 2
if a % i == 0:
a = int(a / i)
if a >= -1:
print(*list(range(a +1, a + i + 1)))
exit()
print(-1)
complexity
n time and space
