Găleți

Avem n găleți numerotate de la stânga la dreapta numere de la 1 la n. Fiecare găleată conține inițial 1 litru de apă. Capacitatea fiecărei găleți se consideră 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 cu \( a_i \) volumul de apă conținut în găleata cu numrăul 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,\forall \) k a.î. j < k < i (dacă j + 1 = k, atunci această regulă nu va putea exista);
3. efortul depus este \( a_i \);
4. după vărsare \( a_j = a_j + a_i \) și \( a_i=0 \).

Cerința

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 galeti.in conține pe prima linie două numere naturale, n și e, în această ordine, separate printr-un 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 galeti.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 printr-un 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 și precizări

1 ≤ n ≤ 100.000
1 ≤ e ≤ 5.000.000.000
Se asigură faptul că există cel puțin o soluție posibilă pentru fiecare test în parte;
Dacă există mai multe soluții, oricare dintre ele se va considera validă;
Pentru teste în valoare de 18 puncte, datele de intrare sunt cunoscute. Mai precis:
Testul 0: n = 91, e = 90.
Testul 1: n = 30, e = 435.
Testul 2: n = 7, e = 16.
Pentru alte teste în valoare de 15 puncte, n ≤ 9.

În concurs s-au acordat 10p din oficiu. Aici, exemplul va valora exact 10p.

Exemplu

galeti.in

4 4

galeti.out

2 1
4 3
3 1

Explicație

Inițial, fiecare găleată conține 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 =>
2 0 1 1.
Apoi vărsăm un litru de apă din găleata 4 în găleata 3 cu efort 1 =>
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 =>
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ă.

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema galeti:

#include <bits/stdc++.h>
#define RECURSIV 0
using namespace std;
ifstream f("galeti.in");
ofstream g("galeti.out");
void solve_recursiv(int,int,long long);
void solve_iterativ();
int N,From[1000010],To[1000010];
long long E;
int main()
{

    f>>N>>E;
    if(RECURSIV){solve_recursiv(1,N,E);return 0;}
    solve_iterativ();
    return 0;
}
void solve_recursiv(int ST,int DR,long long E)
{
    int n=DR-ST+1;
    if(n==1)return;
    if(E>=2LL*n-3LL)
    {
        solve_recursiv(ST+1,DR,E-1LL*n+1LL);
        g<<ST+1<<' '<<ST<<'\n';
        return;
    }
    solve_recursiv(ST,DR-1,E-1LL);
    g<<DR<<' '<<ST<<'\n';
}
void solve_iterativ()
{
    int ST=1,DR=N,k=0;
    while(ST<DR)
    {
        int n=DR-ST+1;
        if(E>=2LL*n-3LL)
        {
            From[++k]=ST+1;
            To[k]=ST;
            ST++;E-=1LL*n-1LL;
        }
        else
        {
            From[++k]=DR;
            To[k]=ST;

            DR--,E-=1LL;
        }
    }
    for(;k;k--)
        g<<From[k]<<' '<<To[k]<<'\n';
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #2785 galeti

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2785 galeti de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #2785 galeti