Fișierul intrare/ieșire canibali.in, canibali.out Sursă Lot Sovata 2014
Autor Dragoș Oprică Adăugată de avatar spatarel Spatarel Dan-Constantin spatarel
Timp de execuție pe test 0.5 sec Limită de memorie 65536 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip fullstea de rating de tip fullstea de rating de tip fullstea de rating de tip full
open book Poți vedea testele pentru această problemă accesând atașamentele .

Canibali (lot liceu)

Pe o insulă se află N canibali. Pentru fiecare canibal i se cunosc 4 factori determinanți: X[i] – viteza canibalului, Y[i] – rezistența canibalului, Z[i] – forța canibalului și T[i] – valoarea canibalului.

Se știe că un canibal i poate să mănânce un canibal j dacă și numai dacă:

X[i] ≥ X[j], Y[i] ≥ Y[j], Z[i] ≥ Z[j] și T[i] ≥ T[j].

Adevărul este că foamea e mare și neavând nimic de mâncare, canibalii încep să se mănânce între ei. ținând cont de religia lor, un canibal nu poate să mănânce mai mult de doi canibali. știind toate acestea, voi trebuie să determinați care este numărul minim de canibali care pot rămâne în viață după Marele Festin.

Date de intrare

Fișierul de intrare canibali.in conține pe prima linie un număr natural N, reprezentând numărul de canibali. Pe următoarele N linii se află câte 4 numere separate prin spații: X[i], Y[i], Z[i] și T[i], reprezentând viteza, rezistența, forța și valoarea celor N canibali.

Date de ieșire

În fișierul de ieșire canibali.out se va găsi un singur număr, reprezentând numărul minim de canibali care pot rămâne în viață.

Restricții

  • 3 ≤ N ≤ 2048
  • 0 ≤ X[i], Y[i], Z[i], T[i] ≤ 217
  • Din motive etice și filozofice, un canibal nu poate să se mănânce pe el înșuși.

Exemplu

canibali.in canibali.out Explicație
3
1 2 3 4
2 1 3 4
1 2 4 3
3
Niciunul din cei 3 canibali nu poate să mănânce niciunul din ceilalți 2,
deci rămân toți 3 în viață.
3
1 2 3 4
1 2 3 4
1 2 3 4
1
Fiecare din cei 3 canibali poate să mănânce oricare din ceilalți 2,
așa că o soluție pentru care se obține răspunsul corect este: canibalul 2
îl mănâncă pe canibalul 3, iar canibalul 1îl mănâncă pe canibalul 2.
O altă soluție corectă este: canibalul 1 îimănâncă pe canibalul 2
și pe canibalul 3.
4
1 2 3 4
1 2 3 4
1 2 3 4
2 3 4 5
1
O soluție corectă este: canibalul 2 îl mănâncă pe canibalul 3, canibalul 1
îl mănâncă pe canibalul 2, iar canibalul 4 îl mănâncă pe canibalul 1.
O soluție greșită este: canibalul 4 îi mănâncă pe canibalul 1 și
pe canibalul 2, rămânând 2 canibali în viață.

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 2 categorii