| Fişierul intrare/ieşire: | starispirit.in, starispirit.out | Sursă | ACM ICPC Faza Nationala 2015 |
| Autor | Traian Rebedea | Adăugată de |  Traian Rebedea •trebedea |
| Timp execuţie pe test | 0.5 sec | Limită de memorie | 8096 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Stari de spirit
Gigel are un nou hobby: el urmăreşte pe reţeaua socială Carteacufeţe activităţile desfăşurate de prietenii săi în fiecare zi. Astfel, pentru orice prieten al său din reţeaua socială, Gigel ştie activitatea desfăşurată într-o anumită zi. Mai mult, Gigel s-a apucat să ţină diverse statistici despre stările de spirit prin care trece fiecare prieten, precum şi despre activităţile desfăşurate de aceştia.
Drept urmare, pentru fiecare prieten, Gigel cunoaşte atât cele M activităţi desfaşurate de către acesta, cât şi cele K stări de spirit prin care trece prietenul respectiv. Mai mult, el a observat sau calculat următoarele lucruri despre prietenii săi:
1. Distribuţia de probabilitate pentru stările de spirit pentru fiecare prieten al său (dist[1..K]). Aceasta este folosită de Gigel pentru a estima starea de spirit doar dacă nu există informaţii despre nicio zi anterioară.
2. Faptul că starea de spirit dintr-o zi depinde doar de starea de spirit din ziua anterioară. De fapt, modelul real este mai complicat, dar Gigel s-a gandit sa vă ajute şi să folosească această premisă. Probabilitatea de tranziţie de la o stare de spirit din ziua anterioară la starea de spirit din ziua curentă este denotată de matricea A[1..K][1..K], numită matrice de tranziţie. Aceste matrici sunt individuale pentru fiecare persoană în parte.
3. Activitatea desfaşurată de fiecare persoană într-o zi depinde doar de starea sa de spirit din ziua respectivă. Drept urmare, pentru fiecare stare de spirit a unui prieten, Gigel ştie distribuţia de probabilitate ca prietenul său să practice o anumita activitate în ziua respectivă. Această distribuţie este modelată printr-o matrice B[1..K][1..M], unde fiecare rând din această matrice specifică distribuţia pentru starea de spirit K. Deci B[i][j] reprezintă probabilitatea ca persoana să practice activitatea j dacă este în starea de spirit i.
Gigel are nevoie ca voi să îl ajutaţi să rezolve următoarea problemă: să determinaţi cele mai probabile N stări de spirit prin care trece un prieten de-al său, pornind de la lista de activităţi desfăşurate de acesta/aceasta pentru o secvenţă consecutivă de N zile.
Date de intrare
Datele de intrare se citesc din fişierul starispirit.in.
Pe prima linie se află numărul de teste, T. După aceea, pentru fiecare test sunt citite următoarele informaţii.
- Prima linie pentru fiecare test conţine 3 numere naturale: N - numărul de zile din secvenţa analizată, K - numărul de stări de spirit şi M - numărul de activităţi practicate de prietenul curent.
- Pe a doua linie se află N numere naturale între 1..M separate prin spaţii, reprezentând acitivităţile desfăşurate de prietenul lui Gigel în secvenţa de N zile.
- Pe următoarea linie se află cele K numere reale modelând distribuţia dist[1..K] separate prin spaţii.
- Pe următoarele K linii se află câte K numere reale modelând distribuţia corespunzătoare lui A[i], 1<=i<=K.
- În final, pe ultimele K linii, se află M numere reale modelând distribuţia corespunzătoare lui B[j], 1<=j<=K.
Date de ieşire
Pentru fiecare test trebuie să afişaţi câte o linie în fişierul starispirit.out, care să conţină N numere reale corespunzând celei mai probabile secvenţe de stări de spirit prin care a trecut prietenul lui Gigel.
Restricţii
- 1 <= T <= 20
- 1 <= N, M <= 1000
- 1 <= K <= 30
- Activităţile sunt numerotate de la 1..M
- Stările de spirit sunt numerotate de la 1..K
Exemplu
| starispirit.in | starispirit.out |
|---|---|
| 4 1 2 2 1 0.75 0.25 0.5 0.5 0.3 0.7 0.5 0.5 0.5 0.5 1 2 2 1 0.75 0.25 0.5 0.5 0.3 0.7 0.1 0.9 0.5 0.5 4 2 3 1 2 2 2 0.75 0.25 0.75 0.25 0.25 0.75 0.50 0.25 0.25 0.1 0.9 0.1 3 2 3 1 2 3 0.6 0.4 0.7 0.3 0.4 0.6 0.5 0.4 0.1 0.1 0.3 0.6 | 1 2 1 2 2 2 1 1 2 |
Explicaţie
- Toate probabilităţile care influenţează starea de spirit dintr-o zi sunt independente una de cealaltă.
- Când nu există nici o zi anterioară, starea cea mai probabilă se determină doar în funcţie de activitatea desfăşurată în ziua respectivă şi distribuţia stărilor de spirit dist.
- Drept urmare, pentru primele două teste, contează doar activitatea observată în singura zi din testul respectiv şi probabilitatea dist să avem o anumită stare de spirit în prima zi.
- Pentru celelalte două teste, pentru toate zilele în afară de prima zi contează atât starea de spirit din ziua anterioară, cât şi activitatea desfăşurată în ziua curentă.
- Explicaţie pentru primele două teste:
- Primul test: 0.75 * 0.5 (pentru prima stare de spirit) > 0.25 * 0.5 (pentru a doua stare de spirit) => prima stare de spirit este mai probabilă
- Al doilea test: 0.75 * 0.1 (pentru prima stare de spirit) < 0.25 * 0.9 (pentru a doua stare de spirit) => a doua stare de spirit este mai probabilă
- Observaţie finală: probabilităţile sunt numere subunitare!
