Problemi 005

Kërkesa

Jepet një varg me numra natyrorë: \(a_1, a_2, ... , a_n\). A është e mundur që duke zëvendësuar vetëm \(k\) prej tyre me numra natyrorë të tjerë (sipas dëshirës), të bëjmë që ky kusht të jetë i vërtetë: \(a_1^2 + a_2^2 + ... + a_n^2 \leq a_1 + a_2 + ... + a_n\)

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

Shembull

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

$ python3 prog.py < input.txt
YES
NO

Kemi 2 rast testimi. Në rastin e parë kemi n=3 dhe k=2, dhe në rreshtin e tretë kemi a1=1, a2=2, a3=5. Nqs zëvendësojmë a2=1 dhe a3=1 atere mosbarazimi plotësohet.

Në rastin e dytë nuk ka mundësi që mosbarazimin ta bëjmë të vërtetë vetëm me 3 zëvendësime.

Zgjidhja 1

T = int(input())
for t in range(T):
    n, k = map(int, input().split())
    A = list(map(int, input().split()))
    nr = 0
    for a in A:
        if a > 1:
            nr += 1
    if nr > k:
        print('NO')
    else:
        print('YES')

https://tinyurl.com/101-prog-005-1

Sqarime

Mosbarazimi i dhënë mund të plotësohet vetëm nëse të gjithë numrat e vargut janë 1 (dhe në këtë rast është barazim).

Te lista A mbajmë vargun e numrave, dhe gjejmë sa prej elementeve të listës janë më të mëdhenj se 1. Nëse ky numër është më i madh se k (numri i elementëve të vargut që mund të zëvendësojmë), atëherë përgjigja është NO (nuk mund ta bëjmë të vërtetë mosbarazimin). Përndryshe përgjigja është YES.

Zgjidhja 2

T = int(input())
for t in range(T):
    n, k = map(int, input().split())
    A = list(map(int, input().split()))
    nr = len([ a for a in A if a > 1 ])
    if nr > k:
        print('NO')
    else:
        print('YES')

https://tinyurl.com/101-prog-005-2

Fillimisht krijojmë një listë të re me të gjithë elementët e listës A që janë më të mëdhenj se 1, dhe pastaj gjejmë gjatësinë e kësaj liste me anë të funksionit len().

Zgjidhja 3

T = int(input())
for t in range(T):
    n, k = map(int, input().split())
    A = list(map(int, input().split()))
    nr = len([ a for a in A if a > 1 ])
    print('NO' if nr > k else 'YES')

https://tinyurl.com/101-prog-005-3

Zgjidhja 4

for _ in range(int(input())):
    n, k = map(int, input().split())
    A = list(map(int, input().split()))
    print('NO' if k < n - A.count(1) else 'YES')

https://tinyurl.com/101-prog-005-4

Detyra

Albani mendon se numri 3 është me fat (nuk thonë kot ‘e treta e vërteta’). Kështu që kur shikon një varg me numra ai numëron sa tresha ka në të. Bëni një program që e ndihmon Albanin të gjejë sa tresha ka në një varg me numra të dhënë. Ky program duhet të shfaqë numrin e treshave, por nëse janë 3 tresha duhet të shkruajë SUPERFAT.

Shembull

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

$ python3 prog.py < input.txt
2
0
SUPERFAT