Problemi 150

Kërkesa

Në një konkurs jepet një varg S me shkronja të mëdha (anglisht). Shkronjat e kësaj fjale i jepen sipas radhës konkurrentit, i cili po formon një varg të ri. Konkurrenti mund ti vendosë shkronjat që i jepen në fillim ose në fund të vargut që po formon. Ai fiton nqs vargu që formon është i fundit (sipas rendit alfabetik) nga të gjitha vargjet që mund të formohen.

P.sh. nqs vargu i dhënë është S = CAB, mund të formojë këto vargje:

vendos A para C dhe formohet AC, vendos B para AC dhe formohet BAC
vendos A para C dhe formohet AC, vendos B pas AC dhe formohet ACB
vendos A pas C dhe formohet CA, vendos B para CA dhe formohet BCA
vendos A pas C dhe formohet CA, vendos B pas CA dhe formohet CAB

Vargu fitues (i fundit alfabetikisht) nga këta është CAB. Nqs S = JAM, atere vargu fitues do ishte MJA.

Referenca: https://code.google.com/codejam/contest/4304486/dashboard#s=p0&a=0

Shembull

$ cat input.txt
8
CAB
JAM
CODE
ABAAB
CABCBBABC
ABCABCABC
ZXCASDQWE
DGFKGKTYRYEIRMDBACDFSEORLFNDF

$ python3 prog.py < input.txt
Case #1: CAB
Case #2: MJA
Case #3: OCDE
Case #4: BBAAA
Case #5: CCCABBBAB
Case #6: CCCBAABAB
Case #7: ZXCASDQWE
Case #8: YYTKKGDFGREIRMDBACDFSEORLFNDF

Zgjidhja 1

for t in range (int(input())):
    S = input()
    A = set([''])    # set of all possible strings
    for c in S:
        A = set([c + s for s in A] + [s + c for s in A])
    print('Case #{}: {}'.format(t+1, max(A)))

Sqarime

Kjo zgjidhje gjen të gjitha vargjet e mundshme që mund të krijohen dhe pastaj kthen më të madhin prej tyre. Mund të quhet edhe zgjidhje kombinatoriale (përkëmbyese), meqë merr në shqyrtim të gjitha kombinimet e mundshme.

Ndërlikushmëria (kompleksiteti) i kësaj zgjidhjeje është eksponenciale, edhe në kohë, edhe në hapësirën që duhet në kujtesë: \(O(2^N)\) ku N është gjatësia e vargut të dhënë.

P.sh. te rasti i fundit kjo zgjidhje ngec. Zgjidhjet eksponenciale janë shpërthyese. (Kujdes se mos ju hedh kompjuterin në erë! Edhe bomba atomike shpërthen ngaqë grimcat e uranit fillojnë të ndahen në mënyrë eksponenciale.)

Zgjidhja 2

for t in range (int(input())):
    S = input()
    S1 = ''    # the new string
    for c in S:
        S1 = c + S1 if c + S1 > S1 + c else S1 + c
    print('Case #{}: {}'.format(t+1, S1))

Sqarime

Kjo zgjidhje është lineare. Ndërlikushmëria: \(O(N)\).

Për një diskutim të detajuar se pse kjo zgjidhje jep rezultatin e duhur shikoni: https://code.google.com/codejam/contest/4304486/dashboard#s=a&a=0

Zgjidhja 3

for t in range (int(input())):
    S = input()
    S1 = ''    # the new string
    for c in S:
        S1 = min(c + S1, S1 + c)
    print('Case #{}: {}'.format(t+1, S1))