== include(page="template/taskheader" task_id="mostenire") ==
Poveste și cerință...
Regele Rufus dorește să stabilească moștenitorul averii sale, adică să ofere parola de la seif celui mai deștept dintre fiii săi. Inițial, regele a avut parola *X* formată din *N* cifre nenule și un cod cheie *Q* (număr natural cu exact 9 cifre, distincte, toate nenule). În fiecare an din cei *K* ani de domnie, folosind codul cheie *Q*, Rufus a modificat câte o secvență de cifre din parolă ajungând la parola finală *P*.
Pentru fiecare secvență se cunoaște poziția *S* a primei cifre din secvență și poziția *D* a ultimei cifre din secvență. Astfel, secvența este formată din cifrele situate pe pozițiile *S*, [*S*]+1, [*S*]+2,..., *D* în parola *X*. Modificarea unei secvențe din *X* constă în înlocuirea fiecărei apariții a cifrei 1 cu prima cifră a lui *Q*, apoi a fiecărei apariții a cifrei 2 cu a doua cifră a lui *Q*, ..., a fiecărei apariții a cifrei 9 cu ultima cifră a lui *Q*.
Pentru a decide moștenitorul, regele le dă fiilor parola finală *P*, codul cheie *Q*, numărul *K* de ani de domnie si cele *K* secvențe de cifre care au fost modificate și le cere să găsescă: parola inițială *X*, poziția minimă *Z* din parola *X* care a apărut în cele mai multe secvențe dintre cele modificate de rege de-a lungul celor *K* ani de domnie și cifrele distincte care au ocupat poziția *Z* în cei *K* ani.
h2. Cerințe
Scrieți un program care citește numerele *Q*, *N*, *K*, cele *N* cifre ale parolei finale *P* și cele *K* perechi de poziții *S* și *D*, și care rezolvă următoarele două cerințe:
# determină parola inițială *X*;
# determină poziția minimă *Z* și cifrele distincte care au ocupat această poziție în cei *K* ani de domnie.
h2. Date de intrare
Fișierul de intrare $mostenire.in$ ...
Fișierul de intrare $mostenire.in$ conține pe prima linie un număr natural *C* reprezentând cerința din problemă care trebuie rezolvată (1 sau 2). A doua linie din fișier conține cele trei numere naturale *Q*, *N* și *K*, separate prin câte un spațiu. A treia linie din fisier conține cele *N* cifre ale parolei finale *P*, separate prin câte un spațiu. Fiecare linie dintre următoarele *K*, conține câte două numere naturale *S* și *D*, separate printr-un singur spațiu, reprezentând câte o pereche de poziții.
h2. Date de ieșire
În fișierul de ieșire $mostenire.out$ ...
Dacă [*C*]=1, fișierul de ieșire $mostenire.out$ va conține pe prima linie cele *N* cifre ale parolei initiale *X*, separate prin câte un spațiu, în ordinea în care apar în *X*, reprezentând răspunsul la cerința 1.
Dacă [*C*]=2, fișierul de ieșire $mostenire.out$ va conține pe prima linie numărul natural *Z*, iar pe a doua linie cifrele distincte care au apărut pe poziția minimă *Z*, reprezentând răspunsul la cerința 2. Acestea vor fi afișate în ordine crescătoare, separate prin câte un spațiu.
h2. Restricții
* $... ≤ ... ≤ ...$
* 1 ≤ *N* ≤ 10 000
* numărul natural *Q* este format din exact 9 cifre, distincte și nenule
* pozițiile cifrelor din parola *X* sunt numerotate cu numerele distincte consecutive 1, 2, ..., *N*
* 1 ≤ *K* ≤ 100
* pentru toate perechile de poziții modificate de rege: *S* ≤ *D*
* cel puțin o cifră din parola *X* va fi înlocuită
* pentru rezolvarea corectă a cerinței 1 se acordă 50 de puncte
* pentru rezolvarea corectă a cerinței 2 se acordă 50 de puncte.
h2. Exemplu
table(example).
|_. mostenire.in |_. mostenire.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
table(example).
|_. mostenire.in |_. mostenire.out |_. Explicații |
| 1
712534698 12 4
1 4 7 1 3 4 7 1 4 8 1 8
2 4
6 11
3 9
1 7
| 2 7 3 5 4 1 3 3 7 9 2 8
| Cerința este 1, [*N*]=12, [*K*]=4.
*K* *S* *D* *Parola*
4 1 7 *1 4 7 1 3 4 7* 1 4 8 1 8
3 3 9 2 6 *1 2 5 6 1 1 4* 8 1 8
2 6 11 2 6 2 3 4 *7 2 2 6 8 1* 8
1 2 4 2 *6 2 3* 4 1 3 3 7 9 2 8
X initial 2 7 3 5 4 1 3 3 7 9 2 8
|
| 2
712534698 12 4
1 4 7 1 3 4 7 1 4 8 1 8
2 4
6 11
3 9
1 7
| 3
1 2 3 7
| Cerința este 2, [*N*]=12, [*K*]=4.
*P* = (1 4 7 1 3 4 7 1 4 8 1 8)
Pozițiile care au apărut în cele mai multe
secvențe sunt: 3,4,6,7 => [*Z*]=3, iar cifrele
distincte care au ocupat succesiv această
pozitie sunt 3,2,1,7. Aceste cifre se vor scrie
în fișier în ordine crescătoare
|
h3. Explicație
...
== include(page="template/taskfooter" task_id="mostenire") ==
