| 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 trecuta, 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 solutia 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 probleme), K.
Pe fiecare dintre urmatoarele K linii se 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 ≤ 100.000
- Atat studentii, cat si problemele sunt indexate incepand cu 1
- Daca exista mai multe distribuiri ale problemelor, corespunzatoare solutiei optime, se poate afisa oricare dintre ele.
- Pentru teste in valoare de 30 puncte, 1 ≤ N ≤ 2.000
Exemplu
| ps.in | ps.out |
|---|---|
| 5 5 8 1 1 1 2 2 1 2 3 3 2 3 3 4 5 5 4 | 1 1 3 2 5 4 |
| 5 5 6 1 1 1 2 2 3 3 3 4 5 5 4 | 2 1 1 3 5 4 |
