Link do treści zadania: https://szkopul.edu.pl/problemset/problem/pAy3KzzMQ8Gh-LFsyL0tZts6/site/?key=statement
Cześć, rozwiązuje zadanie Wycinek. Moim rozwiązaniem jest najpierw liczenie sum prefiksowych, potem zapisywanie kandydatów (liczb, które prefi[i]+s in prefi), a na końcu wybieram największa rożnice elementów prefi[i]+s - prefi[i]. Niestety nie mogę wyłapać 2 błedów:
Pierwszy błąd polega na tym, że zamiast wypisywać BRAK, wypisuje mi liczbe całkowitą. Drugi błąd jest taki, że wynik jest większy niż powinien być. Podejrzewam, że chodzi o coś z sumami prefiksowymi.
Mój kod w pythonie:
n, s = map(int, input().split())
ciag = list(map(int, input().split()))
sum_pref = [0]
odp = 0
kandydaci = dict()
# liczenie sum prefiksowych
for i in range(n):
sum_pref += [sum_pref[-1]+ciag[i]]
a = set(sum_pref) #Tworze seta, żeby było stałe wyszukiwanie sum_pref[i]+s w sumach pref.
# dodawanie kandydatów
for i in range(n):
if sum_pref[i]+s in a:
if sum_pref[i] not in kandydaci:
kandydaci[sum_pref[i]] = i
# Szukanie najwiekszej róznicy sum_pref[i]-s - sum_pref[i]
odp = 0
for i in range(1, n+1):
if sum_pref[i]-s in kandydaci:
odp = max(odp, abs(i-kandydaci[sum_pref[i]-s]))
# Jeżeli odpowiedz jest rowna 0, to oznacza to, że nie ma żadnego takiego podciagu
if odp == 0:
print('BRAK')
else:
print(odp)
