Lista de probleme 24

Valoarea unei litere este dată de numărul ei de ordine în alfabet (A are valoarea 1, B are valoarea 2, C are valoarea 3, etc.). Un text special este format din una sau mai multe litere mari ale alfabetului englez și nu conține alte tipuri de caractere. Valoarea unui text special o definim ca fiind egală cu suma valorilor literelor care îl compun.

Un text special poate fi transcris într-o formă restrânsă prin utilizarea perechilor de paranteze și a numerelor naturale.

Transcrierea în formă restrânsă a unui text special se realizează prin înlocuirea fiecărei secvențe care are apariții consecutive în text cu secvența scrisă între o pereche de paranteze rotunde urmată apoi de numărul de repetiții.

Dacă, după transcriere, textul în formă restrânsă conține secvențe care au apariții consecutive în text atunci și acesta se va transcrie în formă restrânsă.

Dacă textul special nu conține nicio secvență cu apariții consecutive în text, atunci forma restrânsă a textului este identică cu forma inițială.

Scrieți un program care citește un șir de caractere S reprezentând forma restrânsă a unui text special, și apoi determină:

1. numărul literelor distincte care apar în textul special;
2. suma numerelor care apar în forma restrânsă a textului special;
3. valoarea textului special dat în forma restrânsă.

Pentru o permutare p1, p2, …, pN a numerelor de la 1 la N și o poziție K, (1 ≤ K ≤ N), notăm cu BestK numărul minim de interschimbări (a valori situate pe poziții consecutive) necesare pentru a se obține o permutare descrescătoare de la poziția 1 la poziția K și crescătoare de la poziția K la poziția N. Se dă o permutare. Se cere să se rezolve una dintre următoarele două cerințe:
1. Pentru o poziție K dată să se calculeze BestK.
2. Pentru toate pozițiile K de la 1 la N să se calculeze BestK.

Plictisit de filantropie și produs cipuri, William Poartă și-a găsit o nouă pasiune: anchetele epidemiologice. Astfel, el s-a gândit să cerceteze răspândirea unui virus din trecut asupra omenirii, formată din N persoane. William știe pentru fiecare om starea sa finală (infectat sau neinfectat), însă nu știe care dintre oameni au fost infectați inițial, și care au fost infectați de la alte persoane. Acum William își pune următoarele întrebări:
1. Pentru fiecare om, poate acesta să fie unul dintre cei infectați inițial?
2. Pentru fiecare om, poate acesta să fie unul dintre cei neinfectați inițial?

Se dau N cuvinte formate doar din primele K litere mici ale alfabetului englez și un șir xi de M numere naturale. Trebuie să se formeze M cuvinte astfel încât oricare cuvânt i (1 ≤ i ≤ M) să respecte
următoarele proprietăți:

• Să aibă lungimea xi
• Să fie format doar din primele K litere mici ale alfabetului englez
• Să nu existe niciun cuvânt cuv din cele N date inițial sau din celelalte M - 1 nou formate astfel încât cuv să fie prefix al cuvântului i
• Să nu existe niciun cuvânt cuv din cele N date inițial sau din celelalte M - 1 nou formate astfel încât cuvântul i să fie prefix al lui cuv

Să se calculeze numărul de moduri de a forma M cuvinte care respectă proprietățile de mai sus. Două moduri se consideră diferite dacă există cel puțin o poziție i pentru care al i-lea cuvânt diferă. Deoarece acest număr poate fi foarte mare, se va afișa doar restul său la împărțirea cu 1.000.000.007.