La banca Moretime, moneda este Time-ul. Cei n clienţi ai băncii au conturi identificate prin valori naturale nenule, distincte două câte două. La deschiderea contului, fiecare client a depus un fond de siguranţă reprezentat printr-un număr natural nenul (cantitatea de Time aferentă contului, ce poate fi folosită de bancă, pentru urgenţe majore). Un client al băncii este considerat premium dacă numărul său de cont începe şi se termină cu aceeaşi cifră nenulă.
Lumea este lovită de criza de timp şi banca Moretime a hotărât să susţină doar clienţii premium printr-un program special. Astfel, banca va colecta fondurile de siguranţă ale unora dintre clienţii premium iar suma obţinută o va folosi integral pentru a finanţa, cu cantităţi egale de Time, pe fiecare client premium, inclusiv pe cei de la care a colectat fondul.

Cerința

Cunoscând n, numărul de clienţi, conturile şi valorile fondurilor de siguranţă ale acestora, să se determine:

a. numărul clienţilor premium;
b. numărul clienţilor premium ce pot fi aleşi de bancă astfel încât suma fondurilor de siguranţă colectată de la aceştia să poată fi distribuită în mod egal fiecărui client premium;
c. numerelor de cont ale celor selectaţi la punctul b).

Date de intrare

Fişierul text moretime.in conţine pe prima linie n, numărul de clienţi ai băncii iar pe următoarele n linii perechi de numere, separate prin câte un spaţiu, reprezentând numărul contului şi valoarea fondului de siguranţă, pentru fiecare dintre cei n clienţi.

Date de ieșire

Fişierul de ieşire moretime.out va conţine, pe prima linie cp, numărul de clienţi premium, pe a doua linie p, numărul de clienţi premium ce pot fi aleşi de bancă în condiţiile de mai sus iar pe linia a treia, un şir de p numere separate prin câte un spaţiu, reprezentând conturile acestor clienţi. Dacă sunt mai multe soluţii se va scrie una dintre acestea.

Restricții și precizări

• 1 ≤ p ≤ cp ≤ n ≤ 10000
• Moneda Time nu este divizibilă.
• Numerele de cont sunt numere naturale cu cel puţin două şi cel mult cinci cifre.
• Fondurile de siguranţă sunt numere naturale nenule mai mici decât 100000.
• Pentru răspunsuri corecte se acordă punctaje parţiale astfel: a) 30%; a)+b)+c) 100%

Exemplu

moretime.in

moretime.out

3
2
2902 44

Explicație

sunt 3 clienţi premium; pot fi aleşi 2 clienţi premium pentru colectarea fondurilor de siguranţă;
clienţii cu conturile 2902 şi 44 pot fi aleşi pentru că suma fondurilor lor (200+100=300) poate fi împărţită în mod egal celor 3 clienţi premium (fiecare ar primi 100).

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

#include <fstream>

using namespace std;

ifstream fin("moretime.in");
ofstream fout("moretime.out");
long n, m, cp, p, cont[10001], fond[10001];
int r[10001];

int main()
{
    //citirea si construirea vectorilor cu conturi si fonduri ale clientilor premium
    long x, a, y, i, rest, s;
    int u;
    fin>>n;
    for (i=1; i<=n; i++)
    {
        fin>>x>>y;
        a=x;
        u=a%10;
        while (a>9) a/=10;
        if (a==u)    cont[++cp]=x, fond[cp]=y;
    }
    fout<<cp<<'\n';
    //determinarea submultimii de clienti premium pentru care suma fondurilor este divizibila cu cp
    //algoritmul bazat pe principiul cutiei lui Dirichlet
    s=0;
    for (i=1; i<=cp; i++)
    {
        s=s+fond[i];
        if (s%cp==0)
        {
            x=1; y=i;
            break;
        }
        else
        {
            rest=s%cp;
            if (r[rest]==0) r[rest]=i;
            else {
                    x=r[rest]+1;
                    y=i;
                    break;
                 }
        }
    }
    //afisarea conturilor clientilor selectati
    fout<<y-x+1<<'\n';
    for (int i=x; i<=y; i++)
        fout<<cont[i]<<' ';
    fout.close();
    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 #2105 Moretime

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