Problemi 025

Kërkesa

Një sistem monetar ka prerje (ose monedha) me vlerë: 1, 2, 5, 10, 50, 100. Bëni një program që gjen numrin më të vogël të monedhave që e kanë shumën sa një vlerë e dhënë N.

Referenca: https://www.codechef.com/problems/FLOW005

Shembull

$ cat input.txt
3
1200
500
242

$ python3 prog.py < input.txt
12
5
7

Zgjidhja

prerjet = [100, 50, 10, 5, 2, 1]

for _ in range(int(input())):
    N = int(input())
    nr = 0
    for p in prerjet:
         nr += N // p
         N %= p
    print(nr)

Sqarime

Në listën prerjet mbajmë vlerat e prerjeve të renditura në rendin zbritës. Për një numër të dhënë N, gjejmë sa herë hyn prerja më e madhe në të, pastaj sa herë hyn prerja pasardhëse në vlerën e mbetur, e kështu me radhë.

Detyra

Çufoja ka bërë N copa keku të vogla dhe tani po mendon si ti paketojë. Çdo paketë duhet të ketë numër të njëjtë kekësh. Çufoja duhet të zgjedhë një numër të plotë A, nga 1 në N, dhe duhet të vendosë fiks A copa keku në çdo paketë. Pasi ka plotësuar aq paketa sa të jetë e mundur, copat e kekut që kanë mbetur pa paketuar Çufoja mund ti hajë vetë. Çufos i pëlqejnë shumë këta dreq kekë. Sa duhet ta zgjedhë numrin A të paketimit që ti mbeten sa më shumë copa keku për të ngrënë?

Bëni një program që merr numrin N dhe gjen numrin A, ku \(2 \leq N \leq 100000000 (10^8)\) Ky program duhet ta kthejë përgjigjen në më pak se 1 sek.

Referenca: https://www.codechef.com/problems/MUFFINS3

Shembull

$ cat input.txt
2
2
5

$ python3 prog.py < input.txt
2
3