Misiune
La internat, Janko împarte frigiderul cu alte trei persoane. De multe ori se întâmplă ca mâncarea pe care o pune în ea să dispară misterios de acolo. De exemplu, duminica trecută a adus din casă un delicios pulpă de pui la grătar cu orez și sos de brânză albastră. L-a pus pe raftul lui din frigider, spunând că va fi mâncat luni seara.
Luni seara, la ora 19, s-a întors toată ziua la cămin la facultate, flămând ca un lup. A deschis frigiderul și ce vede aici? Nimic! Coapsa și ideile sale despre o cină delicioasă au dispărut.
Și-a spus că nu poate continua așa și i-a venit ideea: va depozita lucruri necomestibile în frigider, pe lângă lucrurile comestibile. Înfășoară toate lucrurile în folie, astfel încât colegii săi de cameră să nu știe ce se întâmplă.
Problema este că nu va ști ce să mănânce în siguranță. Din fericire, Janko a aflat recent despre cifre la școală, așa că știe să eticheteze pachetele astfel încât numai el să le cunoască conținutul.
Așa că a creat un tabel în care a atribuit fiecărei litere mici ale alfabetului englez exact o literă majusculă a alfabetului englez. A marcat pachetele în două cuvinte. Prima constă din litere mici ale alfabetului englez și a doua din litere mari ale alfabetului englez. Dacă există hrană în pachet, atunci al doilea cuvânt este format din primul conform acestui tabel.
Colegii de cameră ai lui Janek care nu cunosc acest cod sunt destul de susceptibili să se bucure de pachete necomestibile, care pot conține, de exemplu, lemn sau capsule cu pulbere de spălat.
Scrie-i lui Janek un program care să-l ajute să afle dacă pachetul este comestibil.
Sarcina
La intrare este o listă de pachete în frigider. Există exact două cuvinte pe fiecare dintre ele. Conform cuvintelor de pe fiecare pachet, aflați dacă există alimente în el. Există hrană în pachet chiar atunci când:
- Fiecărei litere din primul cuvânt i se atribuie exact o literă majusculă (imagine) în al doilea cuvânt.
- Aceleași litere au aceeași imagine.
- Diferite litere au o imagine diferită.
- Ordinea imaginilor din al doilea cuvânt corespunde ordinii literelor din primul cuvânt.
formatul de intrare
Pe prima linie a intrării este numărul \ (1 \ leq t \ leq 10 ^ 4 \), numărul pachetelor din frigider. Următoarele sunt descrierile \ (t \) ale pachetelor - două rânduri care conțin cuvintele de pe fiecare pachet. Primul cuvânt este format din litere mici și al doilea din majuscule ale alfabetului englez. Fiecare cuvânt conține cel puțin un caracter. Suma lungimilor tuturor cuvintelor nu depășește \ (4 \, 000 \, 000 \) .
Format de iesire
Scrieți „da” pentru fiecare pachet de ieșire, dacă există alimente în el, altfel scrieți „nu”.
Exemple
Intrare:
Ieșire:
De la cuvântul „anna” „a” a apărut pentru a face A ”și„ n ”la„ B ”
Cuvântul „ABB” este mai scurt decât „anna”, deci nu este adevărat că fiecare literă din primul cuvânt este doar secară se afișează la al doilea.
Nicio literă nu se repetă în cuvântul „minge”, deci cinci litere sunt afișate în cinci imagini diferite.
Cuvântul „banane” nu a apărut corect în cuvântul „PINEAPPLE”, deoarece până la două litere „b” și „n” li se atribuie „A”.
Atribuirea spune că avem două șiruri de intrare și sarcina noastră este de a afla dacă îndeplinesc condițiile specificate. Putem rezuma condițiile astfel încât fiecare caracter (mic) al primului cuvânt să corespundă acelorași caractere (mari) - imagini - din al doilea cuvânt. Diferite caractere ale primului cuvânt ar trebui să aibă imagini diferite în al doilea.
Soluție funcțională
În cea mai simplă soluție, este suficient să parcurgeți toate perechile de caractere ale cuvântului original și să verificați dacă sunt îndeplinite condițiile din intrare.
În primul rând, verificăm dacă cuvintele au aceeași lungime. Dacă nu sunt, știm că un caracter al primului cuvânt nu are nicio imagine în al doilea cuvânt sau invers, și astfel putem spune imediat că răspunsul este „nu”.
Acum vine partea principală a soluției. Să presupunem că avem ambele șiruri \ (A \) și \ (B \) de lungime \ (n \) citite în memorie și traversăm ambele cuvinte caracter cu caracter. Scopul este de a verifica dacă toate caracterele îndeplinesc condițiile de introducere specificate. Pentru fiecare \ (i \) -a pereche de caractere \ (A_i \) și \ (B_i \) trecem printr-o altă pereche \ (n - i \) \ (A_j \), \ (B_j \). Există 4 situații care pot apărea în timpul acestei tranziții:
\ (A_j \), \ (B_j \) match \ (A_i \), \ (B_i \) - atunci totul este în regulă. \ (A_i = A_j \) și, prin urmare, imaginile lor sunt aceleași \ (B_i = B_j \) .
\ (A_i \ neq A_j \) și \ (B_i \ neq B_j \) - atunci totul este în regulă. Literele originale sunt diferite și deci imaginile lor sunt diferite.
\ (A_i = A_j \) și \ (B_i \ neq B_j \) (sau invers \ (A_i \ neq A_j \) și \ (B_i = B_j \)) înseamnă că, fie că avem două litere identice în cuvântul original că au imagini diferite sau, în acest din urmă caz, sunt litere diferite în cuvântul original și au aceleași imagini. Ambele cazuri înseamnă că am găsit un personaj care nu îndeplinește condiția misiunii și, prin urmare, răspunsul este „nu”.
Dacă parcurgem întreg cuvântul în acest fel și nu găsim nicio eroare, condițiile sunt îndeplinite pentru toate caracterele și, prin urmare, răspunsul este „da”.
Complexitatea în timp a acestei soluții este \ (O (n ^ 2) \), întrucât pentru fiecare dintre pozițiile \ (n \) \ (i \) trebuie totuși să trecem prin ordinea pozițiilor \ (n \) \ (j \) .
Complexitatea memoriei este \ (Pe) \), deoarece ne amintim două cuvinte cu litere \ (n \).
Cu toate acestea, la intrare putem obține un cuvânt de lungime de până la \ (2 \, 000 \, 000 \), ceea ce înseamnă că, cu complexitatea de timp menționată mai sus, soluția ar rula pentru un timp relativ lung ...
Cifru de substituție
Cu toate acestea, putem simplifica și reformula condițiile din atribuire, astfel încât să dorim ca fiecare literă a alfabetului cu litere mici (din primul cuvânt) să fie criptată la litera alfabetului cu majuscule (din al doilea cuvânt). De asemenea, trebuie să fie adevărat că nu pot fi criptate două litere mici cu aceeași literă mare.
Rețineți că o astfel de criptare poate fi complet definită folosind alfabet de criptare, care este un șir în care caracterul criptat (imaginea) \ (i \) al acelei litere din alfabetul clasic este situat în locul \ (i \). De exemplu, utilizarea alfabetului de criptare ANCDEFGHIJKLMBOPQRSTUVWXYZ transformă cuvântul „abba” în cuvântul „ANNA”. Litera a se schimbă în A, b în N .
O astfel de criptare este denumită în mod obișnuit cifru de substituție. Sarcina noastră este să aflăm dacă textul criptat ar fi putut proveni din original folosind un astfel de cifru.
O soluție mai bună
Și cu ajutorul alfabetului de criptare putem concepe o soluție mai rapidă! Dacă ne amintim alfabetul de criptare, atunci nu trebuie să parcurgem restul cuvântului pentru fiecare caracter, ci trebuie doar să verificăm dacă toate caracterele noi sunt criptate în conformitate cu același alfabet ca și caracterele anterioare.
Ne vom aminti două alfabete de criptare, datorită cărora vom putea implementa criptarea și decriptarea. Un alfabet va cripta caracterele din cuvântul original în cifru, iar celălalt va fi invers - dacă alfabetul de criptare schimbă a în B, atunci alfabetul de decriptare schimbă B în a .
Pentru fiecare caracter \ (i \) -ty din cuvântul original, vom afla dacă avem deja o imagine în alfabet pentru criptare atribuită acestuia. Dacă nu există nicio imagine, înseamnă că am descoperit o astfel de scrisoare pentru prima dată. În acest caz, atribuim imaginea caracterului conform cifrului său, adică caracterul \ (i \) -ty din al doilea cuvânt.
Găsim același lucru pentru caracterele din al doilea cuvânt, criptat, și creăm un alfabet de decriptare.
Dacă caracterul \ (i \) -th are deja o imagine asociată în alfabetul de criptare, verificăm dacă această imagine se potrivește cu caracterul \ (i \) -th din al doilea cuvânt. Dacă nu se potrivesc, am găsit o eroare de criptare - două caractere identice sunt criptate pe imagini diferite. De asemenea, trebuie să verificăm dacă nu se întâmplă ca un caracter diferit să fie criptat pe imaginea \ (i \) -th. Vom verifica acest lucru folosind alfabetul de decriptare construit până acum.
Complexitatea memoriei este practic aceeași ca înainte, deși acum trebuie să ne amintim două alfabete - \ (2 \ ori 26 \) caractere. Inseamna \ (O (2 \ ori n + 2 \ ori 26) \), dar putem neglija constantele atunci când estimăm complexitățile, deoarece ne interesează doar o estimare ordonată a cantității de memorie folosită. Astfel, putem determina complexitatea memoriei rezultate la \ (Pe) \) .
Cu complexitatea timpului, obținem o îmbunătățire semnificativă și ajungem la complexitatea liniară, deoarece efectuăm doar un număr constant de operații pentru fiecare literă. Asa de. \ (Pe) \) .
Discuţie
Aici puteți discuta în mod liber soluția, puteți partaja fragmentele de cod și așa mai departe.
Trebuie să fiți conectat pentru a adăuga comentarii.