Fişierul intrare/ieşire:ingamfat.in, ingamfat.outSursăCupa Dorinel 2015
AutorStefan CreastaAdăugată detudorcomanTudor Coman tudorcoman
Timp execuţie pe test5 secLimită de memorie1024 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise

Îngâmfat

Deoarece Gigel-Rămurel a făcut bine problema cash, tatăl său a decis să îi dea o parte din bani. Gigel-Rămurel a fost foarte mândru şi a început să facă pe deşteptul. A făcut acest lucru şi la şcoală, iar profesorul de informatică Evantai i-a dat o problemă grea, numită "arbore". În această problemă este vorba de arborele genealogic al lui Gigel-Rămurel: în partea stângă se află mama sa, iar în partea dreaptă se află tatăl său. Prima poziţie din arbore (Gigel-Rămurel sau rădăcina arborelui) este 1, mama sa având indicele 2 * 1 = 2, iar tatăl său având indicele 2 * 1 + 1 = 3. Mama şi tatăl lui Gigel, au şi ei o mamă şi un tată, şi astfel, dacă vom avea copilul, notat cu n, mama va avea indicele 2 * n, iar tatăl va avea indicele 2 * n + 1. Pe acest arbore vom face nişte mişcări. Astfel, vom avea denumirile S, stânga (pentru mamă) şi D, dreapta (pentru tată). De asemenea mai există şi pasul P, în care ne oprim la copil şi nu mai facem nicio mişcare de tipul S sau D. De asemenea, ca să facă problema şi mai grea, Evantai a adăugat şi pasul N, pe care putem să îl înlocuim cu paşii S, D, P. Numim valoarea drumului, ultimul număr pe care îl obţinem făcând aceste operaţii. Numim o suma drumurilor, suma totală de valori a fiecărui drum posibil, luând orice variantă (înlocuind caracterul N cu S, D sau P).
Să se determine mulţimea sumelor a şirului.

Date de intrare

Fişierul de intrare ingamfat.in conţine pe prima linie T, numărul de teste. Pe următoarele T linii se află câte un şir de caractere ce reprezintă mişcările de la fiecare test.

Date de ieşire

În fişierul de ieşire ingamfat.out se află T linii ce reprezintă răspunsul pentru fiecare întrebare.

Restricţii

  • 1 ≤ T ≤ 15
  • 1 ≤ lungimea şirului ≤ 10000
  • Nu este necesar să ştiţi structura de date arbore binar pentru a rezolva această problemă.

Exemplu

ingamfat.iningamfat.out
2
PNP
NN
6
33
Trebuie sa te autentifici pentru a trimite solutii. Click aici