Fişierul intrare/ieşire:galeti2.in, galeti2.outSursăOJI 2018, Clasele 11-12
AutorAdrian PanaeteAdăugată deAndrei1998Andrei Constantinescu Andrei1998
Timp execuţie pe test0.25 secLimită de memorie32768 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Galeti2

Avem n găleţi, numerotate de la stânga la dreapta cu numere de la 1 la n. Fiecare găleată conţine iniţial 1 litru de apă. Capacitatea fiecărei găleţi este nelimitată. Vărsăm găleţile una în alta, respectând o anumită regulă, până când toată apa ajunge în prima găleată din stânga. Vărsarea unei găleţi presupune un anumit efort.

Regula după care se răstoarnă găleţile este următoarea: se aleg două găleţi astfel încât orice găleată situată între ele să fie goală. Se varsă apa din găleata din dreapta în găleata din stânga. Efortul depus este egal cu volumul de apă din găleata din dreapta (cea care se varsă).

Formal, dacă notăm  a_i volumul de apă conţinut în găleata cu numărul i, regula de vărsare a acestei găleţi în găleata cu numărul j poate fi descrisă astfel:

  1. j < i
  2. a_k = 0 pentru orice k astfel încât j < k < i
  3. efortul depus este  a_i
  4. după vărsare  a_j = a_j + a_i şi  a_i = 0

Cerinţă

Cunoscând numărul de găleţi n şi un număr natural e, să se determine o succesiune de vărsări în urma căreia toată apa ajunge în găleata cea mai din stânga şi efortul total depus este exact e.

Date de intrare

Fişierul de intrare galeti2.in conţine pe prima linie două numere naturale, n şi e, în această ordine, separate prin spaţiu. Primul număr n reprezintă numărul de găleţi. Al doilea număr e reprezintă efortul care trebuie depus pentru a vărsa toată apa în găleata din stânga.

Date de ieşire

Fişierul de ieşire galeti2.out trebuie să conţină n - 1 linii care descriu vărsările, în ordinea în care acestea se efectuează, pentru a vărsa toată apa în găleata din stânga cu efortul total e. Fiecare dintre aceste linii trebuie să conţină două numere i şi j, separate prin spaţiu, cu semnificaţia că apa din găleata cu numărul i se varsă în găleata cu numărul j.

Restricţii

  • 1 ≤ n ≤ 100 000
  • 1 ≤ e ≤ 5 000 000 000
  • Se asigură că pentru datele de test există cel puţin o soluţie posibilă,
  • Dacă există mai multe soluţii se poate afişa oricare dintre acestea.
  • Punctajul maxim al problemei este de 100 de puncte dintre care 10 puncte din oficiu.
  • Pentru teste in valoare de 18 puncte datele de intrare sunt cunoscute. Mai precis:
Numarul testuluine
29190
330435
4716
  • Pentru alte teste in valoare de 15 puncte n ≤ 9.
  • Conform regulamentului OJI, se vor acorda 10 puncte din oficiu (pentru rezolvarea exemplelor).

Exemplu

galeti2.ingaleti2.outExplicaţie
4 4
2 1
4 3
3 1
Initial fiecare galeata contine câte un litru de apă.
1 1 1 1.
Prima dată vărsăm un litru de apa din găleata 2 în găleata 1 cu efort 1  \rightarrow
2 0 1 1.
Apoi vărsăm un litru de apă din găleata 4 în găleata 3 cu efort 1  \rightarrow
2 0 2 0.
În final vărsăm cei doi litri de apă din găleata 3 în găleata 1 cu efort 2  \rightarrow
4 0 0 0
O altă variantă corectă ar fi fost:
4 3
2 1
3 1
Observaţi că următoarea succesiune de vărsări este greşită:
4 2
2 1
3 1
Deşi efortul depus este 4 si cei 4 litri ajung în prima găleata, la primul pas vărsarea unui litru de apă din găleata 4 în găleata 2 nu este permisă deoarece între acestea se găseşte găleata 3 care conţine apă.
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?