Fişierul intrare/ieşire:starispirit.in, starispirit.outSursăACM ICPC Faza Nationala 2015
AutorTraian RebedeaAdăugată detrebedeaTraian Rebedea trebedea
Timp execuţie pe test1 secLimită de memorie8096 kbytes
Scorul tăuN/ADificultateN/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.instarispirit.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!
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?