panettiere con valanga di spiccioli

[jordan]

una "gentile" vecchietta va dal panettiere, portando con sè tutti centesimi di poco valore, cioè solo da 1, 2, 5, 10 e 20cent. se la pagnotta di pane costa un numero intero positivo n di euro, in quanti modi la vecchietta malefica potrà pagare allo sfortunato?

NB si assuma che ha appena rotto un salvadanaio enorme e quindi porta un borsone di centesimi
NB per legge è noto che esiste un limite per pagare una certa somma in spiccioli, ma consideriamo che la vecchietta infranga tranquillamente il codice
NB credo sia il piu orribile problema che abbia mai postato

[pa]

lo sai che e' molto simile a un problema dei regionali dell'anno scorso di informatica?

[jordan]

si lo so, ma la differenza è che io non voglio l'algoritmo
(viene da un vecchissimo test sns)

[caino]

Completamente off topic, o forse no. In un refettorio americano 29 studenti hanno deciso che per protestare contro la pausa pranzo troppo corta avrebbero pagato con solo monete da un cent. Si son fatti 2 giorni di carcere! Notizia letta sull'ansa l'altro ieri. (/OT)
Comunque non penso che il problema sia così brutto...

[jordan]

be non si cimenta nessuno nel problema (oggettivamente) piu brutto dell'anno?

[Californication]

perchè non "cementarsi"...

Non perdo di generalità se dico che per arrivare a un euro la gentile vecchietta deve mettere insieme 5 mucchi assortiti da 20 centesimi, infatti comunque io metta le monetine, per i 20 centesimi ci devo passare visto che la graziosa ottuagenaria ha pensato bene di non portarsi monete da 50 centesimi...inoltre, per mettere insieme i suoi schifosi 20 centesimi o si prende direttamente un monetone da 20 o passa per i 10 centesimi, vediamo quindi che, potendo assortire mucchi da 10 centesimi in 11 modi (6 modi con monete da 1 e 2 cent, 4 includendo anche le monete da 5 e uno con la moneta da 10) può raccogliere 20 cent in 11x2 modi passando per i 10 cent + 1 col monetone, quindi arriva a un euro in 23x5=115 modi e quindi a n euro in 115n modi...non so se va bene ma se mi capita al test venerdì giuro che ci sto più attento...

*ok meglio se ci riprovo

magari un problema più interessante sarebbe quello di vedere in quanti modi il panettiere può restituire alla simpatica nonnina i soldi e tenersi il pane sapendo che per legge "nessuno è obbligato ad accettare più di cinquanta monete metalliche in un singolo pagamento"

[Californication]

ok è tanto brutto

[FeddyStra]

... quindi arriva a un euro in 23x5=115 modi

Ti dico solo che in realtà sono $ 4111 $. Credo che tu ne abbia saltato qualcuno...

[Californication]

sì grazie me ne sono reso conto apparte che per fare una cosa corretta avrei dovuto chiaramente elevare a potenza, ma comunque ne avrei considerati troppi in quel caso perchè ci sarebbero state combinazioni comuni

[FeddyStra]

Compito di punizione
Trovare i primi 3000 coefficienti nella serie di Maclaurin di $ \displaystyle \frac{1}{(1-x) \left(1-x^2\right) \left(1-x^5\right) \left(1-x^{10}\right) \left(1-x^{20}\right)} $.