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

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.

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 Plata:

//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;
}

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 #1592 Plata

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1592 Plata 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 #1592 Plata