Problemi 125

Kërkesa

Na jepen dy vargje shkronjash A dhe B. A është e mundur të gjejmë një nënvarg s1 në A dhe një nënvarg s2 në B, që mos të jenë bosh, dhe që s1+s2 të jetë palindromë?

Shenja + tregon bashkimin ose ngjitjen e dy vargjeve, kurse palindromë do të thotë që po ta lexosh vargun nga fundi në fillim është njësoj me vargun fillestar (nga fillimi në fund).

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

Shembull

$ cat input.txt
3
abc
abc
a
b
abba
baab

$ python3 prog.py < input.txt
Yes
No
Yes

Në rastin e parë, një nga zgjedhjet e mundshme është s1 = "ab" dhe s2 = "a". Atere kemi s1+s2 = "aba" e cila është palindromë, kështu që përgjigja është “Yes”.

Në rastin e dytë kemi A = "a" dhe B = "b" dhe nuk ka asnjë mundësi që të krijojmë ndonjë palindromë, kështu që përgjigja është “No”.

Zgjidhja

for _ in range(int(input())):
    if len(set(input()).intersection(set(input()))) == 0:
        print('No')
    else:
        print('Yes')

Sqarime

Meqenëse nënvargjet s1 dhe s2 nuk mund të jenë bosh dhe shkronja e parë e s1+s2 duhet të jetë e njëjtë me shkronjën e fundit (nga përkufizimi i palindromës), i bie që vargjet A dhe B duhet të kenë të paktën një shkronjë të përbashkët, përndryshe nuk mund të formojmë një palindromë. Nga ana tjetër, nqs A dhe B kanë një shkronjë të përbashkët, p.sh. x, atere ne mund të zgjedhim s1 = "x" dhe s2 = "x" dhe s1+s2 = "xx" do jetë një palindromë.

Kështu që kusht i nevojshëm dhe i mjaftueshëm që problemi të ketë zgjidhje është që A dhe B të kenë të paktën një shkronjë të përbashkët. Edhe programi i zgjidhjes pikërisht për këtë kontrollon: i kthen vargjet A dhe B në bashkësi shkronjash, gjen prerjen e tyre, dhe shikon nëse prerja është bosh ose jo.