Lista de probleme 2

De câte ori trebuie să transmită un mesaj URGENT!!! directorul şcolii noastre are o mare problemă. Indiferent de canalul de comunicare pe care îl foloseşte (e-mail, what’s app, site-ul şcolii etc.), întotdeauna vor exista elevi la care mesajul nu ajunge sau nu ajunge în timp util. După multe încercări, a decis să numeroteze cei n elevi din şcoală cu numere distincte de la 1 la n şi să studieze relaţiile de comunicare dintre elevi. Apoi, bazându-se pe aceste relaţii de comunicare, să aleagă un număr minim de elevi-răspândaci cărora să le transmită mesajul direct, urmând ca aceasta să fie transmis la absolut toţi elevii, prin relaţiile de comunicare dintre aceştia. Să se scrie un program care, cunoscând relaţiile de comunicare dintre elevi, determină numărul minim de răspândaci necesari pentru ca mesajul directorului să ajungă în timp util la toţi elevii din şcoală.

Să considerăm n zaruri, numerotate de la 1 la n. La aruncarea celor n zaruri obţinem o succesiune de n numere naturale cuprinse între 1 și 6. Suma unei aruncări va fi egală cu suma numerelor obţinute. Câte aruncări de n zaruri au suma cuprinsă între st și dr? Scrieți un program ce calculează răspunsul pentru mai multe întrebări de forma celei de mai sus. Pentru că numărul de aruncări poate fi destul de mare, calculați răspunsul modulo 1.000.003.