Lista de probleme 2

Jocul betaşah se joacă folosindu-se doar piese asemănătoare damelor clasicului şah, numite tot dame. Suprafaţa de joc are o formă triunghiulară şi este formată din N*(N+1)/2 pătrate identice dispuse pe N rânduri şi N coloane. Rândurile se numerotează de sus în jos, de la 1 la N. Coloanele se numerotează de la stânga la dreapta, de la 1 la N. Primul rând conţine un singur pătrat, al doilea rând conţine două pătrate alăturate,…, al N-lea rând conţine N pătrate alăturate, ca în suprafeţele de joc cu N=6 din figurile de mai jos. Din cele N*(N+1)/2 pătrate, K sunt gri, iar restul sunt albe. Poziţia fiecărui pătrat de pe suprafaţa de joc este dată de rândul şi coloana în care acesta este situat.

Pe suprafaţa de joc sunt aşezate D dame în D pătrate albe distincte, ocupându-le. Într-un pătrat alb poate fi aşezată o singură damă, iar într-un pătrat gri nu poate fi aşezată nicio damă. Poziţia unei dame pe suprafaţa de joc este dată de poziţia pătratului alb în care este aşezată dama.

Damele pot accesa orice pătrat alb neocupat situat pe direcţiile: verticală, orizontală sau diagonală, numerotate de la 1 la 8 în figura b). Accesul pe o direcţie se face trecând din pătrat alb în pătrat alb (doar pătrate albe neocupate) până la întâlnirea unui pătrat gri sau a unui pătrat alb ocupat de o altă damă sau până la terminarea suprafeţei de joc.

Numim pătrat accesibil orice pătrat alb neocupat (de pe suprafaţa de joc) care ar putea fi accesat de cel puţin una din cele D dame.

De exemplu, pentru suprafaţa de joc din figura c) numărul de pătrate accesibile (marcate cu X) de pe suprafaţă este 11; pentru suprafaţa de joc cu N=6, D=3 şi K=4 din figura d) numărul de pătrate accesibile de pe suprafaţă este 13. În figura e) sunt marcate cu X pătratele accesibile fiecărei dame de pe suprafaţa de joc din figura d).

Pătratele accesibile damei din rândul 3 şi coloana 2	Pătratele accesibile damei din rândul 5 şi coloana 2	Pătratele accesibile damei din rândul 5 şi coloana 4	Pătratele accesibile de pe suprafaţa de joc
Figura e)

Scrieţi un program care să citească numerele naturale N, D, K, poziţiile damelor şi ale pătratelor gri pe suprafaţa de joc şi care să determine:
a) numărul maxim M de pătrate albe conţinute de un rând al suprafeţei de joc;
b) numărul P de pătrate accesibile de pe suprafaţa de joc.

O clepsidră este un dispozitiv folosit pentru a măsura timpul. Clepsidra este alcătuită din două incinte de sticlă, conectate printr-un tub fin. Una dintre incinte este umplută cu nisip, acesta scurgându-se în cea de-a doua incintă, cu o viteză constantă. Clepsidra poate fi întoarsă, pentru a măsura o altă perioadă de timp.

Arheologii au descoperit un dispozitiv, pe care l-au denumit clepsidru, format din n clepsidre identice, suprapuse, numerotate de la 1 la n, prin care nisipul poate circula de la o clepsidră la alta datorită forţei gravitaţionale.

Studiind acest obiect, arheologii au constatat că :

• dispozitivul poate fi utilizat atât în poziţia 1, când clepsidrele sunt în ordinea 1, 2 ,…, n cu clepsidra n aşezată pe sol, cât şi în poziţia 2, când clepsidrele sunt în ordinea n, n-1,…, 1 cu clepsidra 1 aşezată pe sol;
• viteza de trecere a nisipului de la o incintă la alta, a aceleiaşi clepsidre, este de 1 bob de nisip/secundă, pentru toate clepsidrele, indiferent de poziţie;
• trecerea clepsidrului dintr-o poziţie în alta presupune răsturnarea acestuia şi reaşezarea boabelor de nisip;
• timpul de trecere a boabelor de nisip de la o clepsidră la alta este 0.

Arheologii studiază comportarea clepsidrului realizând două experimente diferite, după cum urmează:

a) Se aşează clepsidrul în poziţia 1, se introduc în incinta de sus a clepsidrei 1 un număr b de boabe de nisip şi se determină după câte secunde vor ajunge toate boabele de nisip în incinta de jos a ultimei clepsidre;
b) Se aşează clepsidrul în poziţia 1, se introduc în incinta de sus a clepsidrei 1 un număr b de boabe de nisip, apoi se aşează clepsidrul în k stări consecutive, o stare fiind caracterizată de valorile si şi pi , 1 ≤ i ≤ k, ce reprezintă numărul de secunde, respectiv poziţia, în care este menţinut nemişcat clepsidrul, iar la final se determină numărul de boabe de nisip din incintele fiecărei clepsidre.

Spre exemplu, dacă clepsidrul este format din n=2 clepsidre, iar în incinta de sus a primei clepsidre se introduc b=3 boabe de nisip, la primul experiment se va obţine valoarea 4.

La al doilea experiment se aşează clepsidrul în k=2 stări, caracterizate prin s1=3, p1=1; s_{2=1, p2=2.}

Numărul de boabe de nisip din clepsidre va evolua ca în figura alăturată.

Să se scrie un program care citeşte valorile n şi b, precum şi valorile k, si, pi , 1 ≤ i ≤ k, şi calculează valorile obţinute de arheologi la realizarea celor două experimente.