Problemi 065

Kërkesa

Një bashkësi me numra natyrorë quhet e mirë nëse nuk ekzistojnë në të tre elemente të ndryshëm a, b, c të tillë që a + b = c.

Bëni një program që merr një numër n (nga 1 deri në 100) dhe nxjerr një bashkësi të mirë me n elementë, ku çdo element i bashkësisë mund të jetë një numër nga 1 deri në 500.

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

Shembull

$ cat input.txt
5
1
2
3
4
5

$ python3 prog.py < input.txt
7
1 2
1 2 4
1 2 4 16
3 2 15 6 10

Zgjidhja 1

for _ in range(int(input())):
    n = int(input())
    s = []
    for i in range(n):
        s.append(500 - i)
    print(*s)

Sqarime

Mqs bashkësia nuk mund të ketë më shumë se 100 numra, dhe këta numra mund të jenë deri në 500, mund ti zgjedhim numrat nga 400 deri në 500, dhe jemi të sigurtë që shuma e tyre do jetë më e madhe se 500, kështu që nuk do jetë në bashkësi.

Zgjidhja 2

for _ in range(int(input())):
    n = int(input())
    s = []
    for i in range(n):
        s.append(250 + i)
    print(*s)

Sqarime

Pak a shumë njësoj si zgjidhja e parë, vetëm se numrat zgjidhen duke filluar nga 250 e lartë.

Zgjidhja 3

for _ in range(int(input())):
    n = int(input())
    s = []
    for i in range(n):
        s.append(2*i + 1)
    print(*s)

Sqarime

Nqs zgjedhim në bashkësi vetëm numra tek, shuma e tyre do jetë numër çift, kështu që është e garantuar që nuk do jetë në bashkësi.

Detyra

Një bankomat (ATM) ka brenda K para. Në radhë janë N klientë, ku secili do që të tërheqë \(A_i\) para. Nëse bankomati ka gjendje aq sa kërkon klienti ose më shumë, ai ia jep lekët klientit, përndryshe nxjerr një mesazh gabimi dhe klienti largohet pa marrë lekë. Gjeni për secilin klient nëse i ka marrë lekët ose jo.

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

Shembull

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

$ python3 prog.py < input.txt
11010
0010

Kur klienti i merr lekët shënohet me 1, përndryshe shënohet me 0.

Në rastin e parë janë 5 klientë dhe bankomati ka 10 lekë. Pasi merr lekët klienti i parë dhe i dytë, në bankomat mbeten 2 lekë, të cilat janë të pamjaftueshme për ti dhënë lekët klientit të tretë, por mjaftojnë për ti dhënë lekët klientit të katërt.

Në rastin e dytë janë 4 klientë dhe bankomati ka 6 lekë. Dy klientët e parë nuk mund ti tërheqin lekët, por i treti po. Pastaj nuk ngelet më asnjë lekë, kështu që as klienti i katërt nuk mund ti tërheqë lekët.