Problemi 018

Kërkesa

Një shkallë që të çon në katin e dytë ka \(n\) hapa, dhe lartësia e secilit hap nga toka është \(h_i\). Ada do të ngjitet në katin e dytë, por ajo mund të ngjitet nga lartësia \(h_i\) në lartësinë \(h_f\) vetëm nëse \(h_f - h_i \leq k\). Për ta ndihmuar Adën duhet të ndërtojmë disa hapa të ndërmjetëm midis hapave ekzistues (ose para hapit të parë).

Bëni një program që gjen numrin më të vogël të hapave ndihmës që duhen ndërtuar, që Ada të mund të ngjitet në katin e dytë.

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

Shembull

$ cat input.txt
1
4 3
2 4 8 16

$ python3 prog.py < input.txt
3

Jepen numrat \(n\) dhe \(k\), dhe pastaj jepet lartësia e secilit prej hapave.

Zgjidhja 1

T = int(input())
for t in range(T):
    n, k = list(map(int, input().split()))
    h = list(map(int, input().split()))
    hapat = 0
    for i in range(n):
        d = h[0] if i==0 else h[i] - h[i-1]
        while d > k:
            d -= k
            hapat += 1
    print(hapat)

Sqarime

Gjejmë diferencën midis dy hapave, dhe nqs është më e madhe se k, ndërtojmë një hap ndihmës me lartësi k (dhe kështu diferenca zvogëlohet me k).

Gjatë gjetjes së diferencës hapin e parë e kemi trajtuar në mënyrë të veçantë sepse nuk kemi hap tjetër para tij.

Zgjidhja 2

T = int(input())
for t in range(T):
    n, k = list(map(int, input().split()))
    h = list(map(int, input().split()))
    hapat = 0
    h = [0] + h
    for i in range(1, n+1):
        d = h[i] - h[i-1]
        while d > k:
            d -= k
            hapat += 1
    print(hapat)

Sqarime

Kemi shtuar një 0 në krye të listës së hapave, dhe i-në e marrim nga 1 deri në n, në mënyrë që të shmangim if-n për gjetjen e diferencës.

Zgjidhja 3

for _ in range(int(input())):
    n, k = list(map(int, input().split()))
    h = [0] + list(map(int, input().split()))
    hapat = 0
    for i in range(1, n+1):
        hapat += (h[i] - h[i-1]) // k
    print(hapat)

Sqarime

I rrisim hapat me aq herë sa hyn k-ja te diferenca midis hapave ekzistues.

Detyra

Një sistem monetar ka prerje (ose monedha) me vlerë: 1, 2, 5, 10, 50, 100. Bëni një program që gjen numrin më të vogël të monedhave që e kanë shumën sa një vlerë e dhënë N.

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

Shembull

$ cat input.txt
3
1200
500
242

$ python3 prog.py < input.txt
12
5
7