Fișierul intrare/ieșire	amestec.in, amestec.out	Sursă	ONI 2013 clasa a 8-a
Autor	Ciprian Cheșcă	Adăugată de	Tudor Coman • tudorcoman
Timp de execuție pe test	0.5 sec	Limită de memorie	4096 KB
Scorul tău	N/A	Dificultate	N/A

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Amestec (clasa a 8-a)

Se consideră un amestec de două substanțe, ale căror molecule se notează cu 0, respectiv 1, reprezentat ca o matrice pătratică cu n linii și n coloane.

În vederea separării celor două substanțe, asupra amestecului se aplică succesiv o serie de k forțe magnetice, caracterizate de următoarele trei mărimi:

• durata aplicării forței, notată cu d_i (1 ≤ i ≤ k) exprimată în secunde;
• poziția aplicării forței, notată cu p_i {‘N’, ‘S’, ‘E’, ‘V’}, 1 ≤ i ≤ k, ce reprezintă unul dintre cele patru puncte cardinale (Nord, Sud, Est, Vest);
• tipul moleculelor (0 sau 1) asupra cărora acționează forța, notat cu m_i, 1 ≤ i ≤ k.

Deplasarea moleculelor se face după următoarele reguli:

• moleculele se deplasează numai pe orizontală când forța este aplicată în Est sau Vest sau numai pe verticală când forța este aplicată în Nord sau Sud;
• moleculele se deplasează către locul în care este amplasată forța și, într-o secundă, o moleculă se deplasează cel mult cu o singură poziție;
• o moleculă se deplasează numai dacă în fața ei, în direcția de deplasare, există o moleculă de alt tip, cu care face schimb de locuri, altfel rămâne pe aceeași poziție;
• o forță acționează asupra tuturor moleculelor de tipul precizat.

Cerință

Să se scrie un program care determină matricea amestecului obținut după aplicarea forțelor magnetice.

Spre exemplu, dacă n = 3, matricea moleculelor este cea de mai jos și se aplică k = 2 forțe, caracterizate prin 1N1, 2E0, amestecul va trece prin următoarele etape:

Date de intrare

Fișierul de intrare amestec.in conține pe prima linie două numerele naturale, n și k, separate printr-un spațiu, cu semnificația de mai sus. Pe fiecare din următoarele n linii se găsește câte un șir de n caractere 0 sau 1. Pe fiecare dintre următoarele k linii se găsesc câte 3 valori, după cum urmează: un număr natural d_i, un caracter p_i (‘N’, ‘S’, ‘E’, ‘V’) și un număr natural m_i, 1 ≤ i ≤ k, având semnificația de mai sus, neseparate prin spațiu.

Date de ieșire

Fișierul de ieșire amestec.out va conține matricea amestecului final. Pe fiecare din cele n linii ale fișierului de ieșire se va scrie câte un șir de n caractere 0 sau 1, neseparate prin spațiu.

Restricții

• 2 ≤ n ≤ 100
• 1 ≤ k ≤ 100
• 1 ≤ d_i ≤ 10⁹, 1 ≤ i ≤ k

Exemplu

Explicație

Matricea moleculelor are 3 linii și 3 coloane.
Se aplică un număr de k = 2 forțe, prima cu durata de 1 secundă, spre nord, și care atrage moleculele de tip 1, și a doua cu durata de 2 secunde, spre est, ce atrage moleculele de tip 0. După aplicarea celor 2 forțe, moleculele se vor reașeza conform matricei alăturate.