Feladat
A bentlakásos iskolában Janko három másik emberrel osztozik egy hűtőszekrényben. Gyakran előfordul, hogy az általa beletett étel rejtélyes módon eltűnik onnan. Például múlt vasárnap hozott egy finom, roston sült csirkecombot rizzsel és kéksajtmártással a házból. Letette a hűtőszekrény polcára, hétfőn este megette.
Hétfőn este 19 órakor éhes volt, mint a farkas, egész nap a karon a kollégiumba. Kinyitotta a hűtőszekrényt, és mit lát itt? Semmi! A comb és az ötletek egy finom vacsoráról eltűntek.
Azt mondta magának, hogy ez így nem mehet tovább, és előállt az ötlettel: az ehető dolgokon kívül ehető ételeket is tárol a hűtőszekrényben. Minden dolgot fóliába csomagol, hogy szobatársai ne tudják, mi történik.
A probléma az, hogy nem fogja tudni, mit fogyasszon biztonságosan. Szerencsére Janko nemrégiben tanult a titkosításról az iskolában, így tudja, hogyan kell címkézni a csomagokat, hogy csak ő ismerje azok tartalmát.
Így létrehozott egy táblázatot, amelyben az angol ábécé minden kisbetűjéhez pontosan az angol ábécé egy nagybetűjét rendelte hozzá. Két szóval jelölte meg a csomagokat. Az első az angol ábécé kisbetűiből, a második az angol ábécé nagybetűiből áll. Ha van étel a csomagban, akkor a második szó az elsőből alakul ki ennek a táblázatnak megfelelően.
Janek szobatársai, akik nem ismerik ezt a kódot, nagy valószínűséggel élvezik az ehetetlen csomagokat, amelyek például fát vagy mosóporos kapszulát tartalmazhatnak.
Írjon Janeknek egy programot, amely segít megtudni, hogy a csomag ehető-e.
A feladat
A bejáratnál egy csomag található a hűtőszekrényben. Mindkettőn pontosan két szó van. Az egyes csomagokon szereplő szavakból derítse ki, van-e benne étel. Élelmiszer van a csomagban, amikor:
- Az első szó minden betűjéhez pontosan egy nagybetű (kép) tartozik a második szóban.
- Ugyanazoknak a betűknek ugyanaz a képe.
- A különböző betűknek más a képük.
- A második szó képeinek sorrendje megegyezik az első szó betűinek sorrendjével.
Beviteli formátum
A bemenet első sorában a \ (1 \ leq t \ leq 10 ^ 4 \) szám, a hűtőszekrényben lévő csomagok száma található. Az alábbiakban a csomagok \ (t \) leírása található - két sor, amelyek az egyes csomagokon található szavakat tartalmazzák. Az első szó kisbetűkből áll, a második pedig az angol ábécé nagybetűiből. Minden szó legalább egy karaktert tartalmaz. Az összes szó hosszának összege nem haladja meg a \ (4 \, 000 \, 000 \) értéket .
Kimeneti formátum
Írjon "igen" minden kimeneti csomagra, ha van élelmiszer, különben írjon "nem".
Példák
Bemenet:
Kimenet:
Az 'anna' szóból az 'a' jelent meg A-t és az n-t a B-ig
Az "ABB" szó rövidebb, mint az "anna", ezért nem igaz, hogy az első szó minden betűje az éppen Rozs megjelenik a másodikra.
A "labda" szóban egyetlen betű sem ismétlődik meg, ezért öt betű jelenik meg öt különböző képen.
A „banán” szó nem szerepelt helyesen a „PINEAPPLE” szóban, mivel legfeljebb két „b” és „n” betűhöz rendelték az „A” betűt.
A hozzárendelés azt mondja, hogy két karakterlánc van a bemeneten, és az a feladatunk, hogy kiderítsük, megfelelnek-e a megadott feltételeknek. Összefoglalhatjuk a feltételeket úgy, hogy az első szó minden azonos (kis) karaktere megegyezzen a második szó ugyanazokkal (nagy) karaktereivel - képeivel. Az első szó különböző karaktereinek másképp kell lenniük.
Funkcionális megoldás
A legegyszerűbb megoldásnál elegendő az eredeti szó összes karakterpárját átnézni és ellenőrizni, hogy a bemeneti feltételek teljesülnek-e.
Először ellenőrizzük, hogy a szavak azonos hosszúak-e. Ha nem, akkor tudjuk, hogy az első szó valamelyik karakterének nincs képe a második szóban, vagy fordítva, ezért azonnal azt mondhatjuk, hogy a válasz "nem".
Most jön a megoldás fő része. Tegyük fel, hogy mindkét \ (A \) és \ (B \) hosszúságú \ (n \) memóriát olvasunk, és mindkét szót karakterenként haladjuk át. A cél annak ellenőrzése, hogy minden karakter megfelel-e a megadott beviteli feltételeknek. Minden \ (i \) -edik karakterpárra \ (A_i \) és \ (B_i \) átadjuk a többi \ (n - i \) párot \ (A_j \), \ (B_j \). A feltérképezés során 4 helyzet fordulhat elő:
\ (A_j \), \ (B_j \) egyezik \ (A_i \), \ (B_i \) - akkor minden rendben van. \ (A_i = A_j \), ezért képeik megegyeznek \ (B_i = B_j \) .
\ (A_i \ neq A_j \) és \ (B_i \ neq B_j \) - akkor minden rendben is van. Az eredeti betűk különböznek, ezért képeik is eltérőek.
\ (A_i = A_j \) és \ (B_i \ neq B_j \) (vagy fordítva \ (A_i \ neq A_j \) és \ (B_i = B_j \)) azt jelenti, hogy vagy az eredeti szóban két azonos betű van hogy különböző képeik vannak, vagy ez utóbbi esetben az eredeti szóban különböző betűk vannak, és ugyanazok a képek. Mindkét eset azt jelenti, hogy olyan karaktert találtunk, amely nem felel meg a hozzárendelés feltételének, ezért a válasz "nem".
Ha ily módon végigmegyünk az egész szóon, és nem találunk hibát, akkor az összes karakter teljesül, és ezért a válasz "igen".
A megoldás időbeli összetettsége \ (O (n ^ 2) \), mivel mindegyik \ (n \) pozícióhoz \ (i \) még mindig át kell élnünk a \ (n \) pozíciók \ (j \) sorrendjét .
A memória bonyolultsága az \ (Tovább) \), mert két szóra emlékszünk \ (n \) betûvel.
A bemenetnél azonban kaphatunk akár \ (2 \, 000 \, 000 \) hosszúságú szót is, ami azt jelenti, hogy a fent említett időbonyolultság mellett a megoldás viszonylag hosszú ideig futna ...
Helyettesítési rejtjel
Egyszerűsíthetjük és átfogalmazhatjuk a feltételeket a hozzárendeléstől úgy, hogy azt akarjuk, hogy a kisbetűs ábécé minden egyes betűjét (az első szótól kezdve) a nagybetűs betűig (a második szótól) kódoljuk. Az is igaz, hogy egyetlen kisbetű sem kódolható ugyanazon nagybetűvé.
Vegye figyelembe, hogy az ilyen titkosítás teljesen meghatározható a titkosítási ábécé, amely egy karakterlánc, amelyben a klasszikus ábécé adott betűjének titkosított karaktere (kép) \ (i \) a \ (i \) -edik helyen található. Például az ANCDEFGHIJKLMBOPQRSTUVWXYZ titkosító ábécé használatával az „abba” szó „ANNA” szóvá válik. Az a betű A-ra változik, b-ről N-re változik .
Az ilyen titkosítást általában hívják helyettesítő rejtjel. Feladatunk az, hogy egy ilyen titkosítás segítségével kiderítsük, hogy a titkosított szöveg származhat-e az eredetiből.
Jobb megoldás
És a titkosítási ábécé segítségével tervezhetünk gyorsabb megoldást! Ha emlékszünk a titkosítási ábécére, akkor nem kell minden karakternél végigélnünk a szó többi részét, hanem csak azt kell ellenőriznünk, hogy az összes új karakter ugyanolyan ábécé szerint van-e titkosítva, mint az előző karakterek.
Két titkosító ábécére fogunk emlékezni, amelyeknek köszönhetően képesek leszünk megvalósítani a titkosítást és a visszafejtést. Az egyik ábécé az eredeti szóból a karaktereket kódolja a rejtjelbe, a másik pedig inverz lesz rá - ha a titkosítási ábécé szerint a-t B-re változtatja, akkor B a visszafejtési ábécé szerint a-ra változik. .
Az eredeti szó minden \ (i \) -ty karakteréhez megtudjuk, hogy van-e már képünk az ábécében a titkosításhoz. Ha nincs kép, az azt jelenti, hogy először fedeztünk fel egy ilyen levelet. Ebben az esetben hozzárendeljük a képet a karakterhez annak titkosítása szerint, azaz a \ (i \) -ty karaktert a második szóban.
Ugyanezt találjuk a második, titkosított szóban szereplő karakterek esetében is, és létrehozunk egy visszafejtő ábécét.
Ha az \ (i \) -edik karakterhez már van kép társítva a titkosítási ábécében, akkor ellenőrizzük, hogy ez a kép megegyezik-e a második szó \ (i \) -edik karakterével. Ha nem egyeznek, akkor egy titkosítási hibát találtunk - két azonos karakter van titkosítva a különböző képeken. Azt is ellenőriznünk kell, hogy véletlenül egy másik karakter nincs-e titkosítva az \ (i \) -th képen. Ezt az eddig felépített visszafejtő ábécé segítségével ellenőrizzük.
A memória bonyolultsága alapvetően megegyezik a korábbiakkal, bár most két ábécére - \ (2-szer 26-szor \) - kell emlékeznünk. Azt jelenti \ (O (2-szer n + 2-szer 26-szor) \), de az összetettség becslésénél elhanyagolhatjuk az állandókat, mivel csak a felhasznált memória mennyiségének nagyságrendű becslése érdekel. Így meghatározhatjuk a kapott memória komplexitást a \ (Tovább) \) .
Az idő komplexitásával jelentős javulást érünk el, és eljutunk a lineáris komplexitásig, mivel minden betűhöz csak állandó számú műveletet hajtunk végre. Így. \ (Tovább) \) .
Vita
Itt szabadon megvitathatja a megoldást, megoszthatja kódjait és így tovább.
Megjegyzések hozzáadásához be kell jelentkeznie.