Lista de probleme 2

Părinții lui Rox au cumpărat de curând un teren care are N metri lățime și M metri lungime, pe care l-au împărţit în pătrate cu latura de un metru, denumite celule. Văzând planul terenului, lui Rox i-a venit o idee. Ea s-a decis să semene florile ei preferate în etape, pe U dintre parcele de teren. Denumirile florilor sunt litere mari ale alfabetului
englez. O parcelă este un dreptunghi inclus în teren, cu laturile paralele cu ale terenului și care conține doar celule complete.

În fiecare etapă în care Rox seamănă flori, procedează astfel: alege o parcelă pentru care reține indicii celulelor din stânga sus și dreapta jos, stabilește tipul florii pe care dorește să o semene peste tot în parcelă, apoi scrie aceste informații pe o foaie de hârtie. Documentându-se pe Internet, Rox ajunge la concluzia că apare următorul fenomen ciudat: dacă într-o celulă se seamănă același tip de floare într-un număr par de etape, semințele de acel tip pur și simplu dispar.

Când finalizează semănatul, Rox le povesteşte părinților despre isprava ei. Entuziasmați, părinții fetei îi pun mai multe întrebări de tipul ”Câte tipuri de flori au rămas semănate în celula de pe linia L și coloana C?”

Deoarece Rox a plantat foarte multe flori, ea nu poate să răspundă rapid întrebărilor părinților, așa încât vă cere ajutorul și vă va răsplăti efortul cu maxim 100 de puncte.

Algorel tocmai a avut un interviu la AlgoTech. Fiind isteţ din fire, el a reuşit să rezolve toate problemele, mai puţin una de care nu reuşeşte nicicum să se prindă cum se face. Aflând că la Iaşi are loc Concursul Urmaşii lui Moisil, s-a gândit să propună această problemă şi să ofere 100 de puncte ca recompensă celor care o rezolvă corect.

Fie un şir cu N cifre asupra căruia se poate efectua operaţia swap de maxim X ori. Prin swap se înţelege interschimbarea a două elemente din şir aflate pe poziţii vecine.

Să se determine numărul maxim care se poate obţine din şirul cu N cifre, după efectuarea a maxim X operaţii swap.