Lista de probleme 3

Presupunem că avem două cutii notate A și B. Cutia A conține N bile numerotate cu numerele naturale distincte: 0, 1, 2, . . . , N − 1. Cutia B este goală. Spunem că o bilă dintr-o cutie este bila specială a acestei cutii dacă numărul X cu care este numerotată această bilă este egal cu media aritmetică a numerelor celorlalte bile din cutie. La un moment dat, cineva mută bila cu numărul K din cutia A în cutia B. Vi se cere să alegeți alte K bile, din cutia A, pe care să le mutați în cutia B astfel încât cutia B să conțină K + 1 bile, iar bila cu numărul K să fie bila specială a cutiei B.

Se consideră un șir cu N elemente numere întregi. Definim următoarele noțiuni:

• secvență în șir = elemente situate pe poziții consecutive în șir
• lungimea unei secvențe = numărul de elemente care o formează
• suma unei secvențe = suma elementelor care o formează
• secvența nebanală = secvența de lungime cel puțin egală cu 2
• N-secvență = secvență a cărei sumă este divizibilă cu N (secvența poate fi și banală)
• N-secvență nebanală = secvență nebanală a cărei sumă este divizibilă cu N.

Scrieți un program care să citească numărul natural N și apoi șirul de N elemente. Programul determină:

1. numărul de N-secvențe nebanale, din șir;
2. cea mai mare lungime a unei N-secvențe din șir;
3. cea mai mare sumă a unei N-secvențe din șir.

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ă.