Fişierul intrare/ieşire:clepsidru.in, clepsidru.outSursăOJI 2013, clasa a 9-a
AutorCiprian ChescaAdăugată deMihai22eMihai Ionut Enache Mihai22e
Timp execuţie pe test1 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Clepsidru

O clepsidra este un dispozitiv folosit pentru a masura timpul. Clepsidra este alcatuita din doua incinte de sticla, conectate printr-un tub fin. Una dintre incinte este umpluta cu nisip, acesta scurgandu-se in cea de-a doua incinta, cu o viteza constanta. Clepsidra poate fi intoarsa, pentru a masura o alta perioada 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 clepsidra la alta datorita fortei gravitationale.
Studiind acest obiect, arheologii au constatat ca:

  • dispozitivul poate fi utilizat atat in pozitia 1, cand clepsidrele sunt in ordinea 1, 2, ..., n cu clepsidra n asezata pe sol, cat si in pozitia 2, cand clepsidrele sunt in ordinea n, n-1, ..., 1 cu clepsidra 1 asezata pe sol;
  • viteza de trecere a nisipului de la o incinta la alta, a aceleiasi clepsidre, este de 1 bob de nisip/secunda, pentru toate clepsidrele, indiferent de pozitie;
  • trecerea clepsidrului dintr-o pozitie in alta presupune rasturnarea acestuia si reasezarea boabelor de nisip;
  • timpul de trecere a boabelor de nisip de la o clepsidra la alta este 0.

Arheologii studiaza comportarea clepsidrului realizand doua experimente diferite, dupa cum urmeaza:

  1. Se aseaza clepsidrul in pozitia 1, se introduc in incinta de sus a clepsidrei 1 un numar b de boabe de nisip si se determina dupa cate secunde vor ajunge toate boabele de nisip in incinta de jos a ultimei clepsidre;
  2. Se aseaza clepsidrul in pozitia 1, se introduc in incinta de sus a clepsidrei 1 un numar b de boabe de nisip, apoi se aseaza clepsidrul in k stari consecutive, o stare fiind caracterizata de valorile Si si Pi, 1 ≤ i ≤ k, ce reprezinta numarul de secunde, respectiv pozitia, in care este mentinut nemiscat clepsidrul, iar la final se determina numarul de boabe de nisip din incintele fiecarei clepsidre.

Spre exemplu, daca clepsidrul este format din n=2 clepsidre, iar in incinta de sus a primei clepsidre se introduc b=3 boabe de nisip, la primul experiment se va obtine valoarea 4.
La al doilea experiment se aseaza clepsidrul in k=2 stari, caracterizate prin S1=3, P1=1; S2=1, P2=2.
Numarul de boabe de nisip din clepsidre va evolua ca in figura alaturata.

Cerinta

Sa se scrie un program care citeste valorile n si b, precum si valorile k, Si, Pi, 1 ≤ i ≤ k, si calculeaza valorile obtinute de arheologi la realizarea celor doua experimente.

Date de intrare

Prima linie a fisierului de intrare clepsidru.in contine doua numere naturale nenule n si b, separate printr-un singur spatiu, cu semnificatia din enunt; a doua linie contine numarul natural nenul k avand semnificatia din enunt, iar urmatoarele k linii contin fiecare cate o pereche de valori Si si Pi, 1 ≤ i ≤ k, separate printr-un singur spatiu, cu semnificatia din enunt.

Date de ieşire

Fisierul de iesire clepsidru.out va contine pe prima linie un numar natural ce reprezinta valoarea obtinuta la primul experiment, iar pe urmatoarele n linii va contine cate o pereche de numere naturale, separate printr-un singur spatiu, ce reprezinta cantitatile de boabe de nisip din incintele de sus si jos ale celor n clepsidre, scrise in ordinea de la 1 la n a clepsidrelor, dupa realizarea celui de-al doilea experiment.

Restricţii

  • 1 ≤ n ≤ 1 000
  • 1 ≤ b ≤ 1 000 000 000
  • 1 ≤ k ≤ 1 000
  • 1 ≤ Si ≤ 1 000, 1 ≤ i ≤ k
  • Pi apartine multimii {1, 2}, 1 ≤ i ≤ k
  • pentru rezolvarea corecta a primei cerinte se acorda 25% din punctaj, iar pentru rezolvarea corecta a celei de-a doua cerinte se acorda 75% din punctaj.
  • acordarea punctajului pentru a doua cerinta se face numai daca in fisierul de iesire exista un raspuns pentru prima cerinta, indiferent de corectitudinea acestuia.

Exemplu

clepsidru.inclepsidru.out
2 3
2
3 1
1 2
4
1 1
0 1

Explicaţie

  • Clepsidrul este format din n=2 clepsidre si in incinta de sus a primei clepsidre se introduc b=3 boabe de nisip.
  • Toate boabele de nisip vor ajunge in incinta de jos a ultimei clepsidre dupa 4 secunde.
  • Dupa ce clepsidrul este asezat 3 secunde in pozitia 1 si 1 secunda in pozitia 2, in clepsidre se vor gasi cate (1,1), (0,1) boabe de nisip.
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content