Problemi 082

Kërkesa

Në një listë me numra natyrorë bëjmë këtë veprim: Zgjedhim disa prej numrave të listës dhe i fshijmë nga lista. Si kosto të këtij veprimi përkufizojmë rezultatin e kryerjes së një Bitwise OR midis elementeve të fshira. Këtë veprim e përsërisim deri sa në listë të mos ngelet më asnjë element. Kostoja e përgjithshme është shuma e kostos së çdo veprimi. Gjeni vlerën më të vogël të mundshme të kostos së përgjithshme.

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

Shembull

$ cat input.txt
2
2
1 2
3
1 3 6

$ python3 prog.py < input.txt
3
7

Zgjidhja 1

for _ in range(int(input())):
    input()
    c = 0
    for i in input().split():
        c |= int(i)
    print(c)

Sqarime

Veprimi bitwise OR merr paraqitjen binare të dy numrave dhe bën veprimin llogjik OR për çiftet korresponduese të biteve. P.sh. 3 = 0011, 5 = 0101, 3 OR 5 = 0011 | 0101 = 0111 = 7. Dmth nqs njëri nga bitet korresponduese është 1 (ose të dy janë 1) rezultati del 1. Nqs të dy janë 0 rezultati del 0.

Le ta zëmë se kemi 2 numra të listës që kanë 1 në të njëjtin pozicion. Nqs këta numra do ishin fshirë në veprime të ndryshme, vlera përkatëse që paraqet ky njësh (që është një nga fuqitë e dyshit) do ti shtohej kostos së përgjithshme dy herë. Kurse po të fshihen nga lista në të njëjtin veprim, kjo vlerë i shtohet kostos totale vetëm një herë, kështu që kostoja totale do jetë më e vogël se në rastin e parë.

Kjo do të thotë që vlera minimale e kostos së përgjithshme arrihet kur kryhet vetëm një veprim, i cili i fshin të gjithë numrat e listës.

Zgjidhja 2

from functools import reduce
for _ in range(int(input())):
    input()
    L = [int(i) for i in input().split()]
    print(reduce(lambda x,y: x|y, L))

Zgjidhja 3

from functools import reduce
from operator import __or__
for _ in range(int(input())):
    input()
    L = [int(i) for i in input().split()]
    print(reduce(__or__, L))

Detyra

Na jepet një varg S me gjatësi N dhe një shkronjë X. Gjeni numrin e nënvargjeve të S që e përmbajnë shkronjën X të paktën një herë.

Referenca: https://www.codechef.com/APRIL19B/problems/STRCH

Shembull

$ cat input.txt
2
3
abb b
6
abcabc c

$ python3 prog.py < input.txt
5
15

Në rastin e parë, vargu abb ka gjashtë nënvargje: a, b, b, ab, bb, abb. Nënvargjet që përmbajnë b janë: b, b, ab, bb, abb.