Problemi 069

Kërkesa

Regjimi ditor i Çufos është shumë i thjeshtë, në fillim të ditës ai gatuan, pastaj ha, dhe në fund shkon të flejë. Çufoja ka instaluar disa pajisje smart-home, midis të cilave edhe disa kamera, të cilat në mënyrë periodike shënojnë veprimin që është duke bërë Çufoja në atë moment. Kur Çufoja është duke gatuar sistemi shënon një ‘C’ (cooking), kur është duke ngrënë shënon një ‘E’ (eating), dhe kur është duke fjetur shënon një ‘S’ (sleeping). Duke parë shënimet e sistemit për një ditë, gjeni nëse ato mund të jenë të sakta ose jo.

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

Shembull

$ cat input.txt
6
CES
CCCEESS
CS
CCC
SC
ECCC

$ python3 prog.py < input.txt
yes
yes
yes
yes
no
no

Është e qartë që rasti i parë është i saktë.
Në rastin e dytë, largësia midis regjistrimeve mund të ketë qenë më e vogël, kështu që të njëjtin veprim e ka regjistruar disa herë, por prapë shënimet janë të sakta.
Në rastin e tretë, largësia midis regjistrimeve mund të ketë qenë shumë e madhe, kështu që ngrënien nuk e ka kapur fare, por prapë shënimet mund të jenë të rregullta.
Në rastin e katërt intervalet e regjistrimit kanë qenë të tilla që ngrënien e ka kapur disa herë, kurse veprimet e tjera nuk i ka kapur fare, megjithatë shënimet mund të jenë të rregullta.
Në rastin e pestë shënimet nuk mund të jenë të sakta, sepse nuk ka mundësi që të ketë fjetur njëherë dhe pastaj të ketë gatuar.
Në rastin e fundit shënimet nuk mund të jenë të sakta, sepse nuk ka mundësi që të ketë ngrënë njëherë dhe pastaj të ketë gatuar.

Zgjidhja 1

for _ in range(int(input())):
    s = input()
    l = [s[0]]
    for i in range(1, len(s)):
        if s[i] != s[i-1]:
            l.append(s[i])
    if len(l)==3 and l[0]=='C' and l[1]=='E' and l[2]=='S':
        print('yes')
    elif len(l)==2 and ((l[0]=='C' and l[1]=='E') or (l[0]=='C' and l[1]=='S') or (l[0]=='E' and l[1]=='S')):
        print('yes')
    elif len(l) == 1:
        print('yes')
    else:
        print('no')

Sqarime

Në fillim e bëjmë kompakt vargun, duke mbajtur vetëm një kopje të shkronjave që përsëriten, pastaj e kontrollojmë.

Zgjidhja 2

for _ in range(int(input())):
    s = input()
    l = [s[0]]
    for i in range(1, len(s)):
        if s[i] != s[i-1]:
            l.append(s[i])
    s1 = ''.join(l)
    if len(l)==1 or s1=='CE' or s1=='CS' or s1=='ES' or s1=='CES':
        print('yes')
    else:
        print('no')

Sqarime

Kontrolli mund të bëhet më kollaj nëse shkronjat i bashkojmë në një varg.

Zgjidhja 3

for _ in range(int(input())):
    L = list(input())
    for i in range(len(L)):
        if L[i] == 'C':
            L[i] = 1
        elif L[i] == 'E':
            L[i] = 2
        else:
            L[i] = 3

    for i in range(1, len(L)):
        if L[i] < L[i-1]:
            print('no')
            break
    else:
        print('yes')

Sqarime

Kjo është një zgjidhje e ndryshme. Në fillim i zëvendësojmë shkronjat C, E, F me 1, 2, 3 dhe pastaj kontrollojmë që numrat vijnë gjithmonë në rritje.

Zgjidhja 4

from re import match
for _ in range(int(input())):
    print('yes') if match('^C*E*S*$',input()) else print('no')

Sqarime

Në këtë zgjidhje përdorim shprehjet e rregullta. Shprehja ‘C’ do të thotë disa C njëra pas tjetrës (ndoshta asnjë). Po kështu edhe ’E’ dhe ’S*’. Kurse shenja ^ do të thotë që përputhja e shprehjes me vargun duhet të fillojë që në fillim të vargut. Po ashtu, shenja $ do të thotë që përputhja e shprehjes me vargun duhet të vazhdojë deri në fund të vargut.

Detyra

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.

Kemi 2 senatorë nga partia A dhe 2 nga partia B. Nxjerrim AB dhe na ngelen 1A 1B. Nxjerrim BA.
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.
Kemi 1A 1B 2C. Nxjerrim C dhe na ngelen 1B 1B 1C. Nxjerrim C dhe ngelen 1A 1B. Nxjerrim AB.
Kemi 2A 3B 1C. Nxjerrim BA dhe ngelen 1A 2B 1C. Nxjerrim BB dhe mbeten 1A 1C. Nxjerrim AC.