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
192
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
Useita puukotettu Tampereella
Mikäs homma tämä nyt taas on? "Useaa henkilöä on puukotettu Tampereen keskustassa kauppakeskus Ratinan lähistöllä." ht2434629Kuka rääkkää eläimiä Puolangalla?
Poliisi ampui toistakymmentä nälkiintynyttä eläintä Puolangalla Tilalta oli ollut karkuteillä lähes viisikymmentä nälkii763065- 472473
Meneeköhän sulla
oikeasti pinnan alla yhtä huonosti kuin mulla? Tai yhtä huonosti mutta jollain eri tyylillä? Ei olisi pitänyt jättää sua451777- 281753
- 801456
Lähetä terveisesi kaipaamallesi henkilölle
Vauva-palstalta tuttua kaipaamista uudessa ympäristössä. Kaipuu jatkukoon 💘851285PS uusimman gallupin rakettimainen nousija
https://yle.fi/a/74-20170641 Aivan ylivoimaisesti suurin kannatuksen nousu PS:lle. Nousu on alkanut ja jatkuu 2 vuoden143965- 69948
Sellainen tunne sydämessä
Että nainen olet kaivannut minua. Tai sanonko että oikeastaan koet sitä samaa nostalgiaa, kaipuuta ja mukavia muistoja,86894