Fişierul intrare/ieşire:ps.in, ps.outSursăFMI No Stress 9
AutorBogdan Ciobanu, Bogdan IordacheAdăugată defminostress9FMI No Stress 9 fminostress9
Timp execuţie pe test0.5 secLimită de memorie524288 kbytes
Scorul tăuN/ADificultateN/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.inps.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
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?