|
|||
All You Need Is Love
“All you need is love. All you need is love. Az International Beautiful Machines vállalat megalkotta legújabb hatékony eszközét, a szeretetgépet! Ha megadunk egy bináris számjegyekből álló sztringet, a szeretetgép meghatározza, hogy csupa szeretetből áll-e, azaz hogy csak szeretetre van-e szükség a sztring előállításához. A szeretet definícióját egy másik bináris számjegyekből álló sztring határozza meg a szeretetgép számára, amit egy emberi operátor ad meg. Tegyük fel, hogy van egy L sztringünk, ami a „szeretetet” reprezentálja, és az S sztringet tápláljuk a szeretetgépbe. Akkor mondjuk, hogy S előállításához csak szeretetre van szükség, ha L-et egymás után többször kivonva S-ből végül L-et kapjuk eredményül. Az itt definiált kivonás ugyanazt az aritmetikát alkalmazza, mint a bináris kivonási művelet. Ezen definíció alapján könnyen belátható, hogy ha L > S (binárisan), akkor S nem szeretetből készült. Ha pedig S = L, akkor S nyilvánvalóan szeretetből készült. Nézzünk egy példát! Tegyük fel, hogy S = 11011 és L = 11! Ha újra és újra kivonjuk L-et S-ből, a következőket kapjuk: 11011, 11000, 10101, 10010, 1111, 1100, 1001, 110, 11. Tehát e mellett az L érték mellett S csupa szeretetből áll. A szeretetgép bizonyos korlátai miatt nem adhatunk meg nullával kezdődő sztringeket. Azaz a 0010101, 01110101, 011111 stb. sztringek nem érvényesek. Az egyetlen számjegyből álló sztringek szintén érvénytelenek (ez egy másik korlátozás). A feladatod a következő: ha adott két érvényes bináris sztring (S1 és S2), határozd meg, hogy létezik-e legalább egy olyan érvényes L sztring, amelyre igaz, hogy csupán L-ből előállítható S1 és S2 is. Ha például S1 = 11011 és S2 = 11000, akkor lehet például L = 11 úgy, hogy S1 és S2 is előállítható csupán L-ből (mint ahogy a fenti példában is láthattuk). A bemenet specifikációjaA bemenet első sora egy N < 10000 pozitív egész számot tartalmaz, amely a tesztesetek számát jelenti. Ezt 2N sor követi. Minden teszteset egy sorpárból áll. Az egyes sorpárok két sora a szeretetgép bemenetére küldött sztringeket (S1-et és S2-t) adja meg. Egyetlen sztring sem lesz 30 karakternél hosszabb. Feltételezheted, hogy a bemeneten előforduló minden sztring érvényes a fenti szabályok értelmében. A kimenet specifikációjaMinden sztringpárra egy sort kell a kimenetre írni, amelyben a következő üzenetek egyike szerepel:
Pair #p: All you need is love!
Itt p a pár sorszámát jelöli (1-től kezdődően). Akkor kell kiírnod az első üzenetet, ha van legalább egy olyan érvényes L sztring, amelyre igaz, hogy S1 és S2 is előállítható csupán L-ből. Ha nem így van, a második sort kell kiírni. Példa bemenet
A példa bemenethez tartozó kimenet
|
|||
| Debreceni Egyetem, Informatikai Kar, v. 2019.03.01. |