Problemi 148

Kërkesa

Një shkop kërcimi pogo ka një sustë në fund dhe me të mund të hidhesh nga një vend në një vend tjetër, duke qëndruar mbi të. Por shkopi që ju kanë bërë dhuratë është i veçantë sepse herën e parë kërcen me një largësi 1 njësi, herën e dytë 2 njësi, herën e tretë 3 njësi, e kështu me radhë. Ju mund të kërceni në një nga këto drejtime: veri, jug, lindje, perëndim.

Nqs ndodheni në pikën (0, 0), si mund të shkoni në pikën (X, Y)? Si mund të shkoni me sa më pak kërcime?

Boshti X është sipas drejtimit S-N (jug-veri) dhe boshti Y është sipas drejtimit W-E (perëndim-lindje). Pika (X, Y) është e ndryshme nga (0, 0).

Referenca: https://code.google.com/codejam/contest/2437488/dashboard#s=p1&a=1

Shembull

$ cat input.txt
2
3 4
-3 4

$ python3 prog.py < input.txt
Case #1: ENWSEN
Case #2: ENSWN

Vini re që në rastin e parë ka edhe një rrugë tjetër që është më e shkurtër: WNSEN

Zgjidhja 1

Kjo është një nga zgjidhjet më të thjeshta.

for t in range(int(input())):
    x, y = [int(i) for i in input().split()]
    ans = ''
    while x > 0:
        ans += 'WE'
        x -= 1
    while x < 0:
        ans += 'EW'
        x += 1
    while y > 0:
        ans += 'SN'
        y -= 1
    while y < 0:
        ans += 'NS'
        y += 1
    print('Case #{}: {}'.format(t+1, ans))

Zgjidhja 2

Kjo zgjidhje gjen rrugën më të shkurtër.

for t in range(int(input())):
    x, y = [int(i) for i in input().split()]
    n = 0
    s = 0
    while s < abs(x) + abs(y) or (s + x + y) % 2 == 1:
        n += 1
        s += n
    ans = ''
    while n > 0:
        if abs(x) > abs(y):
            if x > 0: 
                ans += 'E'
                x -= n
            else:
                ans += 'W'
                x += n
        else:
            if y > 0:
                ans += 'N'
                y -= n
            else:
                ans += 'S'
                y += n
        n -= 1
    print('Case #{}: {}'.format(t+1, ''.join(reversed(ans))))