Възлагане
В интерната Янко споделя хладилник с още трима души. Често се случва храната, която влага в нея мистериозно да изчезне от там. Например миналата неделя той донесе вкусен пилешки бут на скара с ориз и сос от синьо сирене от къщата. Той го остави на рафта на хладилника си и го изяде в понеделник вечер.
В понеделник вечерта в 19 ч. Той се върнал в общежитието цял ден във факултета, гладен като вълк. Той отвори хладилника и какво вижда тук? Нищо! Бедрото и идеите му за вкусна вечеря ги няма.
Каза си, че не може да продължава така, и излезе с идеята: Той ще съхранява негодни за консумация неща в хладилника в допълнение към годни за консумация неща. Той увива всички неща във фолио, така че съквартирантите му да не знаят какво става.
Проблемът е, че той няма да знае какво да яде безопасно. За щастие, Янко наскоро научи за шифри в училище, така че знае как да етикетира опаковките, така че само той да знае тяхното съдържание.
Така той създаде таблица, в която присвоява на всяка малка буква от английската азбука точно една главна буква от английската азбука. Той отбеляза пакетите с две думи. Първата се състои от малки букви от английската азбука, а втората от главни букви от английската азбука. Ако в опаковката има храна, тогава втората дума се формира от първата според тази таблица.
Съквартирантите на Janek, които не познават този код, доста вероятно ще се радват на негодни за консумация опаковки, които могат да съдържат например дърво или капсули с прах за пране.
Напишете на Janek програма, която да му помогне да разбере дали опаковката е годна за консумация.
Задачата
На входа има списък с пакети в хладилника. На всяка от тях има точно две думи. Според думите на всяка опаковка разберете дали в нея има храна. В опаковката има храна точно когато:
- На всяка буква в първата дума е зададена точно една главна буква (изображение) във втората дума.
- Едни и същи букви имат едно и също изображение.
- Различните букви имат различно изображение.
- Редът на изображенията във втората дума съответства на реда на буквите в първата дума.
Формат на въвеждане
Първият ред на входа съдържа числото \ (1 \ leq t \ leq 10 ^ 4 \), броя на опаковките в хладилника. По-долу са описанията \ (t \) на пакетите - два реда, съдържащи думите на всеки пакет. Първата дума се състои от малки букви, а втората от главни букви от английската азбука. Всяка дума съдържа поне един знак. Сумата от дължините на всички думи не надвишава \ (4 \, 000 \, 000 \) .
Изходен формат
Напишете "да" за всеки изходен пакет, ако в него има храна, в противен случай напишете "не".
Примери
Вход:
Изход:
От думата „anna“ „a“ се появява като A и „n“ до „B“
Думата "ABB" е по-кратка от "anna", така че не е вярно, че всяка буква от първата дума е просто Ръж показва на втория.
В думата „топка“ не се повтаря нито една буква, така че пет букви се показват в пет различни изображения.
Думата „банани“ не се появи правилно в думата „АНАНАС“, тъй като до две букви „b“ и „n“ са присвоени „A“.
Заданието казва, че имаме два низа на входа и нашата задача е да разберем дали отговарят на посочените условия. Можем да обобщим условията, така че всеки един и същ (малък) знак на първата дума да съответства на едни и същи (големи) знаци - изображения - във втората дума. Различните знаци на първата дума трябва да имат различни изображения във втората.
Функционално решение
В най-простото решение е достатъчно да преминете през всички двойки символи на оригиналната дума и да проверите дали условията от въведеното са изпълнени.
На първо място проверяваме дали думите са с еднаква дължина. Ако не са, знаем, че някакъв знак от първата дума няма изображение във втората дума, или обратно, и затова веднага можем да кажем, че отговорът е „не“.
Сега идва основната част от решението. Да кажем, че имаме и двата низа \ (A \) и \ (B \) с дължина \ (n \) прочетени в паметта и преминаваме през двете думи символ по знак. Целта е да се провери дали всички знаци отговарят на посочените условия за въвеждане. За всяка \ (i \) -та двойка символи \ (A_i \) и \ (B_i \) предаваме другите \ (n - i \) двойки \ (A_j \), \ (B_j \). Има 4 ситуации, които могат да възникнат по време на това обхождане:
\ (A_j \), \ (B_j \) съвпадат \ (A_i \), \ (B_i \) - тогава всичко е наред. \ (A_i = A_j \) и следователно техните изображения са еднакви \ (B_i = B_j \) .
\ (A_i \ neq A_j \) и \ (B_i \ neq B_j \) - тогава всичко също е наред. Оригиналните букви са различни и затова изображенията им са различни.
\ (A_i = A_j \) и \ (B_i \ neq B_j \) (или обратно \ (A_i \ neq A_j \) и \ (B_i = B_j \)) означава, че или имаме две еднакви букви в оригиналната дума че имат различни изображения или, в последния случай, те са различни букви в оригиналната дума и имат еднакви изображения. И двата случая означават, че сме намерили герой, който не отговаря на условието на заданието и следователно отговорът е „не“.
Ако преминем през цялата дума по този начин и не открием грешка, условията са изпълнени за всички знаци и следователно отговорът е „да“.
Сложността във времето на това решение е \ (O (n ^ 2) \), като има предвид, че за всяка от позициите \ (n \) \ (i \) все още трябва да преминем през реда на \ (n \) позиции \ (j \) .
Сложността на паметта е \ (На) \), защото помним две думи с букви \ (n \).
На входа обаче можем да получим дума с дължина до \ (2 \, 000 \, 000 \), което означава, че с гореспоменатата времева сложност, решението ще работи сравнително дълго време ...
Заместващ шифър
Можем обаче да опростим и преформулираме условията от заданието, така че да искаме всяка буква от малката азбука (от първата дума) да бъде криптирана до буквата на голямата азбука (от втората дума). Трябва също така да е вярно, че не могат да се криптират две малки букви в една и съща главна буква.
Имайте предвид, че такова криптиране може да бъде напълно дефинирано с помощта на криптиране азбука, което е низ, в който криптираният знак (изображение) \ (i \) на тази буква от класическата азбука се намира на \ (i \) -то място. Например, използвайки азбуката за криптиране ANCDEFGHIJKLMBOPQRSTUVWXYZ превръща думата „abba“ в думата „ANNA“. Буквата a се променя на A, b на N .
Такова криптиране обикновено се нарича заместващ шифър. Нашата задача е да разберем дали шифрованият текст е могъл да произхожда от оригинала с помощта на такъв шифър.
По-добро решение
И именно с помощта на азбуката за криптиране можем да проектираме по-бързо решение! Ако си спомняме азбуката за криптиране, тогава не е нужно да преглеждаме останалата част от думата за всеки знак, а трябва само да проверим дали всички нови знаци са криптирани според същата азбука като предишните знаци.
Ще запомним две азбуки за криптиране, благодарение на които ще можем да реализираме криптиране и дешифриране. Едната азбука ще криптира символите от оригиналната дума в шифъра, а другата ще бъде обратна на нея - ако променя а на В според азбуката за криптиране, тогава В се променя на а според азбуката за дешифриране. .
За всеки знак \ (i \) -ty от оригиналната дума ще разберем дали вече имаме изображение в азбуката за криптиране, което му е присвоено. Ако няма изображение, това означава, че открихме такова писмо за първи път. В този случай ние присвояваме изображението на героя според неговия шифър, т.е. символа \ (i \) във втората дума.
Намираме същото за символите във втората, криптирана дума и създаваме азбука за дешифриране.
Ако \ (i \) -тият знак вече има изображение, свързано с него в азбуката за шифроване, ние проверяваме дали това изображение съвпада с \ (i \) -тия знак във втората дума. Ако не съвпадат, открихме грешка при криптиране - два еднакви знака са криптирани на различни изображения. Също така трябва да проверим дали случайно не е криптиран различен знак върху изображението на \ (i \) -th. Ще проверим това, използвайки азбуката за дешифриране, изградена досега.
Сложността на паметта по същество е същата като преди, въпреки че сега трябва да запомним две азбуки - \ (2 \ по 26 \) знака. Това означава \ (O (2 \ пъти по n + 2 \ по 26) \), но можем да пренебрегнем константите, когато оценяваме сложността, тъй като ни интересува само оценка от порядъка на размера на използваната памет. По този начин можем да определим произтичащата сложност на паметта при \ (На) \) .
Със сложността на времето получаваме значително подобрение и стигаме до линейна сложност, тъй като изпълняваме само постоянен брой операции за всяка буква. Така. \ (На) \) .
Дискусия
Тук можете свободно да обсъждате решението, да споделяте своите парчета код и така нататък.
Трябва да влезете, за да добавяте коментари.