Lista de probleme 888

Se citește un cuvânt S format din litere mici distincte ale alfabetului englez și un număr m. Afișați în ordine lexicografică toate cuvintele formate din cel mult m litere ordonate alfabetic din S, în care nu există consoane alăturate și încep cu vocală.

În țara Zoomba trăiesc K prieteni, fiecare în localități diferite. În această țară se găsesc N orașe, oricare două fiind legate prin cel mult o șosea bidirecțională. Deoarece nu s-au mai întâlnit de mult, cei K prieteni s-au hotărât să se reîntâlnească într-un oraș. Fiecare are câte o mașină cu număr nelimitat de locuri. Pentru a trece de la un oraș la altul, o mașină consumă 1 litru de benzină.

Știind că odată ce au ajuns în același oraș 2 sau mai mulți prieteni, aceștia iși pot continua drumul cu o singură mașină, să se determine consumul minim de benzină pentru ca aceștia să ajungă în orașul Z.

Între timp, într-un univers paralel…

Ștefan Ghe este creatorul site-ului renumit de probleme de algoritmică InfoZona. Din păcate, verișorul său diabolic, Feștan Ț, punându-și în practică skill-urile de hacker nebunatic, a spart site-ul InfoZona și îl va da înapoi domnului Ștefan doar dacă reușeste să rezolve următoarea problemă:

Se dă un șir A, indexat de la 1, de N numere naturale nenule, reprezentând un raft de sandale. Vom defini funcția \( F(l,r) = ( \sum_{i=l}^{r} A[i] )^3 \) ca fiind costul pentru a cumpara sandalele din secvența [l, r] laolaltă, toate în același coș de cumpărături. Feștan Ț are K coșuri de cumpărături la dispoziție și dorește să afle care este prețul minim pe care poate cumpăra toate cele N sandale, folosind coșurile de cumpărături de care dispune.

Ajutați-l pe domnul Ștefan Ghe să-și recupereze site-ul rezolvând această problemă și vă va face cinste cu o bere și cinci cămile!

Ionuț tocmai a terminat liceul și susține examenul de admitere la facultate. Știind că s-a pregătit foarte bine pentru examen, el dorește să își anunțe reușita după examen printr-o postare pe Facebook.
Ionuț cunoaște n utilizatori reprezentați de numerele de la 1 la n, între care există m relații de prietenie de forma i j, unde i și j sunt utilizatori, iar n și m sunt numere naturale nenule. Un utilizator nu poate fi prieten cu el însuși, iar o relație de prietenie între doi utilizatori ne spune că fiecare dintre ei este prieten cu celălalt.

Întrucât dorește ca postarea lui să fie cât mai răspândită, Ionuț vrea să afle care sunt utilizatorii cei mai bine conectați din mulțimea sa de cunoscuți, pentru ca eventual să le ceară prietenia. Pentru aceasta, Ionuț trebuie să găsească cea mai mare submulțime de utilizatori cunoscuți, în care fiecare utilizator din această submulțime are cel puțin k prieteni aflați la rândul lor în submulțime, unde k este un număr natural nenul.

Ajutați-l pe Ionuț să se determine și să se afișeze, printr-o soluție de complexitate timp cât mai bună, în funcție de datele de intrare, membrii celei mai mari submulțimi de utilizatori, cu proprietatea că fiecare utilizator din această submulțime are cel puțin k prieteni aflați la rândul lor în submulțime.

Se citesc de la tastatură un cuvânt s format din litere mici distincte și un număr natural n. Să se afișeze pe ecran toate cuvintele care se pot obține din s eliminând exact n litere.

Să se genereze toate şirurile strict crescătoare de n numere naturale nenule cel mult egale cu S și cu proprietatea că oricare ar fi a şi b două numere dintr-un astfel de şir a-b divide a+b.

Oricare cuvânt care nu este de tip palindrom se poate separa în mai multe părți care, fiecare, să fie de tip palindrom. Care este numărul minim de secvențe de tip palindrom în care se poate separa un cuvânt și care este cea mai mare lungime a unei asemenea secvențe?

Se consideră un şir a cu n numere naturale distincte: a1, a2,..., an.

Să se genereze în ordine lexicografică toate subşirurile vârf ale şirului a, de lungime k≥3.

Orice șir de caractere poate fi descompus în palindromuri într-unul sau mai multe moduri. Dându-se un șir de caractere format numai din litere mici, să se determine numărul de moduri de a descompune șirul în palindromuri.

Se consideră o expresie compusă din operatorii +, -, * și cifre. La expresie se pot adăuga paranteze astfel încât valoarea calculată să fie maximă.