Problemi 087

Kërkesa

Regjistrimi në shkollën e lartë bëhet me anë të konkursit. Gjithsej zhvillohen E provime, ku pikët maksimale në çdo provim janë M, dhe merret shuma e pikëve të tyre. Nga N studentë që hyjnë në provime, vetëm K prej tyre që kanë marrë në total më shumë pikë se të tjerët mund të regjistrohen.

Ju i dini pikët që kanë marrë konkurrentët e tjerë në E-1 provimet e mëparshme. Gjithashtu, me një program të inteligjencës artificiale keni parashikuar edhe pikët që do marrin konkurrentët e tjerë në provimin e fundit. Gjeni se sa janë pikët minimale që duhet të merrni në provimin e fundit, në mënyrë që të hyni në shkollë të lartë. Nëse kjo është e pamundur programi duhet të nxjerrë ‘Impossible’.

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

Shembull

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

$ python3 prog.py < input.txt
4

Kemi 1 rast testimi. Rreshti i parë na jep numrat N=4, K=2, E=3, M=10. Katër rreshtat e tjerë na japin pikët që kanë marrë studentët e tjerë në E=3 provimet që janë zhvilluar, me përjashtim të rreshtit të fundit, i cili jep pikët tuaja në E-1 provimet e kaluara. Pikët totale të konkurentëve të tjerë janë 7+7+7=21, 4+6+10=20, dhe 7+10+9=26. Meqenëse vetëm K=2 veta do jenë fitues, juve ju duhen të paktën 22 pikë për të fituar. Deri tani keni marrë 9+9=18 pikë, kështu që në provimin e fundit duhet të merrni të paktën 4 pikë.

Zgjidhja

for _ in range(int(input())):
    N, K, E, M = map(int, input().split())
    P = []
    for i in range(N):
        P.append(sum([int(p) for p in input().split()]))
    p = P[-1]
    del(P[-1])
    P.sort(reverse=True)
    p1 = max(0, P[K-1] - p + 1)
    print(p1) if p1<=M else print('Impossible')

Sqarime

Shumën e pikëve të studentëve të tjerë e vendosim në një listë dhe e rendisim në rendin zbritës. Ai që ndodhet i K-ti në këtë listë do jetë i fundit që do regjistrohet. Për t’ia kaluar atij ju duhet të merrni 1 pikë më tepër.

Detyra

Labirinti më i thjeshtë në botë përbëhet nga një tabelë me përmasa NxN. Duke filluar në cepin e majtë sipër, duhet vajtur në cepin e djathtë poshtë, duke bërë vetëm lëvizje majtas (East) ose poshtë (South).

Na jepen përmasat e tabelës dhe zgjidhja që ka bërë Lida. A mund të gjeni një zgjidhje tjetër që është komplet e ndryshme nga ajo që ka bërë Lida (dmth nqs zgjidhja e Lidës përmban një kalim nga qeliza A në qelizën B, zgjidhja juaj nuk duhet të përmbajë një kalim të tillë).

Referenca: https://codingcompetitions.withgoogle.com/codejam/round/0000000000051705/00000000000881da

Shembull

$ cat input.txt
2
2
SE
5
EESSSESE

$ python3 prog.py < input.txt
Case #1: ES
Case #2: SEEESSES

Rasti i dytë është si në figurë: