Problemi 017

Kërkesa

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

Zgjidhja 1

for _ in range(int(input())):
    char_list = list(input())

    # find the maximum frequence
    char_list.sort()
    max_freq = 0
    freq = 0
    prev_char = None
    for ch in char_list:
        if ch == prev_char:
            freq += 1
        else:
            if freq > max_freq:
                max_freq = freq
            prev_char = ch
            freq = 1
    if freq > max_freq:
        max_freq = freq

    print('YES' if 2*max_freq==len(char_list) else 'NO')

Sqarime

Fillimisht gjejmë numrin e përsëritjeve të shkronjës që ka numrin më të madh të përsëritjeve, dhe pastaj kontrollojmë nëse ky numër është sa gjysma e numrit të të gjitha shkronjave.

Për të gjetur numrin më të madh të përsëritjeve, fillimisht krijojmë një listë që ka të gjitha shkronjat, dhe pastaj e rendisim në mënyrë që shkronjat e njëjta të jenë në radhë njëra pas tjetrës, dhe kështu të mund ti numërojmë kollaj. Pastaj fillojmë të numërojmë secilën shkronjë dhe ruajmë atë numër përsëritjesh që ka vlerën më të madhe.

Zgjidhja 2

for _ in range(int(input())):
    chars = input()
    frequences = {}    # dictionary of char frequences
    for ch in chars:
        frequences[ch] = frequences.get(ch, 0) + 1:
    print('YES' if 2*max(frequences.values())==len(chars) else 'NO')

Sqarime

Krijojmë një fjalor (dictionary) që për çdo shkronjë të vargut ruan përsëritjet e kësaj shkronje. Pastaj është kollaj të marrim një listë të të gjitha vlerave të këtij fjalori dhe të gjejmë vlerën më të madhe prej tyre.

Zgjidhja 3

for _ in range(int(input())):
    chars = input()
    max_freq = max([chars.count(c) for c in set(chars)])
    print('YES' if 2*max_freq==len(chars) else 'NO')

Sqarime

Funksioni set(chars) kthen një bashkësi të shkronjave të veçanta (pa përsëritje) që ndodhen në vargun chars. Për çdo shkronjë c të kësaj bashkësie, chars.count(c) numëron përsëritjet e kësaj shkronje në vargun chars. Kurse kllapat katrore [ . . . ] bëjnë që gjithë këto vlera të krijojnë një listë të përsëritjeve të shkronjave të veçanta. Funksioni max() gjen vlerën më të madhe të këtyre përsëritjeve.

Detyra

Kemi një varg me numra ku të gjithë numrat përsëriten një numër çift herësh, me përjashtim të njërit i cili përsëritet një numër tek herësh. Të gjendet ky numër.

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

Shembull

$ cat input.txt
2
3
1
2
1
5
1
1
2
2
3

$ python3 prog.py < input.txt
2
3

Janë 2 raste testimi, i pari ka 3 numra (njëri nën tjetrin), dhe i dyti ka 5 numra.