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
136
Vastaukset
- 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
- 477705
- 334263
- 573745
- 503210
- 172896
Voi ei! Jari Sillanpää heitti keikan Helsingissä - Hämmästyttävä hetki lavalla...
Ex-tangokuningas on parhaillaan konserttikiertueella. Hän esiintyi Savoy teatterissa äitienpäivänä. Sillanpää jakoi kons652621- 642498
- 552421
- 402349
- 162296