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

Anonyymi

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

4

192

    Vastaukset

    Anonyymi (Kirjaudu / Rekisteröidy)
    5000
    • 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

    Ketjusta on poistettu 0 sääntöjenvastaista viestiä.

    Luetuimmat keskustelut

    1. Useita puukotettu Tampereella

      Mikäs homma tämä nyt taas on? "Useaa henkilöä on puukotettu Tampereen keskustassa kauppakeskus Ratinan lähistöllä." ht
      Tampere
      243
      4629
    2. Kuka rääkkää eläimiä Puolangalla?

      Poliisi ampui toistakymmentä nälkiintynyttä eläintä Puolangalla Tilalta oli ollut karkuteillä lähes viisikymmentä nälkii
      Puolanka
      76
      3065
    3. Leipivaaran päällä on kuoleman hiljaista.

      Suru vai suuri helpotus...
      Puolanka
      47
      2473
    4. Meneeköhän sulla

      oikeasti pinnan alla yhtä huonosti kuin mulla? Tai yhtä huonosti mutta jollain eri tyylillä? Ei olisi pitänyt jättää sua
      Ikävä
      45
      1777
    5. Laitetaas nyt kirjaimet tänne

      kuka kaipaa ja ketä ?
      Ikävä
      28
      1753
    6. Koska näit kaivattusi viimeksi

      Milloin tapasit rakkaasi? Ja etenikö suhde yhtään?
      Ikävä
      80
      1456
    7. Lähetä terveisesi kaipaamallesi henkilölle

      Vauva-palstalta tuttua kaipaamista uudessa ympäristössä. Kaipuu jatkukoon 💘
      Ikävä
      85
      1285
    8. PS uusimman gallupin rakettimainen nousija

      https://yle.fi/a/74-20170641 Aivan ylivoimaisesti suurin kannatuksen nousu PS:lle. Nousu on alkanut ja jatkuu 2 vuoden
      Maailman menoa
      143
      965
    9. Tekiskö nainen mieli tavata...

      Viikonloppuna ja...?
      Ikävä
      69
      948
    10. Sellainen tunne sydämessä

      Että nainen olet kaivannut minua. Tai sanonko että oikeastaan koet sitä samaa nostalgiaa, kaipuuta ja mukavia muistoja,
      Ikävä
      86
      894
    Aihe