Problemi 140

Kërkesa

Ada ka N lapsa me ngjyra, disa me majën poshtë dhe disa me majën lart. Ada mendon se do ishte më mirë sikur të gjithë lapsat të ishin në të njëjtin drejtim. Ajo mund të kthejë njëherësh një segment të tërë me lapsa të njëpasnjëshëm. Pas një kthimi, ata që ishin me majë poshtë do kthehen me majën lart, dhe anasjelltas. Sa është numri më i vogël i kthimeve për të bërë të gjithë lapsat me të njëjtin drejtim?

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

Shembull

$ cat input.txt
1
UUDDDUUU

$ python3 prog.py < input.txt
1

Me U shënohet një laps me majën lart dhe me D një laps që e ka majën poshtë. Në rastin e dhënë, mjafton vetëm një kthim për ti vendosur me majën lart të gjithë lapsat që janë me majën poshtë.

Zgjidhja

for _ in range(int(input())):
    s = input()
    u = 0    # nr i segmenteve me majën lart
    d = 0    # nr i segmenteve me majën poshtë
    if s[0] == 'U':
        u += 1
    else:
        d += 1
    for i in range(1, len(s)):
        if s[i] != s[i-1]:
            if s[i] == 'U':
                u += 1
            else:
                d += 1
    print(min(u, d))