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 două întrebări.
Cerința
(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 și precizări
1 ≤ N, M ≤ 2000- Teste în valoare totală de 25 de puncte vor solicita rezolvarea cerinței (1), iar restul de 65 de puncte vor solicita rezolvarea cerinței (2). Din oficiu sunt acordate 10 puncte.
- Pentru cerința (2), teste în valoare totală de 45 de puncte vor avea
1 ≤ N, M ≤ 150 - Toate cele
N + Mnote 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.
Exemplul 1:
admitere.in
1 2 3 2 4 6 6 7 8 3 5 12 14
admitere.out
1 XR
Explicație
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ă.
Exemplul 2:
admitere.in
2 2 3 2 4 6 6 7 8 3 5 12 14
admitere.out
2 RU
Explicație
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.
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 admitere:
#include <bits/stdc++.h>
using namespace std;
int main() {
ifstream cin("admitere.in");
ofstream cout("admitere.out");
int tip, n, m; cin >> tip >> n >> m;
vector<vector<int>> fixedGrades(2, vector<int> (m, 0));
vector<vector<int>> currGrades(n, vector<int> (2, 0));
for(int i = 0; i < 2; ++i)
for(int j = 0; j < m; ++j)
cin >> fixedGrades[i][j];
for(int i = 0; i < n; ++i)
cin >> currGrades[i][0] >> currGrades[i][1];
vector<vector<int>> frontAlready(2, vector<int> (n, 0));
vector<vector<int>> p(2, vector<int> (n, 0));
for(int c = 0; c < 2; ++c) {
for(int i = 0; i < n; ++i)
p[c][i] = i;
sort(p[c].begin(), p[c].end(), [&] (int a, int b) {
return currGrades[a][c] < currGrades[b][c];
});
}
for(int c = 0; c < 2; ++c)
for(int i = 0; i < n; ++i)
for(int j = 0; j < m; ++j)
if(fixedGrades[c][j] > currGrades[i][c])
frontAlready[c][i]++;
int bestAns = 0;
string bestConfig(n, 'X');
string label = "RU";
auto realityCheck = [&] (string config) -> string {
for(int c = 0; c < 2; ++c) {
int greaterFriends = 0;
for(int i = n - 1; i >= 0; --i) {
if(config[p[c][i]] != label[c])
continue;
if(greaterFriends + frontAlready[c][p[c][i]] >= m)
config[p[c][i]] = 'X';
greaterFriends++;
}
}
return config;
};
for(int c = 0; c < 2; ++c) {
string config(n, label[c]);
config = realityCheck(config);
int temp = 0;
for(int i = 0; i < n; ++i)
if(config[i] != 'X')
++temp;
if(temp > bestAns) {
bestAns = temp;
bestConfig = config;
}
}
if(tip == 1) {
cout << bestAns << "\n";
cout << bestConfig << "\n";
return 0;
}
const int REAL = 0, UMAN = 1;
for(int minFirst = 0; minFirst < n; ++minFirst) {
string config(n, 'X');
config[minFirst] = label[REAL];
int space = m - 1;
for(int i = 0; i < m; ++i)
if(fixedGrades[REAL][i] > currGrades[minFirst][REAL])
space--;
for(int i = 0; i < n; ++i) {
if(p[UMAN][i] == minFirst)
continue;
if(currGrades[p[UMAN][i]][REAL] > currGrades[minFirst][REAL] && space > 0) {
config[p[UMAN][i]] = label[REAL];
space--;
} else {
config[p[UMAN][i]] = label[UMAN];
}
}
config = realityCheck(config);
int temp = 0;
for(int i = 0; i < n; ++i)
if(config[i] != 'X')
temp++;
if(temp > bestAns) {
bestAns = temp;
bestConfig = config;
}
}
cout << bestAns << "\n";
cout << bestConfig << "\n";
} 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 #2057 admitere
Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2057 admitere 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!