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
Ohjelmointihaaste: ylös, alas kävelyt, joille korkeusvaihtelu on korkeintaan r
4
87
Vastaukset
- Anonyymi
Perus tietorakennealgoritmi. Kaikki kävelyt löytyvät n-syvästä binääripuusta, lisää vain läpikäyntialgoritmiin korkeuserolaskin jolloin haara hylätään jos r ylittyy. Samalla lasket moneenko latvasolmuun päästiin.
- Anonyymi
Paljonko saat tapaukselle r=7, n=2020?
- Anonyymi
Näin se Windows 10 korruptoi kiintolevyn, bioksen halkaisee, prossut se hitsaa jne.
- Anonyymi
Tässä minun ajatuksiani tehtävästä: http://membolicsythod.home.blog/2020/08/26/rajoitettu-vaihteluvaliset-kavelyt/
Eli rojahdutetaan se (rajoitettu) binääripuu niin, että lopulta jää r 1 eri väliä, joille voidaan jäädä seilaamaan.
Ketjusta on poistettu 0 sääntöjenvastaista viestiä.
Luetuimmat keskustelut
Voitasko leikkiä jotain tunnisteleikkiä?
Tietäisi ketä täällä käy kaipaamassa.. kerro jotain mikä liittyy sinuun ja häneen eikä muut tiedä. Vastaan itsekin kohta852268- 501964
Tietysti jokainen ansaitsee
Hän varmasti ansaitsee vain parasta ja sopivinta tietenkin, suon sen onnen hänelle enemmän kuin mielelläni. Aika on nyt231848Jotain puuttuu
Kun en sinua näe. Et ehkä arvaisi, mutta olen arka kuin alaston koivu lehtiä vailla, talven jäljiltä, kun ajattelen sinu83174350+ naiset kyl
Lemottaa sillille mut myös niitte kaka lemottaa pahlle ku kävin naiste veskis nuuhiin101608- 771532
hieman diabetes...
Kävin eilen kaverin kanssa keskusapteekissa kun on muutama kuukausi sitten tullut suomesta ja oli diabetes insuliinit lo241413Välitän sinusta mies
Kaikki mitä yritin kertoa tänään ei mennyt ihan putkeen..Joka jäi jälkeenpäin ajateltuna suoraan sanottuna harmittaa aiv61372Hei A, osaatko
sanoa, miksi olet ihan yhtäkkiä ilmestynyt kaveriehdotuksiini Facebookissa? Mitähän kaikkea Facebook tietää mitä minä en371347- 721331