Problemi 055

Kërkesa

Është një ditë feste dhe Cufi duhet të raportojë rreth parakalimeve që po bëhen në bulevard. Grupe të ndryshme njerëzish parakalojnë në formë autokolone, njëra pas tjetrës, ku dy autokolona mund të kenë edhe njëfarë distance nga njëra-tjetra. Sa herë që shikon fillimin e një autokolone Cufi shënon në një fletore një H, gjatë kohës që autokolona ecën ai vazhdon të shënojë pika (.), dhe kur shikon fundin e autokolonës shënon një T. Gjithashtu, për të shënuar distancat midis autokolonave ai përdor pika.

Meqenëse autokolonat kalojnë me radhë njëra pas tjetrës, një raport i saktë do ishte diçka e tillë: “..H..T…HTH….T.”, ose “…”, ose “HT”. Kurse “T…H..H.T”, “H..T..H” dhe “H..H..T..T” do ishin të pasakta.

Formalisht, një autokolonë paraqitet nga një H, që pasohet nga disa pika (ndoshta asnjë), dhe në fund ka një T. Një raport i saktë është ai që fillon me disa pika (ndoshta asnjë), vazhdon me disa (ndoshta zero) autokolona midis të cilave mund të ketë edhe pika, dhe mbaron me disa pika (ndoshta asnjë).

Cufi ka ndenjur vonë mbrëmë duke festuar dhe është pak përgjumësh, kështu që raporti i tij mund të jetë i pasaktë. Bëni një program që verifikon nëse raporti është i saktë ose jo.

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

Shembull

$ cat input.txt
6
18
..H..T...HTH....T.
3
...
10
H..H..T..T
2
HT
11
.T...H..H.T
7
H..T..H

$ python3 prog.py < input.txt
Valid
Valid
Invalid
Valid
Invalid
Invalid

“H..H..T..T” nuk është e saktë sepse kolona e dytë fillon para se të mbarojë e para.

“.T…H..H.T” nuk është i saktë sepse ka një fund kolone T pa pasur ndonjë fillim H.

“H..T..H” nuk është i saktë sepse ka një fillim kolone H që nuk ka fund T.

Zgjidhja 1

for _ in range(int(input())):
    n = int(input())
    s = input()
    i = 0
    while True:
        while i < n and s[i] == '.':
            i += 1
        if i == n:
            print('Valid')
            break
        if s[i] == 'H':
            i += 1
        else:
            print('Invalid')
            break
        while i < n and s[i] == '.':
            i += 1
        if i == n:
            print('Invalid')
            break
        if s[i] == 'T':
            i += 1
        else:
            print('Invalid')
            break

Sqarime

Kontrollojmë plotësimin e kushteve për të qenë një raport i rregullt:

• të ketë një numër të çfarëdoshëm pikash në fillim, në mes ose në fund
• shkronja H të jetë e para dhe pas saj të vijë një shkronjë T

Zgjidhja 2

def check(n, s):
    i = 0
    while True:
        while i < n and s[i] == '.':
            i += 1
        if i == n:
            return True
        if s[i] == 'H':
            i += 1
        else:
            return False
        while i < n and s[i] == '.':
            i += 1
        if i == n:
            return False
        elif s[i] == 'T':
            i += 1
        else:
            return False

for _ in range(int(input())):
    n = int(input())
    s = input()
    print('Valid') if check(n, s) else print('Invalid')

Sqarime

E njëjtë me zgjidhjen e parë, por e strukturuar me një funksion që kthen True ose False.

Zgjidhja 3

import re
for _ in range(int(input())):
    input()
    print('Valid') if re.search("^\.*(H\.*T\.*)*$", input()) else print('Invalid')

Sqarime

Zgjidhje që përdor shprehjet e rregullta (https://docs.python.org/3/howto/regex.html)

Detyra

Mësuesi ka ngritur disa nxënës në dërrasë dhe u ka dhënë nga një ushtrim për të zgjidhur (klasa ka një dërrasë të gjatë kështu që mësuesi mund të ngrejë në dërrasë shumë nxënës njëkohësisht). Sapo mësuesi doli një moment nga klasa, disa prej nxënësve u kthyen dhe filluan të komunikojnë me shokun që kishin në krah, kurse të tjerët vazhduan punën. Këtë situatë mund ta paraqesim me një varg të tillë: *><><><*, ku një * tregon një nxënës që vazhdon punën, një > tregon një nxënës që po flet me shokun në të djathtë, dhe një < tregon një nxënës që po flet me shokun në të majtë. Sapo dëgjojnë mësuesin të hyjë përsëri, nxënësit që po flisnin kthehen nga frika në krahun e kundërt. Kur mësuesi shikon dy nxënës përball njëri-tjetrit ai mendon se ata po flisnin, kështu që i ndëshkon të dy. Gjeni sa dyshe nxënësish ndëshkohen prej mësuesit.

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

Shembull

$ cat input.txt
4
><
*><*
><><
*><><><*

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