# PBinfo #2963 – mostenire1 – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: deivid

## Enunț

Împăratul cel bătrân vrea să împartă sacii cu galbeni din vistieria palatului celor K feciori ai săi, numerotați de la 1 la K în ordinea vârstei. Feciorul cu numărul 1 este cel mai mare, iar mezinul are numărul K. În vistierie sunt N saci plini cu galbeni, așezați în linie, atât de grei încât nu li se poate schimba ordinea, iar pe fiecare sac este scris numărul de galbeni pe care îi conține. Împăratul îl cheamă pe unul dintre feciori și îi spune: “Fiule, a ta este averea primilor x1 saci!”. Feciorul ia sacii și pleacă fericit. Apoi, împăratul cheamă alt fecior și îi spune: “Fiule, a ta este averea primilor x2 saci dintre cei rămași!”. Și așa mai departe, până ajunge la ultimul fecior chemat, căruia îi dă toți sacii rămași.
El nu are o ordine anume în care își cheamă feciorii dar are grijă să cheme fiecare fecior exact o dată. Totodată, pentru a evita certurile între ei, este atent ca fiecare fecior să primească cel puțin un sac cu galbeni, dar să NU primească în total mai mulți galbeni ca un frate mai mare decât el. Cel mai mic dintre feciorii împăratului este și cel mai viteaz, așa că împăratul ar vrea să îi dea lui o sumă de bani cât mai mare, fără a-i supăra pe ceilalți feciori ai săi.

Cerința
Cum ar putea împărți împăratul sacii?

Date de intrare
Fișierul de intrare mostenire.in conține pe prima linie numerele naturale N, K, separate de un spațiu, cu semnificația din enunț. Pe următoarele N linii se găsește câte un număr natural, reprezentând numărul de galbeni din fiecare sac, în ordinea în care aceștia urmează să fie distribuiți fiilor.

Date de ieșire
Fișierul de ieșire mostenire.out va conține pe prima linie suma de galbeni pe care o va primi fiul cel mic de la împărat. Pe următoarele K linii se vor afla câte două numere naturale ce reprezintă numărul de ordine al feciorului, respectiv numărul de saci xi pe care îi primește acesta, în ordinea în care au fost chemați de împărat.

Restricții și precizări

2 ≤ K ≤ 100
K ≤ N ≤ 100 000
1 ≤ Numărul de galbeni din fiecare sac ≤ 100 000
Galbenii din oricare dintre saci nu pot fi împărțiți mai multor frați
Numărul total de galbeni aflați în vistierie este mai mic sau egal cu 1.000.000.000
Împăratul cel bătrân nu are doi feciori cu aceeași vârstă
Puteți afișa orice soluție în care mezinul primește numărul maxim posibil de galbeni
Pentru fiecare test, afișarea corectă a numărului maxim de galbeni primiți de mezin este notată cu 40% din punctajul alocat testului
Pentru teste valorând 10 puncte N = K, N ≤ 100
Pentru teste valorând 30 de puncte 2 ≤ K < N ≤ 15
Pentru teste valorând 50 de puncte 2 ≤ K < N ≤ 100
În concurs s-au acordat 10 puncte din oficiu. Aici se acodră pentru exemplele din enunț.

Exemplul 1:
mostenire.in

8 3
1
2
3
4
5
6
7
8
mostenire.out

10
3 4
2 2
1 2
Explicație
Fiul cel mic este chemat primul și ia primii 4 saci, primind astfel 1 + 2 + 3 + 4 = 10 galbeni.
Fiul cel mijlociu este chemat al doilea și ia următorii 2 saci, primind astfel 5 + 6 = 11 galbeni.
Fiul cel mare este chemat ultimul și ia restul de 2 saci, primind astfel 7 + 8 = 15 galbeni.

Exemplul 2:
mostenire.in

12 4
10
5
23
1
20
4
10
12
6
23
18
17
mostenire.out

35
2 3
4 4
1 3
3 2
Explicație
Al doilea fiu în ordinea vârstei este chemat primul și ia primii 3 saci, primind astfel 10 + 5 + 23 = 38 de galbeni.
Fiul cel mic este chemat al doilea și ia următorii 4 saci, primind astfel 1 + 20 + 4 + 10 = 35 de galbeni.
Fiul cel mare este chemat al treilea și ia următorii 3 saci, primind astfel 12 + 6 + 23 = 41 de galbeni.
Al treilea fiu în ordinea vârstei este chemat ultimul și ia restul de 2 saci, primind astfel 18 + 17 = 35 de galbeni.
O altă soluție corectă este:

35
2 3
3 4
1 3
4 2

## Cod sursă C++

```cpp
/*
 * Problema mostenire (OJI 2019)
 * Complexitate: O(N*(log(S)+log(N))
 * Autor: Lucian Bicsi
 */
#include <bits/stdc++.h>
using namespace std;
vector<tuple<int, int, int>> Solve(vector<int> v, int k, int need) {
    int n = v.size();
    vector<tuple<int, int, int>> ans;
    int have = 0, start = 0;
    for (int i = 0; i < n; ++i) {
        have += v[i];
        if (have < need) continue;
        if ((int)ans.size() == k - 1 && i != n - 1) continue;
        ans.emplace_back(have, start, i + 1);
        have = 0;
        start = i + 1;
    }
    return ans;
}
int main() {
    ifstream cin("mostenire.in");
    ofstream cout("mostenire.out");
    int n, k; cin >> n >> k;
    assert(k <= 100);
    assert(k <= n);
    assert(n <= 100 * 1000);
    vector<int> v(n);
    int total = 0;
    for (int i = 0; i < n; ++i) {
        cin >> v[i];
        total += v[i];
    }
    assert(total <= 1000 * 1000 * 1000);
    int b = 0, e = total, ans = -1;
    while (b <= e) {
        int m = (b + e) / 2;
        if ((int)Solve(v, k, m).size() == k) {
            ans = m;
            b = m + 1;
        } else e = m - 1;
    }
    assert(ans != -1);
    cout << ans << endl;
    auto sol = Solve(v, k, ans);
    sort(sol.rbegin(), sol.rend());
    vector<tuple<int, int, int>> new_sol;
    for (int i = 0; i < k; ++i) {
        int b, e; tie(ignore, b, e) = sol[i];
        new_sol.emplace_back(b, i, e - b);
    }
    sort(new_sol.begin(), new_sol.end());
    for (auto itr : new_sol) {
        int i, cnt; tie(ignore, i, cnt) = itr;
        cout << i + 1 << " " << cnt << '\n';
    }
    return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/2963)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/2963/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-2963/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)