Fişierul intrare/ieşire:canibali.in, canibali.outSursăLot Sovata 2014 Seniori Baraj 1
AutorDragos OpricaAdăugată dedariusdariusMarian Darius dariusdarius
Timp execuţie pe test0.25 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Canibali

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] şi Y[i] ≥ Y[j] şi 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şierului 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

Fişierului de ieşire canibali.out conţine 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.incanibali.outExplicatie
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 îlmă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 sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?