Problemi 047

Kërkesa

Një radhë e vlefshme kllapash është një varg jo-bosh, ku çdo element i vargut është ose ‘(’ ose ‘)’, dhe i cili plotëson kushtin që duke fshirë në mënyrë të përsëritur çifte kllapash të njëpasnjëshme ‘()’ është e mundur të bëhet varg bosh.

P.sh. (()) dhe ()((()())) janë radhë të vlefshme kllapash, kurse )()( dhe (() nuk janë.

Mikeli ka një radhë të vlefshme kllapash. Ai është i kënaqur me të, përveç faktit që është shumë e gjatë. Kështu që Mikeli ka vendosur ta zëvendësojë me një varg më të shkurtër. Por jo çdo radhë e vlefshme kllapash është e kënaqshme për të. Për të kuptuar kërkesat e tij, po përkufizojmë një funksion F(S) të tillë:

FUNCTION F( S - a valid parentheses sequence )
    BEGIN
        count = 0
        max_count = 0
        FOR index FROM 1 TO LENGTH(S)
        BEGIN
            if S[index] == '(' then count = count + 1
            if S[index] == ')' then count = count - 1
            max_count = max( max_count, count )
        END
        RETURN max_count
    END

Me fjalë të tjera, F(S) është thellësia maksimale e kllapave në një radhë të vlefshme S.

Le të shënojmë me A radhën e kllapave që ka Mikeli dhe B një radhë kandidate për ta zëvendësuar. Mikeli është i gatshëm ta zëvendësojë radhën A me B nëse F(B) është e barabartë me F(A). Gjithashtu do të donte të zgjidhte një B të tillë që ka gjatësi sa më të shkurtër. Nëse ka disa radhë B që i plotësojnë këto kushte do të preferonte atë që është alfabetikisht më e vogël, duke konsideruar ‘(’ më të vogël se ‘)’.

Bëni një program që zgjidh këtë problem për Mikelin.

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

Shembull

$ cat input.txt
1
()((()()))

$ python3 prog.py < input.txt
((()))

Zgjidhja

def F(S):
    cnt = 0
    max_cnt = 0
    for c in S:
        if c == '(':
            cnt += 1
        if c == ')':
            cnt -= 1
        if cnt > max_cnt:
            max_cnt = cnt
    return max_cnt

for _ in range(int(input())):
    n = F(input())
    print(n*'(' + n*')')

Sqarime

Mjafton të gjejmë thellësinë maksimale të kllapave duke përdorur funksionin e dhënë, dhe mund të ndërtojmë një radhë kllapash me të njëjtën thellësi dhe që ka gjatësinë më të vogël të mundshme.

Detyra

Jepen disa shkopinj me gjatësi të përcaktuara. Gjeni sipërfaqen e drejtkëndëshit më të madh që mund të formohet me këta shkopinj, ose printoni -1 nëse asnjë drejtkëndësh nuk mund të formohet.

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

Shembull

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

$ python3 prog.py < input.txt
2
-1

Në rastin e parë mund të formohet një drejtkëndësh me brinjë 1 dhe 2. Në rastin e dytë asnjë drejtkëndësh nuk mund të formohet.