Problemi 059

Kërkesa

Në një festë morën pjesë N djem dhe M vajza. Na jepet një matricë \(A\) me N rreshta dhe M shtylla, ku \(A_{ij}\) është 1 nëse djalit i i pëlqen vajza j, përndryshe është 0. Vini re që nuk është e thënë që nëse djalit x i pëlqen vajza y, edhe vajzës y i pëlqen djali x.

Nqs dy djemve x dhe y u pëlqen vajza z, kjo quhet një përplasje. Gjeni numrin e përplasjeve të ndryshme në këtë festë. Vini re që radha e djemve në një përplasje nuk ka rëndësi.

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

Shembull

$ cat input.txt
2
4 3
111
100
110
000
2 2
10
01

$ python3 prog.py < input.txt
4
0

Jepet numri i djemve the i vajzave N dhe M, dhe pastaj matrica e pëlqimeve me 0/1.

Në rastin e parë, tre djem e kanë qejf vajzën e parë, kështu që kemi 3 përplasje (i pari me të dytin, i dyti me të tretin, dhe i pari me të tretin). Djali i parë dhe i tretë pëlqejnë vajzën e dytë, kështu që kemi edhe një përplasje tjetër. Gjithsej 4 përplasje.

Në rastin e dytë kemi 2 djem dhe 2 vajza, dhe asnjë përplasje.

Zgjidhja

for _ in range(int(input())):
    n, m = map(int, input().split())
    L = []
    for i in range(n):
        L.append(input())

    c = 0    # number of collisions
    for i in range(m):
        k = 0
        for j in range(n):
            if L[j][i] == '1':
                p += 1
        c += p * (p - 1) // 2
    print(c)

Sqarime

Matricën e mbajmë në një listë me rreshta. Për çdo vajzë, gjejmë se sa djem e pëlqejnë atë, dhe këtë e mbajmë në ndryshoren p. Numri i përplasjeve për çdo vajzë është sa numri i dysheve që mund të formohen nga p, i cili është **p*(p-1)/2**.

Detyra

Një makinë llogaritëse është me difekt. Kur mbledh dy numra ajo nuk e transferon tepricën, p.sh 12 + 9 sipas saj del 11. Bëni një program që merr 2 numra dhe nxjerr rezultatin që do nxirrte kjo makinë llogaritëse për mbledhjen e tyre.

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

Shembull

$ cat input.txt
2
12 9
25 25

$ python3 prog.py < input.txt
11
40