Kokonaispisteet kolmiossa

Anonyymi

Annettuna on positiiviset kokonaisluvut a, b ja n.
Tehtävänä on laskea kuinka monta on kokonaislukupareja (x, y), joille x, y>=1 ja ax by<=n.

Laskenta-algoritmin tulisi olla sen verran tehokas, että se selviää jopa suuruusluokkaa n=10^100 olevista tapauksista (joissa a ja b ovat esim. alle 1000).

5

140

    Vastaukset

    Anonyymi (Kirjaudu / Rekisteröidy)
    5000
    • Anonyymi

      Helppo integroida paloittain ja käyttää sitten aritmeettista summakaavaa ja lisätä lopuksi vajaajaksoinen osuus.

      n = 1234567890#12#3#4#567890123456789012345678901234567890123456789012345678901234567890
      b = 779
      a = 883
      ab = a*b
      m = n - n % ab
      p = m//ab
      c = 0
      for x in range(1,b 1): c = (n-x*a)//b
      cc = p*(c-(p-1)*ab c)//2
      c = 0
      for x in range(m//a 1,n//a 1): c = (n-x*a)//b
      print(c)
      cc = c
      print(cc)


      Ei yhtään sisennystä. Voi kopsata suoran. Aikaa kuluu isoilla luvuilla lähinnä tulostamiseen.

      Toiminnan voi testata pienillä luvuilla yksinkertaisella varmasti toimivalla integrointisilmukalla:

      n = 123456789012#3#4
      b = 779
      a = 883
      c = 0
      for x in range(1,n//a 1): c = (n-x*a)//b
      print (a,b,n,c)

      Kannattaa käyttää Pypyä. Yli 30 kertainen nopeutus. Jos käyttää Python 2:sta, range on korvattava xrange:lla. Silmukka lyhenee, jos laittaa isomman luvun aina a:ksi. Aluksi kannattaa kokeilla "pienillä" n//a arvoilla, jotta näkee mihin kone pystyy. Heti kun c kasvaa yli 63-bittiseksi, toiminta hidastuu.

      • Anonyymi

        Joo, hyvin toimii. Muuten, jos korvaa summaussilmukan sum():lla, niin ei tarvitse välittää onko x- vai range ja eikös se olisi Pythonmaisempaa? Eli esim.

        c = 0
        for x in range(1,b 1): c = (n-x*a)//b

        voisi korvata

        c = sum((n-x*a)//b for x in range(1, b 1))


      • Anonyymi
        Anonyymi kirjoitti:

        Joo, hyvin toimii. Muuten, jos korvaa summaussilmukan sum():lla, niin ei tarvitse välittää onko x- vai range ja eikös se olisi Pythonmaisempaa? Eli esim.

        c = 0
        for x in range(1,b 1): c = (n-x*a)//b

        voisi korvata

        c = sum((n-x*a)//b for x in range(1, b 1))

        Ei Python 2:n range-ongelma mihinkään katoa tuon sum:in kanssa. Siihähän on se ihan sama range. Eikä mitään ongelmaa ei ole pienillä range-arvoilla. b 1 on mitättömän pieni!

        Kokeile joksus Python 2:lla:
        for x in range(0,1234567890):

        Pienennä rangea sitten, kunnes ei tule enää muisti-erroria ja katso sitten montako Gtavua kuluu muistia. Kokeile sitten xrangella. Ei kulu yhtään muistia!

        Pypyn kanssa ei kannata ikinä käyttää mitään turhia erikoiskäskyjä tai rakenteita tai kirjasto-ohjelmia. Nytkin tuli sum:n kanssa yli kaksinkertainen hidastus. Sai odottaa minuuttikaupalla valmistumista. Kokeile sillä lopussa olevalla perusohjelmalla.

        Miten lisäät tilapäisiä testitulostuksia tuon sum:n kanssa? Niitä tarvitaan aina. Jotain iloa saatta olla joissakin erikoistilanteissa.

        Tiedätkö yhtään varmaa tulosta, jos n on yli 20-numeroinen?


      • Anonyymi
        Anonyymi kirjoitti:

        Ei Python 2:n range-ongelma mihinkään katoa tuon sum:in kanssa. Siihähän on se ihan sama range. Eikä mitään ongelmaa ei ole pienillä range-arvoilla. b 1 on mitättömän pieni!

        Kokeile joksus Python 2:lla:
        for x in range(0,1234567890):

        Pienennä rangea sitten, kunnes ei tule enää muisti-erroria ja katso sitten montako Gtavua kuluu muistia. Kokeile sitten xrangella. Ei kulu yhtään muistia!

        Pypyn kanssa ei kannata ikinä käyttää mitään turhia erikoiskäskyjä tai rakenteita tai kirjasto-ohjelmia. Nytkin tuli sum:n kanssa yli kaksinkertainen hidastus. Sai odottaa minuuttikaupalla valmistumista. Kokeile sillä lopussa olevalla perusohjelmalla.

        Miten lisäät tilapäisiä testitulostuksia tuon sum:n kanssa? Niitä tarvitaan aina. Jotain iloa saatta olla joissakin erikoistilanteissa.

        Tiedätkö yhtään varmaa tulosta, jos n on yli 20-numeroinen?

        Joo sori, siellähän se sama range on sisällä. Tajusin just vähän aikaa sitten itsekin. Jotenkin ajattelin, että sum():ssa on niinkuin oma juttunsa, mutta iterable:han sille pitää antaa.

        Niin kieltämättä sitä aina huomaa että haluaisi lisätä tulostuksen tai jotain muuta, niin se pitää muuttaa kun sen on tehnyt sum():lla, lambda:na, listakoostamisena tms.

        Olen melko varma esim. tuloksesta

        31081669306331872406696219768357999389733129838639415077188983595219295535916013

        parametreille

        a = 712
        b = 129
        n = 2389472394671246172423847923847289461284627


      • Anonyymi
        Anonyymi kirjoitti:

        Joo sori, siellähän se sama range on sisällä. Tajusin just vähän aikaa sitten itsekin. Jotenkin ajattelin, että sum():ssa on niinkuin oma juttunsa, mutta iterable:han sille pitää antaa.

        Niin kieltämättä sitä aina huomaa että haluaisi lisätä tulostuksen tai jotain muuta, niin se pitää muuttaa kun sen on tehnyt sum():lla, lambda:na, listakoostamisena tms.

        Olen melko varma esim. tuloksesta

        31081669306331872406696219768357999389733129838639415077188983595219295535916013

        parametreille

        a = 712
        b = 129
        n = 2389472394671246172423847923847289461284627

        Jos vaihtaa a:n ja b:n arvot, tuloksen on tietysti oltava sama. Jos ohjelmassa a ja b ovat epäsymmetrisesti, niin olisiko viallisen ohjelman mahdollista tuottaa molemmilla tavoilla aina sama tulos? Ja useilla eri a:n ja b:n ja n:n arvoilla.


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

    Luetuimmat keskustelut

    1. Suureksi onneksesi on myönnettävä

      Että olen nyt sitten mennyt rakastumaan sinuun. Ei tässä mitään, olen kärsivällinen ❤️
      Ikävä
      85
      1788
    2. Perusmuotoiset TV-lähetykset loppu

      Nyt sanoo useiden HD-muotoistenkin kanavien kohdalla äly-TV, ettei kanava ole käytössä, haluatko poistaa sen? Kanavia
      Apua aloittelijalle
      120
      1204
    3. YLE Äänekosken kaupunginjohtaja saa ankaraa arvostelua

      Kaupungin johtaja saa ankaraa kritiikkiä äkkiväärästä henkilöstöjohtamisestaan. Uusin häirintäilmoitus päivätty 15 kesä
      Äänekoski
      62
      1070
    4. No ei sun asunto eikä mikään

      muukaan sussa ole erikoista. 🤣 köyhä 🤣
      Ikävä
      62
      946
    5. Hyvin. Ikävää nainen,

      Että vainoat ja stalkkaat miestäni.onko tarkoituksesi ehkä saada meidät eroamaan?no,siinä et tule onnistumaan
      Ikävä
      74
      866
    6. Uskomaton tekninen vaaliliitto poimii rusinoita pullasta

      Korni näytösesitelmä menossa kaupunginvaltuustossa. Juhlia ei ole kokouksista tiedossa muilla, kuin monipuolue paikalli
      Pyhäjärvi
      81
      817
    7. Linnasuolla poliisi operaatio

      Kamalaa menoa taas meidän ihanassa kaupungissa. https://www.uutisvuoksi.fi/paikalliset/8646060
      Imatra
      29
      816
    8. Mitä mietit Honey?

      Kulta nainen ❤️❤️
      Ikävä
      57
      810
    9. Katsoin mies itseäni rehellisesti peiliin

      Ja pakko on myöntää, että rupsahtanut olen 😆. Niin se ikä saavuttaa meidät kaikki.
      Ikävä
      46
      810
    10. Martina lähdössä Ibizalle

      Eikä Eskokaan tiennyt matkasta. Nyt ollaan jännän äärellä.
      Kotimaiset julkkisjuorut
      116
      773
    Aihe