Lista de probleme 2

Filtrare

Dificultate

Operații intrare/ieșire

Etichete

#2109 Dineu

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.

Majoritatea copiilor sunt sociabili și relaționează ușor cu cei de vârsta lor dar sunt și copii mai timizi sau mai puțin atrași de activitățile de grup. În urma studierii comportamentului unui eșantion de n copii, s-a stabilit, pentru fiecare doi copii dacă relaționează sau nu. Pentru serbarea de sfârșit de an, s-a propus realizarea unei scenete și este necesară selectarea unei grupe cât mai numeroase de micuți dar fără a depăși k, numărul maxim de personaje. Rolurile presupun interacțiunea fiecărui copil selectat cu toți ceilalți mici actori care joacă în scenetă. Să se determine cel mai mare număr de copii care pot fi implicați în serbare, știind ca fiecare dintre aceștia trebuie să relaționeze cu toți ceilalți copii din scenetă.