Problemi 027

Kërkesa

Shënojmë shuma(N) një funksion që gjen në mënyrë efiçente shumën e numrave nga 1 në N. Quajmë shumshuma(D, N) një funksion që veprimin shuma(N) e zbaton D herë: herën e parë te N dhe herët e tjera te rezultati i veprimit të mëparshëm.

Për shembull, nëse D = 2 dhe N = 3, atere shumshuma(2, 3) është e barabartë me shuma(shuma(3)) = shuma(1 + 2 + 3) = shuma(6) = 21

Bëni një program që gjen vlerën e shumshuma(D, N) për vlerat e dhëna të D dhe N.

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

Shembull

$ cat input.txt
2
1 4
2 3

$ python3 prog.py < input.txt
10
21

Në rastin e parë kemi shumshuma(1, 4) = shuma(4) = 1 + 2 + 3 + 4 = 10. Rasti i dytë është siç është sqaruar te kërkesa.

Zgjidhja 1

def shuma(n):
    return n * (n + 1) // 2

def shumshuma(d, n):
    if d == 1:
        return shuma(n)
    else:
        return shumshuma(d - 1, shuma(n))

for _ in range(int(input())):
    d, n = map(int, input().split())
    print(shumshuma(d, n))

Sqarime

Zgjidhja bazohet në faktin që shumshuma(d, n) == shumshuma(d-1, shuma(n)), për d > 1. Kurse kur d == 1, shumën e numrave nga 1 në n mund ta llogarisim me formulë.

Zgjidhja 2

def shuma(n):
    return n * (n + 1) // 2

for _ in range(int(input())):
    d, n = map(int, input().split())
    while d > 0:
        n = shuma(n)
        d -= 1
    print(n)

Detyra

Sa katrorë me madhësi 2x2 mund të futen në një trekëndësh kënddrejtë dybrinjënjëshëm, ku kateti është me gjatësi B, dhe brinjët e katrorëve janë paralel me katetet?

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

Shembull

$ cat input.txt
11
1
2
3
4
5
6
7
8
9
10
11

$ python3 prog.py < input.txt
0
0
0
1
1
3
3
6
6
10
10