Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | ps.in, ps.out | Sursă | FMI No Stress 9 |
| Autor | Bogdan Ciobanu, Bogdan Iordache | Adăugată de |  FMI No Stress 9 •fminostress9 |
| Timp execuţie pe test | 0.5 sec | Limită de memorie | 524288 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Ps
Chiar inainte de sesiunea anterioara, cei N studenti din grupa 236 trebuiau sa faca fata unui nou obstacol: tema la Probabilitati si Statistica. Ca orice alta tema, rezolvarea acesteia a fost amanata pana in ultima zi. Astfel, chat-ul de WhatsApp al grupei a "explodat", toti voiau sa termine tema cat mai repede si, evident, cu cat mai putin efort depus. Cumuland informatiile despre temele fiecarui student, ei au observat urmatoarele:
* Fiecarui student i-a fost data o tema "personalizata"
* Exista in total M probleme distincte selectate dintr-o culegere (fara raspunsuri la final, din pacate)
* Fiecare problema din cele M se afla in cel putin o tema a unui student
* Orice problema din cele M se afla in cel mult doua teme
* Fiecare tema contine cel putin o problema si cel mult doua probleme
Un elev poate rezolva acum orice problema care se afla in tema lui, dupa ce o rezolva, va incarca rezolvarea in chat-ul de WhatsApp, iar orice alt student care avea acea problema in tema nu o va mai rezolva.
Cerinta
Avand la dispozitie informatii despre temele tuturor studentilor, sa se determine o atribuire optima intre fiecare problema si ce student o va rezolva, astfel incat sa se minimizeze numarul maxim de probleme pe care le rezolva un student.
Date de intrare
Fişierul de intrare ps.in contine pe prima linie trei numere intregi, N (numarul de studenti), M (numarul de problme), K.
Pe fiecare din urmatoarele K linii vor gasi cate doua numere intregi, separate printr-un spatiu, s si p, reprezentand o asociere de tipul: tema studentului cu numarul s contine problema p.
Date de ieşire
În fişierul de ieşire ps.out se va afisa pe primul rand valoarea minima a numarului maxim de probleme pe care le va rezolva un student.
Pe cea de-a doua linie se vor afisa M numere separate prin cate un spatiu. Al i-lea numar reprezinta indicele studentului care rezolva problema i, in cazul optim.
Restricţii
- 1 ≤ N, M ≤ 100.000
- Daca exista mai multe distributii ale problemelor, corespunzatoare solutiei optime, se poate afisa oricare dintre ele.
Exemplu
| ps.in | ps.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicaţie
...
