Šeštadieninė informatikos olimpiadininkų mokykla

Viena iš galimybių pagreitinti skaičiavimus yra atlikinėti juos lygiagrečiai, tai reiškia, kad kai kurie veiksmai atliekami tuo pačiu laiku. Kai kurie šiuolaikiniai mikroprocesoriai jau turi galimybę lygiagrečiai atlikinėti nepriklausomas komandas. Norint pasinaudoti tokiomis mikroprocesorių galimybėmis, turime rašyti programas pritaikytas lygiagretiems skaičiavimams.

Šiame uždavinyje pasinaudokime tokiu paprastu modeliu. Sakykime, procesorius gali naudoti atminties laukelių, kurie yra sunumeruoti nuo 1 iki , bei lygiagrečiai gali atlikti neribotą skaičių komandų.

Procesorius gali atlikti tik šias komandas:

L I J

į I–ąjį atminties laukelį patalpina skaičių J; 

M I J

įI–ąjį atminties laukelį patalpina skaičių iš J–ojo laukelio; J–ojo atminties laukelio reikšmė nesikeičia; 

A I J

sudeda I–tajame laukelyje esantį skaičių su skaičiumi J, rezultatą patalpiną į I–ąjį laukelį; 

S I J

sudeda I–tajame laukelyje esantį skaičių su J–ajame laukelyje esančiu skaičiumi, rezultatą patalpiną į I–ąjį laukelį 

Atliekant komandas lygiagrečiai laikomasi taisyklės: Tuo pačiu laiko momentu negalima vykdyti dviejų ar daugiau komandų su tuo pačiu laukeliu. Pavyzdžiui, lygiagrečiai negalima atlikti komandų M 1 5 ir M 2 5. Be to, negalima keisti veiksmų, atliekamu su tuo pačiu atminties laukeliu, eilės tvarkos. Taip pat privalo būti įvykdytos visos komandos. Optimizuoti negalima.

Pritaikant komandų seką lygiagretiems skaičiavimams, komandos suskirstomos į blokus taip, kad blokuose esančių komandų veiksmai nesikirstų. Taigi visas vienam blokui priklausančias komandas galima atlikti lygiagrečiai.

Atminties laukelių turinys atlikus pradinę veiksmų seką privalo sutapti su atminties laukelių turiniu atlikus tą pačią seką pritaikytą lygiagrečiam skaičiavimui. Jei tą pačią komandą galima paskirti į kelis skirtingus blokus, ją reikia įtraukti į bloką su mažiausiu numeriu.

Užduotis

Parašykite programą, kuri duotąją veiksmų seką pritaikytų lygiagretiems skaičiavimams, t. y. pateiktas komandas suskirstytų į blokus.

Blokų skaičius turi būti kuo mažesnis.

Pradiniai duomenys

Pirmoje eilutėje įrašytas atminties laukelių skaičius bei komandų skaičius . Laikome, kad komandos yra sunumeruotos nuo 1 iki . Likusiose eilučių įrašytos komandos – po vieną į eilutę. Kiekvieną komandą sudaro viena raidė (L, M, A arba S) bei du skaičiai. Jei skaičius reiškia atminties ląstelės numerį, tuomet jis yra iš intervalo 1.., priešingu atveju priešingu atveju – gali būti bet kuris sveikasis skaičius.

Rezultatai

Turi būti išspausdinti blokams priklausančių komandų numeriai po vieną numerį eilutėje. Vieno bloko komandų numerių sąrašas užbaigiamas nuliu (0). Pirma pateikite pirmąjąm blokui priklausančių komandų sąrašą, po to antrąjąm ir t. t.

Komandų, priklausančių tam pačiam blokui, numeriai turi būti pateikiami didėjimo tvarka.

Pavyzdžiai

12 6 
L 10 4 
L 11 3 
M 12 11 
L 11 5 
S 10 12 
L 6 5

1
2
6 
0 
3 
0 
4 
5 
0

Pirmu žingsniu atliekami trys veiksmai: 
L 10 4 
L 11 3 
L 6 5 
Antru žingsniu atliekamas vienas veiksmas: 
M 12 11 
Trečiu žingsniu atliekami du veiksmai: 
L 11 5 
S 10 1

Ribojimai