Fişierul intrare/ieşire:admitere.in, admitere.outSursăOJI 2017, clasa a 9-a
AutorMihai CalanceaAdăugată debciobanuBogdan Ciobanu bciobanu
Timp execuţie pe test0.15 secLimită de memorie36864 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Admitere

Să ne imaginăm faptul că la un anumit liceu există doar două clase per generaţie: una de Real şi una de Uman. În prezent au loc înscrierile pentru clasa a IX-a. Cele două clase au fiecare câte M locuri disponibile, atât la Real, cât şi la Uman. Dacă lista de elevi înscrişi la o anumită clasă conţine mai mult de M elevi, vor fi admişi acei M elevi care au notele cele mai mari. Ambele clase au deja M elevi înscrişi, iar pentru fiecare se ştie nota cu care a fost înscris la clasa respectivă.

Mai există însă N elevi, singurii încă neînscrişi, care sunt privilegiaţi în acest proces (fiindcă au terminat gimnaziul la acest liceu). Privilegiul lor constă în următorul fapt: ei se pot înscrie acum, după ce înscrierile publice au fost încheiate, şi se cunosc notele de înscriere la ambele clase. Fiecare din cei N elevi are câte două note: nota cu care ar fi înscris la Real şi nota cu care ar fi înscris la Uman (acestea pot fi diferite, deoarece examenele de admitere de la cele două clase diferă). Fiecare din cei N elevi va alege să se înscrie în maxim o clasă. Ei îşi vor coordona alegerile astfel încât să maximizeze numărul de elevi admişi. Deoarece calculele devin destul de complicate, aceştia s-ar putea folosi de ajutorul vostru. Ei doresc răspunsul la următoarele două întrebări:

Cerinţe

  1. Care este numărul maxim de elevi privilegiaţi care pot fi admişi dacă se pune restricţia suplimentară ca toţi elevii privilegiaţi admişi să fie admişi la aceeaşi clasă?
  2. Care este numărul maxim de elevi privilegiaţi care pot fi admişi dacă aceştia se pot înscrie la clase diferite?

Date de intrare

Fişierul de intrare admitere.in conţine pe primul rând o valoare egală cu 1 sau 2, reprezentând cerinţa ce urmează a fi rezolvată. Următoarea linie conţine cele două numere N şi M. Pe al treilea rând se află M numere, separate prin câte un spaţiu, reprezentând notele cu care au fost înscrişi elevii care formează momentan clasa de Real. Pe al patrulea rând se află M numere, separate prin câte un spaţiu, reprezentând notele cu care au fost înscrişi elevii care formează momentan clasa de Uman. Următoarele N linii vor conţine câte o pereche de numere R[i], U[i], separate prin câte un spaţiu, reprezentând nota cu care al i-lea elev privilegiat s-ar înscrie la clasa de Real, respectiv la clasa de Uman.

Date de ieşire

Fişierul de ieşire admitere.out va conţine pe prima linie valoarea MAX: numărul maxim de elevi privilegiaţi admişi. A doua linie va conţine un şir de N caractere din mulţimea {'R', 'U', 'X'}, care va descrie scenariul optim. Dacă al i-lea elev va fi înscris la Real, al i-lea caracter va fi egal cu 'R'. Dacă al i-lea elev va fi înscris la Uman, al i-lea caracter va fi egal cu 'U'. Dacă acesta nu va fi înscris nicăieri, al i-lea caracter va fi egal cu 'X'. 
Deoarece elevii nu vor să depună efort inutil, un elev privilegiat care nu va fi admis în scenariul optim nu se va înscrie la nicio clasă. Cu alte cuvinte, pentru ca scenariul descris să fie considerat corect este necesar ca exact MAX caractere din şir să fie diferite de 'X'.

Restricţii

  • 1 ≤ N, M ≤ 2000
  • Pentru cerinţa (2), teste în valoare totală de 45 de puncte vor avea 1 ≤ N, M ≤ 150.
  • Toate cele N + M note pentru clasa de Real sunt distincte două câte două. Acelaşi lucru este valabil şi în cazul notelor pentru clasa de Uman.
  • Toate notele sunt numere naturale din intervalul [1, 4000].
  • Notele elevilor deja înscrişi de la clasa de Real, respectiv Uman vor fi date în ordine crescătoare.
  • În cazul în care există mai multe soluţii corecte, este acceptată oricare dintre acestea.

Exemplu

admitere.inadmitere.outExplicaţie
1
2 3
2 4 6
6 7 8
3 5
12 14
1
XR
Nu este posibil ca ambii elevi să fie admişi la aceeaşi clasă.
Există mai multe soluţii în care un singur elev este admis: XR, XU, RX.
Oricare din acestea este corectă.
2
2 3
2 4 6
6 7 8
3 5
12 14
2
RU
Deoarece acum rezolvăm cerinţa (2), ne este permis să înscriem elevii la clase diferite.
Există o soluţie în care ambii elevi sunt admişi, iar aceasta este unică:
cea în care elevul 1 este înscris la Real (el nu putea fi admis la Uman indiferent de decizia celui de-al doilea elev),
iar cel de-al doilea elev este înscris la Uman.
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?