Fişierul intrare/ieşire:mostenire.in, mostenire.outSursăONI 2018 clasa a 5-a
AutorFlavius BoianAdăugată defrancuCristian Francu francu
Timp execuţie pe test0.3 secLimită de memorie8192 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

Moștenire (clasa a 5-a)

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.

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:

  1. determină parola iniţială X;
  2. determină poziţia minimă Z şi cifrele distincte care au ocupat această poziţie în cei K ani de domnie.

Date de intrare

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.

Date de ieşire

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.

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: SD
  • 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.

Exemplu

mostenire.inmostenire.outExplicaţ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
Trebuie sa te autentifici pentru a trimite solutii. Click aici