Lista de probleme 12

În clasa lui Andrei sunt n elevi, codificaţi cu numerele 1, 2, …, n. Ei au fost rugaţi de către diriginta lor să propună un coleg de clasă care să devină liderul lor. Fiecare elev şi-a exprimat opţiunea scriind pe un bileţel codul său şi codul elevului ales de el pentru funcţia de şef de clasă. În acest fel diriginta a putut afla pe cine a votat fiecare elev. După studierea propunerilor venite din partea elevilor săi, diriginta lui Andrei a dorit să determine un grup cât mai numeros de elevi care s-au votat unii pe alţii. Cu alte cuvinte, pentru fiecare elev din grup să existe un membru al grupului care să-l fi votat.

Scrieţi un program care, pe baza voturilor elevilor clasei, să determine un grup cu un număr maxim de elevi pentru care voturile primite de ei provin de la elevi aparţinând aceluiaşi grup.

La un dineu participă reprezentanţii mai multor state. Fiecare reprezentant cunoaşte un număr de limbi străine. Doi reprezentanţi vor putea discuta direct dacă există cel puţin o limbă pe care o înţeleg amândoi. Organizatorii dineului doresc să existe cel puţin o masă la care să nu fie nevoie de translator, astfel oricare două persoane care stau la această masă să se înţeleagă direct.

Cunoscând N – numărul de reprezentanţi, identificăm fiecare reprezentant cu un număr natural cuprins între 1 şi N, L – numărul limbilor străine care se vorbesc la dineu (acestea sunt codificate prin numerele naturale de la 1 la L), numărul de limbi vorbite de fiecare reprezentant şi codurile acestora să se determine numărul maxim de persoane care pot sta la o masa fără translator.