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şiL = 3, sistemul are configuraţia iniţială:abcabcab - pentru
N = 11şiL = 4, sistemul are configuraţia iniţială:abcdabcdabc - pentru
N = 14şiL = 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:
1. 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).
2. 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ă.
3. 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 gate.in 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 gate.out 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.0001≤r≤N-100000 ≤ p ≤ 100.000, p≠0- Pentru teste în valoare de
20de puncte,N*M ≤ 25.000.000
Exemplu
gate.in
8 3 8 1 3 2 4 1 3 8 1 5 2 2 2 3 1 2 5 -1 3 5
gate.out
c c b
Explicație
Starea iniţială a sistemului : abcabcab
1 3 - abc abcab 2 4 1 - abc bcabc 3 8 - abc bcabc 1 5 - abc bc abc 2 2 2 - cab bc abc 3 1 - cab bc abc 2 5 -1 - cab ab abc 3 5 - cab ab abc
Cum e corect?
cout < "As la info";
cout << "As la info";
cout >> "As la info";
Felicitări! Poți mai mult?
Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.
Greșit, dar nu-i bai!
Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.
Rezolvare
Iată rezolvarea de 100 de puncte pentru problema Gate:
#include <cstdio>
#include <algorithm>
#include <set>
#include <string>
#include <cassert>
using namespace std;
struct Segment {
public:
int poz, rune, lg;
};
Segment THESEG;
bool operator< (const Segment A, const Segment B) {
return A.poz > B.poz;
}
int N, L, M;
set <Segment> segs;
void solve1();
void solve2();
void solve3();
int main() {
freopen("gate.in", "r", stdin);
freopen("gate.out", "w", stdout);
int i, t;
scanf("%d %d %d", &N, &L, &M);
THESEG.poz = 1; THESEG.rune = 0; THESEG.lg = N;
segs.insert(THESEG);
for (i = 0; i < M; ++i) {
scanf("%d", &t);
switch (t) {
case 1: {
solve1(); break;
}
case 2: {
solve2(); break;
}
default:{
solve3(); break;
}
}
}
return 0;
}
int getChar(Segment S, int poz) {
return (S.rune + (poz - S.poz)) % L;
}
void solve1() {
set <Segment> ::iterator it;
Segment nw, old;
int poz;
scanf("%d", &poz);
THESEG.poz = poz;
it = segs.lower_bound(THESEG);
nw = old = *it;
segs.erase(it);
if (poz < old.poz + old.lg - 1) {
nw.poz = poz + 1;
nw.lg = old.poz + old.lg - 1 - poz;
nw.rune = (getChar(old, poz) + 1) % L;
segs.insert(nw);
old.lg = poz - old.poz + 1;
}
segs.insert(old);
}
void solve2() {
set <Segment> ::iterator it;
Segment old;
int poz, p;
scanf("%d %d", &poz, &p);
THESEG.poz = poz;
it = segs.lower_bound(THESEG);
old = *it;
segs.erase(it);
if (p < 0) {
p = abs(p);
p %= L;
p = -p;
}
old.rune += p + L;
old.rune %= L;
segs.insert(old);
}
void solve3() {
set <Segment> ::iterator it;
Segment old;
int poz;
scanf("%d", &poz);
THESEG.poz = poz;
it = segs.lower_bound(THESEG);
old = *it;
printf("%c\n", 'a' + getChar(old, poz));
}Atenție
Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa 
.
Rezolvarea problemei #615 Gate
Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #615 Gate de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.
Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!