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
      282
      5308
    2. Laitetaas nyt kirjaimet tänne

      kuka kaipaa ja ketä ?
      Ikävä
      68
      5248
    3. Kuka rääkkää eläimiä Puolangalla?

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

      Suru vai suuri helpotus...
      Puolanka
      52
      2830
    5. Pieni häivähdys sinusta

      Olet niin totinen
      Ikävä
      22
      2417
    6. Koska näit kaivattusi viimeksi

      Milloin tapasit rakkaasi? Ja etenikö suhde yhtään?
      Ikävä
      119
      2040
    7. 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ä
      47
      2000
    8. Lähetä terveisesi kaipaamallesi henkilölle

      Vauva-palstalta tuttua kaipaamista uudessa ympäristössä. Kaipuu jatkukoon 💘
      Ikävä
      99
      1727
    9. Tekiskö nainen mieli tavata...

      Viikonloppuna ja...?
      Ikävä
      72
      1261
    10. 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
      154
      1108
    Aihe