Jump to content
Main menu
Main menu
move to sidebar
hide
Navigation
Main page
Recent changes
Random page
Help about MediaWiki
Bitnami MediaWiki
Search
Search
Create account
Log in
Personal tools
Create account
Log in
Pages for logged out editors
learn more
Contributions
Talk
Editing
0615 - Gate
Page
Discussion
English
Read
Edit
Edit source
View history
Tools
Tools
move to sidebar
hide
Actions
Read
Edit
Edit source
View history
General
What links here
Related changes
Special pages
Page information
Warning:
You are not logged in. Your IP address will be publicly visible if you make any edits. If you
log in
or
create an account
, your edits will be attributed to your username, along with other benefits.
Anti-spam check. Do
not
fill this in!
După ce a ajutat la conectarea oraşelor Nordemos şi Suderim, Negrimon s-a hotărât să-şi urmeze destinul şi să devină un programamon roşu. Pentru a-şi începe călătoria, este nevoit să părăsească Udobje Lurrak şi să treacă prin Sha’ar Azih, poarta magică de la ieşirea din oraşul Estumar. Această poartă se bazează pe un sistem de runix-uri aşezate în linie, numerotate de la 1 la N. Un runix este un pătrat pe care este înscrisă o literă mică, din mulţimea unui alfabet restrâns, format din primele L litere ale alfabetului englez. Alfabetul restrâns este circular, astfel încât după ultima literă urmează prima, iar înainte de prima literă este ultima literă din alfabet. În starea iniţială a sistemului, primul runix este setat pe litera a, al doilea runix este setat pe următoarea literă din alfabetul restrâns ş.a.m.d . De exemplu: *pentru N = 8 şi L = 3, sistemul are configuraţia iniţială: abcabcab *pentru N = 11 şi L = 4, sistemul are configuraţia iniţială: abcdabcdabc *pentru N = 14 şi L = 7, sistemul are configuraţia iniţială: abcdefgabcdefg Când Negrimon ajunge la poartă, aceasta prinde viaţă şi se produce un şir de acţiuni de următorul tip: # Runix-ul cu numărul r împreună cu toate runix-urile din stânga se deplasează şi se separă de cele din dreapta (dacă există), formându-se astfel două grupuri independente (iniţial toate runix-urile formează un singur grup). # Toate runix-urile din grupul din care face parte runix-ul cu numărul r execută o schimbare de pas p. Aceasta constă în înlocuirea literei asociate cu următoarea a p-a literă din alfabet (p > 0) sau cu precedenta a (-p)-a literă din alfabet (p < 0). Datorită circularităţii alfabetului, oricât de mare ar fi p va exista o literă care să fie la distanţa p faţă de litera actuală. # Negrimon primeşte o întrebare de tipul: pe ce literă este setat runix-ul cu numărul r? Poarta se deschide dacă Negrimon răspunde corect la toate întrebările primite şi astfel își poate continua călătoria în Azih Lurrak. == Cerința == Ajutaţi-l pe Negrimon să deschidă poarta. == Date de intrare == Pe prima linie a fişierului gatein.txt se află valorile N L M, separate prin câte un spaţiu, cu semnificația: N – numărul de runix-uri din sistem, L – numărul de litere din alfabetul restrâns, M – numărul de acţiuni desfăşurate. Fiecare dintre următoarele M linii conţine valorile t – tipul acţiunii, r – numărul runix-ului la care se face referire, p – schimbarea de pas a runix-ului, dacă acţiunea este una de tipul 2 (t = 2), toate separate prin câte un spaţiu. == Date de ieșire == În fişierul gateout.txt se vor afla răspunsurile la întrebările primite, în ordinea în care sunt adresate. Fiecare răspuns ocupă o linie și este format dintr-un singur caracter ce reprezintă litera pe care este setat runix-ul cu numărul dat în întrebare. == Restricții și precizări == *1 ≤ N,M ≤ 200.000 *1≤r≤N *-100000 ≤ p ≤ 100.000, p≠0 *Pentru teste în valoare de 20 de puncte, N*M ≤ 25.000.000 == Exemplu 1 == ; gatein.txt : 8 3 8 : 1 3 : 2 4 1 : 3 8 : 1 5 : 2 2 2 : 3 1 : 2 5 -1 : 3 5 ; gateout.txt : c : c : b <br> == Exemplu 2 == ; gatein.txt : 6 2 6 : 1 4 : 2 2 1 : 3 6 : 1 3 : 2 5 -1 ; gateout.txt : b : a : b <br> == Rezolvare == <syntaxhighlight lang="python" line> #0615 - Gate def open_gate(N, L, M, actions): if not (1 <= N <= 200000 and 1 <= M <= 200000 and 1 <= L <= 26): print("Fals") return alphabet = 'abcdefghijklmnopqrstuvwxyz'[:L] runix_config = {i: alphabet[i % L] for i in range(1, N + 1)} answers = [] for action in actions: t, r, p = action if t == 1: # Deplasare și separare left_group = {i: runix_config[i] for i in range(1, r)} right_group = {i: runix_config[i] for i in range(r, N + 1)} runix_config = {**right_group, **left_group} elif t == 2: # Schimbare de pas current_letter = runix_config[r] new_index = (alphabet.index(current_letter) + p) % L runix_config[r] = alphabet[new_index] answers = [runix_config[r] for r in range(1, N + 1)] # Scrierea rezultatului în fișierul de ieșire with open("gateout.txt", "w") as outfile: for answer in answers: outfile.write(answer + '\n') # Citirea datelor de intrare with open("gatein.txt", "r") as infile: N, L, M = map(int, infile.readline().split()) actions = [list(map(int, line.split())) for line in infile] # Verificarea restricțiilor și calculul rezultatului open_gate(N, L, M, actions) </syntaxhighlight> == Explicatie == Starea iniţială a sistemului : abcabcab 1 3 - abc abcab <br> 2 4 1 - abc bcabc <br> 3 8 - abc bcabc <br> 1 5 - abc bc abc <br> 2 2 2 - cab bc abc <br> 3 1 - cab bc abc <br> 2 5 -1 - cab ab abc <br> 3 5 - cab ab abc
Summary:
Please note that all contributions to Bitnami MediaWiki may be edited, altered, or removed by other contributors. If you do not want your writing to be edited mercilessly, then do not submit it here.
You are also promising us that you wrote this yourself, or copied it from a public domain or similar free resource (see
Bitnami MediaWiki:Copyrights
for details).
Do not submit copyrighted work without permission!
Cancel
Editing help
(opens in new window)
Toggle limited content width