Problemi 035

Kërkesa

Në një reaktor bërthamor janë K dhoma njëra pas tjetrës, të etiketuara nga 0 në K-1. Grimcat vazhdimisht mblidhen në dhomën 0. Por nëse bëhen më shumë se N grimca në një dhomë, ndodh një reaksion i cili bën që një nga grimcat të kalojë në dhomën pasardhëse, kurse të tjerat zhduken. E njëjta gjë vazhdon edhe në dhomat pasardhëse, deri sa asnjë nga dhomat të mos ketë më shumë se N grimca. Pasi të gjitha këto reaksione kanë përfunduar, vjen grimca tjetër në dhomën 0, e kështu me radhë.

Nëse numri total i grimcave të bombarduara është A, sa është numri i grimcave në secilën dhomë në fund të bombardimit?

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

Shembull

$ cat input.txt
3
3 1 3
11 2 2
100 13 3

$ python3 prog.py < input.txt
1 1 0
2 0
2 7 0

Në rastin e parë, pasi bombardohet grimca e parë gjendja e dhomave është 1 0 0. Pasi bombardohet grimca e dytë, te dhoma e parë bëhen 2, kështu që një grimcë kalon te dhoma djathtas, kurse të tjerat zhduken: 0 1 0. Pas grimcës së tretë gjendja është: 1 1 0.

Zgjidhja 1

for _ in range(int(input())):
    A, N, K = map(int, input().split())
    R = [0] * K
    for i in range(A):
        R[0] += 1
        for j in range(K-1):
            if R[j] > N:
                R[j+1] += 1
                R[j] = 0
            else:
                break
        if R[-1] > N:
            R[-1] = 0
        #print(R)    # debug
    print(' '.join(map(str, R)))

Sqarime

Thjesht simulojmë dhomat e reaktorit, bombardimin e A grimcave, dhe reaksionin sa herë që bëhen më shumë se N grimca në një dhomë. Në fund shfaqim rezultatin që kemi në R.

Zgjidhja 2

for _ in range(int(input())):
    A, N, K = map(int, input().split())
    R = [0] * K
    N += 1
    i = 0
    while A > 0 and i < K:
        R[i] = A % N
        A //= N
        i += 1
    print(' '.join(map(str, R)))

Sqarime

Kjo zgjidhje është edhe më e thjeshtë edhe më efiçente (më e shpejtë) se e para, sepse këtu duhen K hapa (ose veprime) për të gjetur rezultatin, kurse te e para duhen A hapa (që mund të jetë edhe numër shumë i madh).

Kjo zgjidhje bazohet në faktin që mënyra se si zhvillohen reaksionet është e ngjashme me paraqitjen e numrit A në bazën N+1, kështu që ne mund ta gjejmë rezultatin duke përdorur mbetjen dhe herësin e pjesëtimit me N+1.

Detyra

Gjuhët e harruara janë gjuhë që janë përdorur dikur gjerësisht por sot nuk përdoren më. Megjithatë disa prej fjalëve të tyre mund të jenë ende në përdorim në gjuhët e sotme.

Ju keni gjetur në internet N fjalë të një gjuhe të harruar. Gjithashtu keni edhe K fjali që përdoren në gjuhët e sotme. Detyra juaj është që të përcaktoni për secilën prej N fjalëve nëse gjendet në ndonjërën nga këto K fjalitë ose jo.

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

Shembull

$ cat input.txt
2
3 2
piygu ezyfo rzotm
1 piygu
6 tefwz tefwz piygu ezyfo tefwz piygu
4 1
kssdy tjzhy ljzym kegqz
4 kegqz kegqz kegqz vxvyj

$ python3 prog.py < input.txt
YES YES NO
NO NO NO YES

Kemi 2 raste testimi. Në rastin e parë, kemi N=3 fjalë të gjuhës së harruar dhe K=2 fjali të gjuhëve të sotme. Pastaj vijnë 2 fjalitë, ku e para ka 1 fjalë dhe e dyta ka 6 fjalë. Dy fjalët e para ndodhen në këtë fjali, kurse e treta jo.