Problemi 038

Kërkesa

Në një listë me numra natyrorë, gjeni numrin e nënlistave për të cilat shuma dhe prodhimi i elementëve është i barabartë.

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

Shembull

$ cat input.txt
3
3
1 3 2
4
4 1 2 1
6
1 2 2 2 2 1

$ python3 prog.py < input.txt
4
5
9

Zgjidhja

for _ in range(int(input())):
    n = int(input())
    L = list(map(int, input().split()))
    nr = 0
    for i in range(n):
        s = 0
        p = 1
        for j in range(i, n):
            s += L[j]
            p *= L[j]
            if s == p:
                nr += 1
    print(nr)

Sqarime

Për të gjetur të gjitha listat përdorim dy treguesa (indekse) i dhe j, ku i-ja lëviz nga elementi i parë i listës deri tek i fundit, kurse j-ja lëviz nga i-ja deri në fund të listës. Për secilën nënlistë (ose segment) që fillon në i dhe mbaron në j, llogarisim shumën dhe prodhimin e numrave përbërës, por këtë e bëjmë në mënyrë dinamike (duke shtuar një element të ri në listë dhe duke përtërirë shumën dhe prodhimin e listës së mëparshme). Sa herë që shuma dhe prodhimi bëhen të barabartë, shtojmë 1 te përgjigja.

Detyra

Kërkesa

Roboti Bani ka humbur rrugën. Ai ndodhet në kordinatat \((x_1, y_1)\) në një plan 2 dimensional, kurse shtëpia e tij ndodhet në kordinatat \((x_2, y_2)\). Bëni një program që ta ndihmojë duke i treguar drejtimin në të cilin duhet të lëvizë për të arritur në shtëpi. Nëse i tregojmë një drejtim, roboti do të vazhdojë të lëvizë në atë drejtim deri sa të arrijë në shtëpi. Janë katër drejtime që mund t’ia japim si komandë: majtas, djathtas, lartë, poshtë. Nëse asnjë nga këto drejtime nuk e çon robotin në shtëpi, programi duhet të nxjerrë: më vjen keq.

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

Shembull

$ cat input.txt
5
0 0 1 0
0 0 0 1
0 0 1 1
2 0 0 0
0 2 0 0

$ python3 prog.py < input.txt
right
up
sad
left
down