Problemi 026

Kërkesa

Për një varg shkronjash \(S\) shënojmë me \(C\) bashkësinë e shkronjave që shfaqen në të të paktën 1 herë. Një përkëmbim (radhitje) të elementeve të bashkësisë \(C\) e shënojmë \((c_1, c_2, c_3...)\). Le të jetë \(f(c)\) numri i herëve që përsëritet shkronja \(c\) në vargun \(S\).

Nëse ndonjë përkëmbim i elementeve të bashkësisë \(C\) kënaq kushtin \(f(c_i) = f(c_{i-1}) + f(c_{i-2})\) për çdo \(i \geq 3\) vargu \(S\) quhet varg dinamik.

Bëni një program që gjen nëse një varg i dhënë është dinamik.

Vini re që nëse numri i shkronjave të veçanta që shfaqen në varg është më pak se 3, p.sh. nëse \(|C| < 3\), atere vargu është gjithmonë dinamik.

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

Shembull

$ cat input.txt
3
aaaabccc
aabbcc
ppppmmnnoooopp

$ python3 prog.py < input.txt
Dynamic
Not
Dynamic

Zgjidhja 1

def is_dynamic(S):
    # count the frequency of each char of the string
    freq = {}
    for c in S:
        freq[c] = freq.get(c, 0) + 1

    if len(freq) < 3:
        return 'Dynamic'

    f = list(freq.values())
    f.sort()
    for i in range(2, len(f)):
        if f[i] != f[i-1] + f[i-2]:
            return 'Not'

    return 'Dynamic'

for _ in range(int(input())):
    print(is_dynamic(input()))

Zgjidhja 2

def is_dynamic(S):
    # count the frequency of each char of the string
    f = [S.count(c) for c in set(S)]

    if len(f) < 3:
        return 'Dynamic'

    f.sort()
    for i in range(2, len(f)):
        if f[i] != f[i-1] + f[i-2]:
            return 'Not'

    return 'Dynamic'

for _ in range(int(input())):
    print(is_dynamic(input()))

Detyra

Një drejtkëndësh me përmasa A dhe B duam ta ndajmë në copa katrore (jo detyrimisht të barabarta). Sa është numri më i vogël i katrorëve në të cilët mund të ndahet ky drejtkëndësh?

Shembull

$ cat input.txt
2
10 15
4 7

$ python3 prog.py < input.txt
3
5