Problemi 075

Kërkesa

Le ta quajmë tidy (të rregullt) një numër që i ka shifrat të renditura në rendin jo-zbritës. P.sh. numrat 8, 123, 555, 224488 janë tidy, kurse numrat 20, 321, 495, 999990 nuk janë.

Nqs numërojmë numrat nga 1 në N, cili ka qenë numri i fundit tidy që kemi numëruar? Ose me fjalë të tjera, gjeni numrin më të madh tidy që është më i vogël (ose i barabartë) se një numër i dhënë N.

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

Shembull

$ cat input.txt
4
132
1000
7
111111111111111110

$ python3 prog.py < input.txt
Case #1: 129
Case #2: 999
Case #3: 7
Case #4: 99999999999999999

Zgjidhja 1

def tidy(n):
    d = n % 10
    while n > 0:
        if n % 10 > d:
            return False
        d = n % 10
        n //= 10
    return True

for t in range(int(input())):
    N = int(input())
    while N > 0 and not tidy(N):
        N -= 1
    print('Case #{}: {}'.format(t+1, N))

Sqarime

Kemi një funksion që kontrollon nëse një numër i dhënë është tidy, pastaj vazhdojmë ta zvogëlojmë numrin deri sa të gjejmë një që është tidy.

Kjo zgjidhje është llogjikisht e thjeshtë, por për numra të mëdhenj (p.sh. për rastin e fundit) vonohet shumë. Duhet gjetur një zgjidhje më e shpejtë.

Zgjidhja 2

def get_tidy(n):
    '''
    Get the smallest tidy number that is >= n
    '''
    D = [int(d) for d in list(str(n))]
    i = 1
    while i < len(D) and D[i] >= D[i-1]:
        i += 1
    while i < len(D):
        D[i] = D[i-1]
        i += 1
    return(int(''.join([str(d) for d in D])))

for t in range(int(input())):
    N = input()
    n = len(N)
    if n == 1:
        print('Case #{}: {}'.format(t+1, N))
        continue
    N = int(N)
    last_t = int('9'*(n-1))
    tidy = last_t
    while tidy < N:
        last_t = tidy
        tidy = get_tidy(tidy + 1)
    if tidy > N:
        tidy = last_t
    print('Case #{}: {}'.format(t+1, tidy))

Sqarime

Kjo zgjidhje fillon nga një numër që ne e dimë që është tidy dhe më i vogël se numri i dhënë, dhe gjen vazhdimisht numrin pasardhës tidy, deri sa ky numër të bëhet më i madh se N. Atere numri i fundit tidy që kemi parë është zgjidhja e kërkuar.

Kjo zgjidhje në përgjithësi është më e shpejtë se zgjidhja e parë, sepse nuk i kontrollon numrat me radhë por vetëm ata që janë tidy, dhe numrat tidy nuk janë shumë të shpeshtë. Gjithsesi edhe kjo zgjidhje është e ngadaltë për numra shumë të mëdhenj (rasti i fundit).

Zgjidhja 3

for t in range(int(input())):
    D = [int(d) for d in list(input())]
    i = 1
    while i < len(D) and D[i] >= D[i-1]:
        i += 1
    if i == len(D):
        print('Case #', t+1, ': ', *D, sep='')
        continue
    i -= 1
    while i > 0 and D[i-1] == D[i]:
        i -= 1
    D[i] = D[i] - 1

    i += 1
    while i < len(D):
        D[i] = 9
        i += 1

    if D[0] == 0:
        D[0] = ''
    print('Case #', t+1, ': ', *D, sep='')

Sqarime

Kjo zgjidhje është jashtëzakonisht e shpejtë edhe për numra shumë të mëdhenj. Numrin e kërkuar e përftojmë duke ndryshuar shifrat e numrit të dhënë në mënyrën e duhur.

Detyra

Trajneri i futbollit të një shkolle duhet të zgjedhë P nxënës për të përfaqësuar shkollën në kampionat. Shkolla ka N nxënës dhe aftësitë e secilit në futboll shënohen me një numër natyror \(S_i\).

Trajneri mendon se skuadra duhet të jetë e niveluar, dmth të ketë P nxënës me të njëjtin nivel aftësish, sepse kështu do të luajnë të gjithë si skuadër. Në fillim mund të mos jetë e mundur që të gjenden P nxënës me aftësi të barabarta, kështu që trajnerit do ti duhet ti stërvitë individualisht disa nxënës, për të rritur aftësitë e tyre. Me një orë stërvitje aftësia e një nxënësi mund të ngrihet me 1 pikë.

Sa është minimumi i orëve të stërvitjes që duhen për të krijuar një skuadër të niveluar.

Referenca: https://codingcompetitions.withgoogle.com/kickstart/round/0000000000050e01/00000000000698d6

Shembull

$ cat input.txt
3
4 3
3 1 9 100
6 2
5 5 1 2 3 4
5 5
7 7 1 7 7

$ python3 prog.py < input.txt
Case #1: 14
Case #2: 0
Case #3: 6

Jepen N dhe P, dhe më pas aftësitë e çdo nxënësi.

Në rastin e parë mund të trajnohet për 6 orë nxënësi i parë dhe për 8 orë nxënësi i dytë, dhe atere tre nxënësit e parë do kenë të njëjtin nivel aftësish.

Në rastin e dytë, dy nxënësit e parë kanë të njëjtin nivel aftësish, kështu që nuk është nevoja për trajnime shtesë.

Në rastin e tretë, nxënësi i tretë duhet trajnuar për 6 orë, dhe kështu të 5 nxënësit do kenë të njëjtin nivel.