Lista de probleme 3

RAU-Gigel își amintește cu nostalgie de momentele sale de început într-ale programării, când mai făcea și stângăcii cum ar fi să declare un nume de tipul int…. așa a apărut următoarea problemă:

Să ne imaginăm harta politică a lumii viitorului, împărțită în țări ale căror nume sunt de fapt numere naturale nenule. Între ele există anumite relații: două țări sunt înfrățite dacă au în compunerea numelui lor aceleași cifre (nu contează numărul de apariții), în timp ce două țări se află în conflict dacă nu au nicio cifră comună în numele lor.

Interesat de politică, RAU-Gigel ar vrea să afle câteva informații: câte țări sunt izolate din punct de vedere politic, în sensul că nu sunt înfrățite cu nicio altă țară? Pentru fiecare țară dintr-o listă de țări preferate să se afle: cu câte țări este înfrățită și cu câte în conflict?

Ajutați-l pe RAU-Gigel să afle răspunsul la întrebările sale !

Prietenii lui RAU-Gigel vor să-i facă o surpriză de ziua lui! Pentru aceasta, ei trebuie să se întâlnească într-un singur loc pentru a se putea organiza mai eficient. Poți să-i ajuți cu cunoștințele tale informatice să rezolve această problemă?

RAU-Gigel se pregătește pentru admiterea la facultate. Curios din fire, el împrumută niște cursuri de la un prieten student, de unde află despre limbajele formale, gramatici, automate finite, expresii regulate și multe alte lucruri interesante. Găsește acolo și o problemă:

Se consideră un alfabet X format din N simboluri (diferite două câte două). Pe mulțimea X este definită o relație de ordine totală (să o numim lexicografică) astfel: orice două elemente a și b alegem din X (a diferit de b), avem fie a<b, fie b<a. Câte cuvinte se pot forma cu simboluri din alfabetul X astfel încât simbolurile prezente în cuvânt să fie în ordine strict crescătoare (de la stânga spre dreapta) și să nu existe în cuvânt două simboluri consecutive lexicografic?