Problemi 013

Kërkesa

Ju e dini që \(n! = 1*2*3*...*n\). Le të përkufizojmë funksionin \(z(n)\) si numrin e zerove që ka në fund \(n!\). Vini re që ky është një funksion jo-zbritës, d.m.th. për \(n_1 < n_2\) kemi \(z(n_1) \leq z(n_2)\). Kjo ndodh sepse kur e shumëzojmë një numër që ka zero në fund me një tjetër, numri i zerove që janë në fund vetëm mund të rritet.

Bëni një program që gjen \(z(n)\) (d.m.th. sa zero ka në fund \(n!\)).

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

Shembull

$ cat input.txt
6
3
60
100
1024
23456
8735373

$ python3 prog.py < input.txt
0
14
24
253
5861
2183837

Zgjidhja 1

T = int(input())
for t in range(T):
    n = int(input())
    f = 1  # faktoriali
    for i in range(1, n+1):
        f *= i
    z = 0  # numri i zerove të faktorialit
    while f % 10 == 0:
        z += 1
        f //= 10
    print(z)

Sqarime

Fillimisht gjejmë faktorialin e numrit të dhënë, pastaj gjejmë sa zero ka në fund.

Kjo është zgjidhje e thjeshtë për tu ndërtuar por jo edhe aq efiçente (e shpejtë). Është e mundur të gjendet numri i zerove pa e gjetur më parë vetë faktorialin.

Zgjidhja 2

for _ in range(int(input())):
    n = int(input())
    z = 0
    p = 5    # fuqite e 5-es
    while p < n:
        z += n // p
        p *= 5
    print(z)

Sqarime

Nqs faktorialin e shprehim si prodhim numrash të thjeshtë, atere është e qartë se numri i zerove në fund të tij është i barabartë me fuqinë e numrit 5, sepse çdo zero në fund të numrit vjen si rezultat i prodhimit 5*2 (dysha në prodhimin faktorial kemi më shumë se pesa, sepse çdo numër çift kontribuon në prodhim të paktën me një dysh).

Zgjidhja e problemit bazohet në faktin që çdo shumëfish i 5-ës kontribon 1 pesë në prodhim, çdo shumëfish i 25-ës kontribon 2 pesa, çdo shumëfish i \(5^3\) kontribon 3 pesa, e kështu me radhë.

Për një sqarim më të detajuar të zgjidhjes shikoni edhe këtë diskutim: https://discuss.codechef.com/questions/58730/fctrl-editorial

Zgjidhja 3

for _ in range(int(input())):
    n = int(input())
    z = 0
    while n > 0:
        n //= 5
        z += n
    print(z)

Sqarime

Ideja është e njëjtë me zgjidhjen e dytë, por algoritmi pak më ndryshe.

Gjejmë sa shumëfisha të 5-ës kemi deri te n-ja, dhe këtë ia shtojmë z-së. Pastaj gjejmë sa shumëfisha të 25-ës dhe ia shtojmë z-së, e kështu me radhë.

Detyra

Në një varg shkronjash të dhënë, përcaktoni nëse njëra prej shkronjave përsëritet po aq sa përsëriten të gjitha shkronjat e tjera sëbashku.

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

Shembull

$ cat input.txt
4
acab
zzqzqq
abc
kklkwwww

$ python3 prog.py < input.txt
YES
YES
NO
YES