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).
Kokonaispisteet kolmiossa
Anonyymi
5
192
Vastaukset 5
- 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 = 2389472394671246172423847923847289461284627Jos 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
Ampuminen kylpylässä
Onko vornasen timbe käynyt hiukan kylpemässä vai mikä tämä ampumatapaus on kylpylässä? Tuntuu aika villi meno olevan naa861966Kemijärvellä vesionnettomuus
Pitkänsillan ja taiteilijanniemen välillä nähty henkilön painuvan veden alle. Mitä on tapahtunut? Onko vesihiisi taas as381270Hei, voitko kuunnella
Voisitko auttaa minua selvittämään asioita? En halua ajaa sinua hulluuteen kanssani, en sitoa sinua, en esittää vaatimu134974Joku porukka lähtenyt täältä
Ihmeen hiljainen on palsta nyt. Yleensä tänne tulvii aloituksia yms, mutta nyt on kyllä erikoisen hiljaista.201893- 77781
- 90774
Olipa yllätys
Kuten hyvin moni tiesi/arvasi että valetta alusta loppuun toi *olemme ystäviä* satu. Instassaan käsi kädessä kuva kertoo213688- 67657
On todella ikävää
Todella ikävää, että asiat ovat menneet tällaisiksi. Tämä ei ollut missään vaiheessa tarkoitukseni. Olen tehnyt virheit79628Se kun olit pitkästä aikaa silmieni edessä
Oli kyllä sykähdyttävää. Tiedätkö, mikä laittaa minut ikävöimään sinua? Kun palautan mieleeni valtavan ihanan olemuksen,46628- 64584
- 35581
- 37541
- 55517
Oletteko koskaan torjuneet kaivattuanne?
Minä olen, kun en silloin tajunnut vielä ihastuneeni. Yritin paikata tapahtunutta, mutta ei onnistunut enää.25467Kai sä mies ymmärrät..
..ettet jättänyt vaihtoahtoa. Tottakai toivon vielä, että pystyisit toimimaan niin että asiat korjaantuisivat. Vahvast28452- 35444
Hämmentävä hetki: TTK:sta pudonnut Johanna Puhakka lataa pettyneenä: "Sitä ei voi kieltää"
Johanna Puhakka ja Jurijs Jurza Trosenko tippuivat Tanssii Tähtien Kanssa -kisasta. Suositussa viihdeohjelmassa nähtiin13439- 33433
- 40427