Parzyste, nieparzyste
O zadaniu z Akademickich Mistrzostw Polski w Programowaniu Zespołowym (2012)
Zadanie. Powiemy, że ciąg liczb naturalnych jest
-parzysty, jeśli
każdy jego
-elementowy spójny fragment ma parzystą sumę.
Przykładowo, ciąg:

jest 5-parzysty, a ciąg:

nie. Ile minimalnie wyrazów ciągu
trzeba zmienić, aby stał się on
5-parzysty?

Następujące podejście jest bardzo naturalne. Suma pierwszych pięciu wyrazów
ciągu
jest równa 16, jest więc parzysta – nic nie trzeba zmieniać. Suma
wyrazów od drugiego do szóstego jest równa 17 – to źle. Aby suma ta stała się
parzysta, wystarczy szósty wyraz ciągu zamienić na jakikolwiek nieparzysty, np.
na 1:

Teraz suma pięciu rozważanych wyrazów jest równa 12 – możemy iść dalej. Kolejny wyraz ciągu jest równy 3, a suma pięciu wyrazów kończących się na tym wyrazie to 13. Wystarczy zatem na siódmej pozycji ciągu wstawić jakąkolwiek liczbę parzystą, np. 2. Nowy ciąg ma postać:

Kontynuując to podejście, zmienimy jeszcze wyrazy 3, 6, 7 i 1. Niestety, wykonaliśmy w sumie sześć zamian, a da się lepiej.
Spróbujmy podejść do zadania bardziej metodycznie. Przede wszystkim
zauważmy, że znaczenie ma jedynie parzystość wyrazów ciągu. Wystarczy
więc, zamiast
rozważać ciąg:

Oznaczmy przez
binarny ciąg wynikowy (powstały z
poprzez
minimalną liczbę zamian).
Dla dowolnego
sumy
oraz
muszą mieć tę samą parzystość. Stąd
Widzimy zatem, że ciąg
rozpada się na
5 podciągów stałych:
itd.
Zapiszmy ciąg
tak, aby wyrazy o indeksach różniących się
o 5 znajdowały się jeden pod drugim:


Otóż... nie do końca. Zapiszmy nasz wynikowy ciąg:

Oto uzyskany przez nas ciąg wynikowy:

oraz ciąg
po minimalnej liczbie zamian:
