Problemi 077

Kërkesa

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

Zgjidhja 1

for _ in range(int(input())):
    s = input()
    i = 0
    j = len(s) - 1
    while i < j:
        if s[i] == '1' and s[j] == '1':
            break
        if s[i] == '0':
            i += 1
        if s[j] == '0':
            j -= 1
    if i > j:
        print('NO')
    else:
        while i < j:
            if s[i] == '0':
                break
            i += 1
        if i == j and s[i] == '1':
            print('YES')
        else:
            print('NO')

Sqarime

Marrim dy indekse i dhe j, njëri që niset nga fillimi dhe tjetri nga fundi, dhe i lëvizim deri sa të gjejmë fillimin dhe fundin e njëshave. Pastaj kontrollojmë nëse midis këtyre ka ndonjë zero.

Zgjidhja 2

for _ in range(int(input())):
    s = input()
    nr1 = s.count('1')
    if nr1 == 0:
        print('NO')
    else:
        i = 0
        while s[i] != '1':
            i += 1
        j = len(s) - 1
        while s[j] != '1':
            j -= 1
        if j - i + 1 == nr1:
            print('YES')
        else:
            print('NO')

Sqarime

Fillimisht gjejmë numrin e njëshave. Pastaj indeksin e njëshit të parë nga fillimi, dhe të njëshit të parë nga fundi. Pastaj kontrollojmë nëse largësia midis këtyre dy indekseve është e barabartë me numrin e njëshave.

Detyra

Në një kompani janë N punonjës, pagat e të cilëve janë \(W_i\) (për i nga 1 në N). Një ditë pronari vendosi që tua bëjë rrogat të barabarta të gjithëve. Por për të arritur këtë qëllim ai përdor një veprim të tillë: Zgjedh një punonjës, dhe rrit me 1 rrogën e gjithë punonjësve të tjerë (por jo të këtij që ka zgjedhur). Sigurisht që punonjësi i zgjedhur mund të jetë i ndryshëm për secilin veprim. Sa është numri më i vogël i veprimeve të tilla që duhen kryer deri sa të gjithë punonjësit të kenë rroga të barabarta?

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

Shembull

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

$ python3 prog.py < input.txt
3
0

Në rastin e parë, fillimisht zgjidhet punonjësi i tretë, dhe pagat bëhen (2, 3, 3). Pastaj mund të zgjidhet punonjësi i dytë, dhe pagat bëhen (3, 3, 4). Pastaj mund të zgjidhet punonjësi i tretë, dhe pagat bëhen (4, 4, 4). Pra duhen 3 veprime për ti barazuar.

Në rastin e dytë janë tashmë të barabarta, kështu që nuk është nevoja për asnjë veprim.