Problemi 153

Kërkesa

Në një stivë me libra disa prej librave janë përmbys. Ne mund të kapim disa prej librave që janë në krye të stivës (ose të gjithë stivën) dhe ta kthejmë në krahun tjetër.

Le ta shënojmë një libër që është përmbys me “-” dhe një libër që është në rregull me “+”. Nqs stiva e librave, duke filluar nga kreu, është e tillë: –+-, atere një mënyrë për ti kthyer të gjithë librat në rregull mund të jetë kjo:

• Kapim 3 librat e sipërm dhe i kthejmë përmbys: -++-
• Kapim librin e parë dhe e kthejmë përmbys: +++-
• Kapim 3 librat e sipërm dhe i kthejmë përmbys: —-
• Kapim gjithë stivën dhe e kthejmë përmbys: ++++

Gjeni numrin më të vogël të lëvizjeve që duhen për të rregulluar një stivë të dhënë.

Referenca: https://code.google.com/codejam/contest/6254486/dashboard#s=a&a=0

Shembull

$ cat input.txt
5
-
-+
+-
+++
--+-

$ python3 prog.py < input.txt
Case #1: 1
Case #2: 1
Case #3: 2
Case #4: 0
Case #5: 3

Zgjidhja

for t in range(int(input())):
    books = input()
    ans = books.count('-+') + books.count('+-')
    if books.endswith('-'):
        ans += 1
    print('Case #{}: {}'.format(t+1, ans))

Sqarime

Strategjia më e thjeshtë dhe më e shkurtër është që gjithmonë të kapim dhe të kthejmë grupin me libra në krye të stivës që kanë të njëjtin drejtim. Kështu që mjafton të numërojmë se sa grupe të tilla kemi. Në fund, nqs të gjithë librat e stivës janë me krye poshtë, duhet të kthejmë të gjithë stivën.

Për një diskutim më të detajuar shiko: https://code.google.com/codejam/contest/6254486/dashboard#s=a&a=1