Ohjelmointihaaste: ylös, alas kävelyt, joille korkeusvaihtelu on korkeintaan r

Anonyymi kirjoitti:

Olkoot r ja n positiivisia kokonaislukuja. Tehtävänä on laskea tietynlaiset n:n askeleen kävelyt. Mahdolliset askeleet ovat ylös ( 1) ja alas (-1). Kävelyn w täytyy toteuttaa ehto maxH(w) - minH(w) <= r. Tässä maxH(w) tarkoittaa korkeutta, jolla kävely korkeimmillaan käy ja minH(w) korkeutta, jolla kävely matalimmillaan käy. Voidaan olettaa, että kävely lähtee nollasta. Formaalisti tämä voidaan ilmaista näin: Kysytään seuraavan joukon kokoa

{ w on kielen {-1, 1}* sana : |w|=n, max_j=1...n {sum(w[:j])} - min_j=1...n {sum(w[:j])} >= r }

Esimerkki, jossa r = 2 ja n = 5:
Sana w = ↓ ↑ ↑ ↓ ↑, kelpaa koska sen korkeus menee -1, 0, 1, 0, 1 ja tämän vaihteluväli on 1 - (-1) = 2. Mutta w = ↓ ↑ ↑ ↑ ↓ ei kelpaa, koska se käy korkeuksilla -1, 0, 1, 2, 1, jolloin väli on 2 - (-1) = 3 > 2.

Tarkoitus on siis tehdä algoritmi, joka laskee tuon lukumäärän, kun parametrit r ja n on annettu. Tässä testitapauksia (muodossa (r, n) ), joille algoritmin täytyisi ainakin toimia:

testCases = [
(1, 3),
(2, 3),
(2, 4),
(2, 7),
(3, 5),
(3, 12),
(4, 15),
(5, 16),
(2, 20),
(2, 109),
(3, 67),
(3, 174),
(11, 23),
(12, 43),
(15, 38),
(21, 45),
(3, 923),
(2, 242398),
(4, 923847),
(2, 12345678910),
]

Lisäksi, koska isoissa tapauksissa luvuista tulee hyvin suuria, niin ilmoitettakoon vastaukset (ja laskennan saa tehdä) modulo 7347249713

MOD = 7347249713

kirjoitti:

Anonyymi

Kirjoita kommentti

5000

Lähetä