Problemi 156

Kërkesa

Një varg quhet DPS (dummy palindromic string) nëse mund të shndërrohet në palindromë duke kryer këto dy veprime (vetëm një herë):

• Ndryshoju vendet shkronjave në mënyrë të çfarëdoshme.
• Zgjidh një nga shkronjat e vargut dhe ndryshoje në një tjetër (që mund të jetë edhe e ndryshme nga shkronjat që janë në vargun fillestar.

Për një varg të dhënë S gjeni nëse është DPS.

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

Shembull

$ cat input.txt
4
code
xyxyxy
sad
baab

$ python3 prog.py < input.txt
!DPS
DPS
DPS
!DPS

Shembulli 1: Është e pamundur që të krijojmë një palindromë duke ndryshuar vendet e shkronjave në vargun ‘code’, dhe duke ndryshuar njërën prej tyre.

Shembulli 2: Mund ti ndryshojmë vendet e shkronjave kështu: ‘xyxyyx’, dhe pastaj ta zëvendësojmë shkronjën e tretë me ‘y’. Marrim vargun ‘xyyyyx’, i cili është palindromë.

Shembulli 3: Mund ta lëmë radhën e shkronjave ashtu siç është, dhe pastaj ta zëvendësojmë shkronjën e parë me ‘d’. Marrim ‘dad’, e cila është një palindromë.

Shembulli 4: Edhe pse vargu i dhënë është palindromë, është e pamundur që të krijojmë një palindromë tjetër duke ndryshuar radhën e shkronjave dhe duke ndryshuar njërën prej shkronjave.

Zgjidhja

for _ in range(int(input())):
    S = input()
    F = {}
    for c in S:
        F[c] = F.get(c, 0) + 1
    nr_odd = 0
    for c in F.keys():
        if F[c] % 2 == 1:
            nr_odd += 1
    print('DPS') if nr_odd in [1, 2, 3] else print('!DPS')

Sqarime

Përdorim faktin që në një palindromë të gjitha shkronjat përsëriten një numër çift herësh, me përjashtim ndoshta të njërës prej tyre, e cila mund të ndodhet një numër tek herësh.