Problemi 081

Kërkesa

Në një kompani janë N punonjës, pagat e të cilëve janë \(W_i\) (për i nga 1 në N). Një ditë pronari vendosi që tua bëjë rrogat të barabarta të gjithëve. Por për të arritur këtë qëllim ai përdor një veprim të tillë: Zgjedh një punonjës, dhe rrit me 1 rrogën e gjithë punonjësve të tjerë (por jo të këtij që ka zgjedhur). Sigurisht që punonjësi i zgjedhur mund të jetë i ndryshëm për secilin veprim. Sa është numri më i vogël i veprimeve të tilla që duhen kryer deri sa të gjithë punonjësit të kenë rroga të barabarta?

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

Shembull

$ cat input.txt
2
3
1 2 3
2
42 42

$ python3 prog.py < input.txt
3
0

Në rastin e parë, fillimisht zgjidhet punonjësi i tretë, dhe pagat bëhen (2, 3, 3). Pastaj mund të zgjidhet punonjësi i dytë, dhe pagat bëhen (3, 3, 4). Pastaj mund të zgjidhet punonjësi i tretë, dhe pagat bëhen (4, 4, 4). Pra duhen 3 veprime për ti barazuar.

Në rastin e dytë janë tashmë të barabarta, kështu që nuk është nevoja për asnjë veprim.

Zgjidhja 1

for _ in range(int(input())):
    n = int(input())
    W = [int(i) for i in input().split()]
    nr = 0
    W.sort(reverse=True)
    while W[0] > W[-1]:
        nr += 1
        for i in range(1, n):
            W[i] += 1
        i = 0
        while W[i] < W[i+1]:
            W[i], W[i+1] = W[i+1], W[i]
            i += 1
    print(nr)

Sqarime

Për të bërë sa më pak veprime, duhet të zgjedhim gjithmonë punonjësin që ka pagën më të lartë (ose një nga ata që kanë pagën më të lartë), dhe të rrisim pagat e të tjerëve me 1.

Për ta lehtësuar këtë proces, listën e pagave e mbajmë të renditur në rendin zbritës. Meqenëse lista është e renditur, më i madhi është gjithmonë i pari në listë, kështu që në çdo hap mjafton të rrisim të tjerët përveç të parit. Pasi kemi bërë një hap, renditjen e listës mund ta rivendosim duke zhvendosur elementin e parë drejt fundit, deri sa të ndodhet në vendin e duhur sipas renditjes.

Duke qenë se lista është e renditur, edhe kontrollin nëse të gjithë elementët e listës janë të barabartë mund ta bëjmë kollaj: mjafton që të krahasojmë elementin e parë me të fundit.

Kjo zgjidhje është llogjikisht e thjeshtë, por për numra të mëdhenj është shumë e ngadaltë dhe nuk e kalon testin (https://www.codechef.com/submit/SALARY).

Zgjidhja 2

for _ in range(int(input())):
    n = int(input())
    W = [int(i) for i in input().split()]
    print(sum(W) - n*min(W))

Sqarime

Mund të vëmë re që veprimi që kryhet është i njëvlershëm me këtë veprim: Zgjedhim një punonjës dhe i zbresim 1 pagës së tij, pastaj u shtojmë 1 të gjithë punonjësve. Meqenëse ne interesohemi që ti bëjmë rrogat të barabarta, pjesën e dytë të këtij veprimi (shtojmë 1 për të gjithë punonjësit) mund të mos ta marrim parasysh.

Atere problemi shndërrohet në këtë formë: Zgjedhim një punonjës dhe i zbresim 1 pagës së tij. Sa herë duhet ta përsërisim këtë veprim deri sa të gjitha rrogat të bëhen të barabarta.

Është e qartë se ne mund të zgjedhim një punonjës çfarëdo dhe ti zbresim 1 deri sa paga e tij të bëhet e barabartë me pagën më të vogël, pastaj të zgjedhim një tjetër, e kështu me radhë, deri sa të gjitha pagat të bëhen të barabarta me pagën më të vogël. Kështu që numri total i veprimeve është \((W_1 - W_{min}) + (W_2 - W_{min}) + ... + (W_n - W_{min})\), që është sum(W) - n*min(W).

Detyra

Në një varg numrash natyrorë \(A_1, A_2, ..., A_n\) gjeni vlerën më të madhe të shprehjes \(A_i mod A_j\) (mbetja e pjesëtimit të \(A_i\) me \(A_j\)) për çdo vlerë të i dhe j.

Referenca: https://www.codechef.com/APRIL19B/problems/MAXREM

Shembull

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

$ python3 prog.py < input.txt
4
5