Problemi 072

Kërkesa

Në dhomën e senatit ka rënë një zjarr i vogël dhe duhet të evakuohet! Aty ndodhen disa senatorë të cilët i përkasin njërës prej N partive politike, të cilat emërtohen me N shkronjat e para (të mëdha) të alfabetit anglisht.

Dera e emergjencës është e gjerë sa për dy persona, kështu që në çdo hap ju mund të zgjidhni për të nxjerrë ose një senator ose dy.

Rregullat e senatit lejojnë mundësinë që senatorët që janë në dhomë mund të votojnë çdo ligj me shumicë votash, edhe në rast emergjence apo evakuimi! Kështu që senatorët duhen nxjerrë në mënyrë të tillë që në asnjë moment ndonjëra nga partitë politike të ketë shumicën absolute në senat. Dmth gjatë boshatisjes, në asnjë moment nuk duhet lejuar që më shumë se gjysma e senatorëve brenda në senat të jenë të një partie.

A mund të ndërtoni një plan evakuimi?

Referenca: https://codingcompetitions.withgoogle.com/codejam/round/0000000000000130/00000000000004c0

Shembull

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

$ python3 prog.py < input.txt
Case #1: AB BA
Case #2: AA BC C BA
Case #3: C C AB
Case #4: BA BB CA

Shembujt tregojnë njërën nga mënyrat e mundshme, por mund të ketë edhe mënyra të tjera.

1. Kemi 2 senatorë nga partia A dhe 2 nga partia B. Nxjerrim AB dhe na ngelen 1A 1B. Nxjerrim BA.
2. Kemi 3A 2B dhe 2C. Nqs AA na ngelen 1A 2B 2C. Kur nxjerrim BC na ngelen 1A 1B 1C. Pasi nxjerrim C na ngelen 1A 1B. Nxjerrim BA.
3. Kemi 1A 1B 2C. Nxjerrim C dhe na ngelen 1B 1B 1C. Nxjerrim C dhe ngelen 1A 1B. Nxjerrim AB.
4. Kemi 2A 3B 1C. Nxjerrim BA dhe ngelen 1A 2B 1C. Nxjerrim BB dhe mbeten 1A 1C. Nxjerrim AC.

Zgjidhja

for t in range(int(input())):
    n = int(input())
    S = [int(i) for i in input().split()]
    X = []    # keep the steps of the solution
    if n == 2:
        for _ in range(S[0]):
            X.append('AB')
    else:
        P = []    # names of each party
        for i in range(n):
            P.append(chr(ord('A') + i))
        # sort in decreasing order
        for i in range(n-1):
            for j in range(i+1, n):
                if S[j] > S[i]:
                    S[i], S[j] = S[j], S[i]
                    P[i], P[j] = P[j], P[i]
        while len(S) > 2:
            X.append(P[0])
            S[0] -= 1
            if S[0] == 0:
                del(S[0])
                del(P[0])
            else:
                # keep it sorted
                for i in range(1, len(S)):
                    if S[i] <= S[i-1]:
                        break
                    else:
                        S[i], S[i-1] = S[i-1], S[i]
                        P[i], P[i-1] = P[i-1], P[i]
        X.append(P[0] + P[1])
                    
    print('Case #{}:'.format(t+1), *X)

Sqarime

Strategjia e përdorur është që të mbajmë një listë të partive të renditur në rendin zbritës sipas numrit të senatorëve të secilës parti, dhe të nxjerrim një senator nga partia që ka numrin më të madh. Kjo garanton që asnjë parti të mos ketë shumicën absolute, me përjashtim të rastit kur kemi vetëm dy parti që në fillim, me një numër të barabartë senatorësh. Këtë e trajtojmë si rast të veçantë, duke nxjerrë njëherësh një senator nga njëra parti dhe një nga tjetra.

Detyra

Në një varg që përbëhet nga shifrat 0 dhe 1 kontrolloni nëse të gjitha shifrat 1 formojnë një segment të vetëm dhe jo-bosh.

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

Shembull

$ cat input.txt
6
001111110
00110011
000
1111
101010101
101111111111

$ python3 prog.py < input.txt
YES
NO
NO
YES
NO
NO