Lista de probleme 8

În anul de grație 6983 (1475), armata turcească condusă de Suleiman Pașa a fost învinsă de armatele aliate creștine moldo-maghiaro-polone conduse de Ștefan cel Mare. Bătălia a avut loc lângă Vaslui în locul numit Podu Înalt. Terenul în care s-au desfășurat luptele poate fi reprezentat ca un tablou bidimensional cu N linii și M coloane, numerotate începând de la 1. Poziția unui element din matrice este identificată prin linia și coloana corespunzătoare. La luptă au participat P oșteni, în poziții distincte, pozițiile acestora în teren fiind cunoscute.

• Determinaţi o diagonală tactică astfel încât terenul de luptă să fie împărțit în două zone care conţin acelaşi număr de oșteni. Dacă nu există soluție, se va scrie doar valoarea -1.
• Determinaţi două diagonale tactice perpendiculare care împart terenul de luptă în patru zone care conţin, fiecare, acelaşi număr de oșteni. Dacă nu există soluție, se va scrie doar valoarea -1.

Se dau N secvențe speciale de forma [a, b] și apoi T secvențe de interogare [L,R]. Orice secvență care include cel puțin o secvență specială va fi numită secvență super-specială. Numărul de secvențe super-speciale pe care o secvență [L, R] le include va fi denumit capacitatea secvenței [L, R]. Pentru fiecare secvență de interogare, să se determine capacitatea sa.

Seiful SEPI, în care sunt depozitate premiile olimpiadelor de informatică, este securizat cu un cifru sub forma unei matrice A de formă pătratică cu N linii și N coloane, unde N este un număr natural par. Liniile și coloanele sunt numerotate începând cu 1. Matricea-cifru A este formată din N / 2 chenare. Al i-lea chenar (1 ≤ i ≤ N / 2) va conține elementele aflate pe marginea matricei A, după excluderea primelor i - 1 chenare. Ordinea elementelor acestui chenar este obținută pornind din poziția (i, i), parcurgând latura de sus de la stânga la dreapta, latura din dreapta de sus în jos, latura de jos de la dreapta la stânga și apoi latura din stânga de jos în sus. Cunoscând numărul natural N, cele N x N elemente ale matricei-cifru precum și succesiunea de T operații de permutare circulară a unor chenare, să se determine configurația finală a matricei, cea care va permite deschiderea seifului!

Baxibilian în timp ce învață la informatică a descoperit jocul Loopover. Cum nu are timp să analizeze prea mult jocul Loopover, deoarece are de învățat, el dorește să știe următoarele lucruri:

• Fiind dată starea unei tabele asupra căreia s-au făcut fie doar operații asupra liniilor, fie doar operații asupra coloanelor, care este numărul minim de operații pe care Baxibilian ar trebui să le aplice pentru a reveni în starea inițială?
• Fiind dată o secvență de m operații, care este numărul minim de aplicări ale acestei secvențe asupra unei tabele de dimensiune n x n aflate în starea inițială astfel încât starea finală să fie aceeași ca starea inițială? Întrucât rezultatul poate fi un număr foarte mare, Baxibilian este mulțumit dacă află doar restul împărțirii acestui număr la 1.000.000.007.

În așteptarea marii confruntări cu turcii, oștenii moldoveni își antrenează mintea, jucând un joc de echipă denumit Bârligă. O echipă are N jucători, numerotați de la 1 la N, în ordinea în care sunt așezați. Fiecare jucător primește o scândură vopsită pe o față cu roşu, iar pe cealaltă cu galben. Scrieți un program care cunoscând N, numărul de jucători din echipă, precum și valorile scrise pe fața roșie a scândurii primite de fiecare jucător, determină punctajul maxim pe care îl poate obține echipa, precum și numerele de ordine ale jucătorilor care trebuie să întoarcă scândura cu față galbenă în sus, pentru a obține acest punctaj maxim.

Se consideră două numere naturale K și N. Să se determine numărul T al tuplelor formate din K numere naturale (X1, X2, X3, …, XK) cu proprietățile:

• 1 ≤ X1 ≤ X2 ≤ X3 ≤ ... ≤ XK ≤ N
• cel mai mare divizor comun al numerelor X1, X2, …, XK este 1.

Se dă un șir s = s0, s1,…, sn-1 de n litere mici. Prin s[i..j] se înțelege secvența si, si+1, …, sj. Asupra șirului se efectuează de mai multe ori operația switch(i,j,c1,c2), care în secvența s[i..j] modifică orice apariție a literei c1 în litera c2. Dându-se șirul s și m operații switch, să se afișeze șirul s după efectuarea celor m operații.

Dorel are o expresie aritmetică reprezentată ca un șir de caractere de lungime N, ce conține ca operanzi cifre nenule, iar ca operatori aritmetici adunarea și înmulțirea, operatori reprezentați prin + și *. Asupra expresiei aritmetice se pot efectua cel mult K operații de interschimbare între doi operatori. De exemplu, pentru expresia 2*3+5+7+1, a cărei valoare este 19, dacă efectuăm o operație de interschimbare între primul și cel de-al treilea operator obținem expresia 2+3+5*7+1, a cărei valoare este 41. Să se afle valoarea maximă a expresiei după efectuarea a cel mult K operații de interschimbare între doi operatori.