Informatyczny kącik olimpijski

123-Pairs

W tym odcinku omówimy rozwiązanie zadania "123-Pairs", które pojawiło się na "Code Festival 2016".

Zadanie (123-Pairs). Danych jest $2n$ liczb naturalnych od $1$ do $2n.$ Chcemy połączyć te liczby w $n$ par tak, aby każda liczba należała do dokładnie jednej pary. Dodatkowo, chcemy aby $|a$ par miało różnicę $1,$ $b$ par miało różnicę $|2$ oraz $c$ par miało różnicę $3.$ Innych par nie powinno być, tzn. $|a+ b + c = n.$ Na ile sposobów można poparować liczby od $1$ do $|2n?$ Należy podać resztę z dzielenia wyniku przez $|109 + 7.$

Przedział liczb naturalnych nazwiemy zamkniętym, jeśli liczby z tego przedziału są poparowane. Niech trójka $′ ′ ′ (a ,b ,c)$ opisuje zamknięty przedział, który zawiera $a′$ par o różnicy $1,b′$ par o różnicy $|2$ oraz $|c′$ par o różnicy $3.$

Cały artykuł dostępny jest w wersji do druku: (316 KB)