# PBinfo #1592 – Plata – Rezolvare C++

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

## Enunț

Eroul nostru, Costy merge la magazin pentru a-şi cumpăra biscuiţi. Vânzătorul îi spune că biscuţii costă S nasturi, şi că doreste ca plata lor să fie făcută cu n tipuri diferite de nasturi. De asemenea, vânzătorul precizează că ar dori ca numărul de nasturi din fiecare tip i să depăşească valoarea x[i], dar, să nu depăşească valoarea y[i]. Presupunând că baiatul are o infinitate de nasturi din fiecare tip şi că doreşte să rămână cu cât mai mulţi nasturi de tipurile n, n-1, n-2,.. în buzunar, ajutaţi-l să efectueze plata şi să pună cât mai repede mâna pe biscuiţi.

Cerința
Scrieţi un program care să determine o modalitate de plată a sumei, respectând condiţiile din enunţ.

Date de intrare
Fişierul de intrare plata.in conţine:
 Pe prima linie, N S, reprezentând numărul de tipuri de nasturi şi suma care trebuie platită. 
 Pe următoarele N linii, două numere separate printr-un spaţiu, x[i] y[i], reprezentând numărul minim şi numărul maxim de nasturi de tipul i, care pot fi aleşi.

Date de ieșire
Fişierul de ieşire plata.out va conţine o linie cu n numere, separate prin câte un spatiu, r[1] r[2] r[3] . . . r[n] reprezentând numărul de nasturi de tipul i ales, sau cuvântul « imposibil » (fără ghilimele) dacă plata nu se poate realiza în condiţiile date.

Restricții și precizări

1 ≤ n ≤ 1000
1 ≤ x ≤ y ≤ 1000
1 ≤ s ≤ 1.000.000
Nasturii au aceeaşi valoare, indiferent de tipul acestora.

Exemplu:
plata.in

5 18
1 2
4 6
1 4
5 8
1 3
plata.out

2 6 4 5 1
Explicație
Eroul nostru va face plata in felul următor:
2 nasturi de tipul 1, 6 nasturi de tipul 2 , 4 nasturi de tipul 3, 5 nasturi de tipul 4, 1 nasture de tipul 5,
În total 2 + 6 + 4 + 5 + 1 = 18 nasturi
De observat că dacă se alegea soluţia : 1 6 4 6 1, aceasta nu era corectă deoarece Costy trebuia să scoată din buzunar un nasture de tip mai mare în schimbul celui de tip 1.

## Cod sursă C++

```cpp
//Dragan Andrei Gabriel
//Complexitate O(N)
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n, i, s1, s2, s, x[1001], y[1001];
int main()
{
    freopen("plata.in", "r", stdin);
    freopen("plata.out", "w", stdout);
    scanf("%d %d", &n, &s);
    for (s1 = s, i = 1; i <= n; i++)
        scanf("%d %d", &x[i], &y[i]), s1 -= x[i], s2 += y[i];
    if (s1 < 0 || s2 < s)
    {
        printf("imposibil\n");
        return 0;
    }
    for (s = s1, i = 1; i <= n; i++)
    {
        if (y[i] - x[i] <= s && s > 0)
            printf("%d ", y[i]), s -= (y[i] - x[i]); else
            if (y[i] - x[i] > s && s > 0)
                printf("%d ",s + x[i]), s=0; else
                if (s == 0) printf("%d ", x[i]);
    }
    return 0;
}
```

## Resurse

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