Un fermier trebuie sa transporte cu trenul o cireada formata din N vaci. Pe
fiecare animal este pictat un numar de ordine, cuprins intre 1 si N, astfel
incat oricare doua animale au numere distincte.
Trenul este format din K vagoane si, evident, o locomotiva care este irelevanta
pentru problema noastra. In fiecare vagon pot fi incarcate cel mult M vaci.
Vacile stau cuminti la coada, in ordinea crescatoare a numerelor lor de ordine
(vaca numerotata cu 1 se va urca in tren prima). La un moment dat sunt incarcate
intr-un vagon un numar oarecare de vaci (care nu depaseste M), de la inceputul
cozii, dupa care vagonul este incuiat, deci nu se mai pot incarca ulterior alte
vaci in vagonul respectiv.
Se stie ca exista perechi de animale care se antipatizeaza si daca sunt incarcate
in acelasi vagon se vor bate, iar cel mai puternic il va omori pe celalalt.
Se stie de asemenea ca exista perechi de animale care se simpatizeaza si daca
animalul mai slab este atacat, cel mai puternic il va proteja.
Dupa ce vagonul se inchide animalele incep sa se atace. Transportul dureaza
suficient de mult, astfel incat toate conflictele sa se epuizeze.
Cerinta
Scrieti un program care sa determine o modalitate de incarcare a animalelor
in vagoane, astfel incat sa ajunga la destinatie un numar maxim de animale vii.
Date de intrare
Fisierul de intrare transport.in contine pe prima linie numerele naturale N K M, separate prin spatii. Pe cea de a doua linie numarul natural D, care reprezinta
numarul de perechi de animale care se antipatizeaza. Pe fiecare dintre urmatoarele D linii exista 3 numere naturale distincte A B C, cu semnificatia: perechea de vaci (A, B) se antipatizeaza, iar perechea de vaci (C, B) se simpatizeaza. In ambele perechi animalul al doilea
(B) este cel mai slab. Cel mai puternic animal dintr-o pereche de animale care se antipatizeaza nu
poate sa apara intr-o alta astfel de pereche ca al doilea animal (adica cel
mai slab). Animalul slab dintr-o pereche de animale care se simpatizeaza are
exact un protector mai puternic (adica C este unic determinat de A si B).
Date de iesire
Fisierul de iesire transport.out
contine pe prima linie numarul de animale ajunse vii la destinatie (maxim posibil).
Restrictii
1 <= N, K <= 1000
1 <= M <= 20
Exemple
transport.in
transport.out
5 2 3
2
1 2 3
1 3 2
5
transport.in
transport.out
8 3 3
6
4 6 2
5 6 4
7 8 6
5 3 6
7 6 5
2 3 4
5
prof. Emanuela Cerchez
Liceul de Informatica "Grigore Moisil" Iasi