Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2020-03-08 22:27:30.
Revizia anterioară   Revizia următoare  

 

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 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.inps.out
This is some
text written on
multiple lines.
This is another
text written on
multiple lines.

Explicaţie

...

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?