Przeskocz do treści

Delta mi!

Parzyste, nieparzyste

Jakub Radoszewski

o artykule ...

  • Publikacja w Delcie: kwiecień 2013
  • Publikacja elektroniczna: 30-03-2013

O zadaniu z Akademickich Mistrzostw Polski w Programowaniu Zespołowym (2012)

Zadanie. Powiemy, że ciąg liczb naturalnych jest math-parzysty, jeśli każdy jego math-elementowy spójny fragment ma parzystą sumę. Przykładowo, ciąg:

display-math

jest 5-parzysty, a ciąg:

display-math

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

obrazek

Następujące podejście jest bardzo naturalne. Suma pierwszych pięciu wyrazów ciągu math 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:

display-math

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ć:

display-math

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 math rozważać ciąg:

display-math

Oznaczmy przez math  binarny ciąg wynikowy (powstały z  math  poprzez minimalną liczbę zamian).

Dla dowolnego math sumy math  oraz math  muszą mieć tę samą parzystość. Stąd math  Widzimy zatem, że ciąg math  rozpada się na 5 podciągów stałych: math  itd.

Zapiszmy ciąg math  tak, aby wyrazy o indeksach różniących się o 5 znajdowały się jeden pod drugim:

|--|--|---|--|-|
|1-|0-|0--|0-|1|
|0-|-1|0--|1-|1|
|0 | 1|0  |1 | |
----------------
Wyrazy położone w tych samych kolumnach muszą stać się równe w ciągu math  Aby wykonać jak najmniej zamian, w pierwszej kolumnie ustawimy same zera, w drugiej – same jedynki, w trzeciej – zera, w czwartej i piątej – jedynki. Razem wyszły nam trzy zamiany. Jakie to proste!

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

|--|--|--|--|--|
|0-|1-|0-|1-|1-|
|0-|1-|0-|1-|1-|
|0 |1 |0 |1 |  |
---------------
Widzimy, że sumy wszystkich pięcioelementowych fragmentów ciągu są równe, ale – nieparzyste! No tak – widać, gdzie popełniliśmy błąd. Aby wszystkie sumy stały się parzyste, należałoby jedną z kolumn zmienić na odwrót. Najbardziej opłaca się wybrać kolumnę, która w tym układzie wymaga najmniej zamian: ustawiamy jedynki w pierwszej kolumnie (względnie zera w drugiej lub w czwartej). Ostatecznie wykonaliśmy cztery zamiany.

Oto uzyskany przez nas ciąg wynikowy:

display-math

oraz ciąg math po minimalnej liczbie zamian:

display-math