Rezolvare completă PbInfo #2157 Bomboane3

Zeno are n cutii cu bomboane, iar în fiecare cutie se găsește un număr natural nenul de bomboane. Zeno poate împărți bomboanele din toate cutiile colegilor în două moduri: frățește sau diferențiat. Împărțirea frățească se realizează astfel:

  • numărul de colegi care primesc bomboane din fiecare cutie este același (dacă din prima cutie primesc bomboane k colegi și din cutia 2 vor primi tot k colegi, și din cutia 3 tot k colegi etc).
  • bomboanele din fiecare cutie se împart în mod egal între cei k colegi, aceștia primind un număr nenul de bomboane;
  • în final în fiecare cutie trebuie să rămână un număr identic de bomboane (posibil zero) care îi revin lui Zeno. De exemplu dacă n = 3, iar în cutii se găsesc 14, 23 respectiv 17 bomboane, din prima cutie oferă câte 4 bomboane pentru 3 colegi, din a doua cutie câte 7 bomboane pentru 3 colegi, iar din ultima cutie câte 5 bomboane pentru 3 colegi, iar în fiecare cutie rămân 2 bomboane.

Împărțirea diferențiată se realizează în felul următor:

  • dintre colegii care primesc bomboane din aceeași cutie fiecare coleg primește un număr diferit de bomboane (număr nenul), neexistând doi colegi care primesc număr identic de bomboane din aceeași cutie;
  • din fiecare cutie Zeno oferă bomboane unui număr cât mai mare de colegi.
  • diferențele în modul dintre numărul de bomboane primite consecutiv de doi colegi sunt distincte două câte două. De exemplu dacă n = 3, iar în cutii se găsesc 14, 23 respectiv 17 bomboane, bomboanele din prima cutie se pot împărți astfel (3, 4, 6, 1), bomboanele din a doua cutie (6, 2, 7, 1, 3, 4), iar bomboanele din a treia cutie se pot împărți astfel (2, 1, 3, 7, 4).

Cerințe

Cunoscând n numărul de cutii și numărul de bomboane din fiecare cutie să se scrie un program care determină:

a) Numărul maxim de colegi care pot primi bomboane, dacă Zeno alege împărțirea frățească.
b) O modalitate de împărțire a bomboanelor din fiecare cutie, dacă se face împărțirea diferențiată.

Date de intrare

Fișierul de intrare bomboane3.in conține pe prima linie două numere naturale p (numărul cerinței de rezolvat), și n (numărul de cutii), despărțite printr-un spațiu. Pe următoarea linie se găsesc n valori naturale, separate prin câte un spațiu, reprezentând numărul de bomboane din fiecare cutie.

Date de ieșire

Dacă p = 1 se va rezolva numai punctul a) din cerință. În acest caz fișierul de ieșire bomboane3.out va conține o valoare naturală reprezentând numărul maxim de colegi care pot primi bomboane, dacă Zeno alege împărțirea frățească.
Dacă p = 2 se rezolvă numai punctul b). Fișierul de ieșire bomboane3.out va conține n linii. Pe fiecare linie i, prima valoare nri reprezintă numărul maxim de colegi care pot primi bomboane din cutia i, urmată de nri valori separate prin câte un spațiu reprezentând o modalitate de împărțire a bomboanelor din cutia i, dacă Zeno alege împărțirea diferențiată.

Restricții și precizări

  • 1 ≤ p ≤ 2;
  • Dacă p = 1 atunci 1 ≤ n ≤ 10 000 și 1 ≤ numărul de bomboane din cutii ≤ 106.
  • Dacă p = 2 atunci 1 ≤ n ≤ 200 și 1 ≤ numărul de bomboane din cutii ≤ 100 000.
  • Dacă există mai multe soluții se poate afișa oricare.
  • Pentru rezolvarea fiecărei cerințe se acordă 50% din punctaj.

Exemplul 1

bomboane3.in

1 3
14 23 17

bomboane3.out

3

Explicație

Se rezolvă numai punctul a). Numărul maxim de colegi care pot primi bomboane dacă Zeno alege împărțirea frățească e 3.

Exemplul 2

bomboane3.in

2 3
14 23 17

bomboane3.out

4 3 4 6 1
6 6 2 7 1 3 4 
5 2 1 3 7 4

Explicație

Se rezolvă numai punctul b). Din prima cutie pot primi bomboane maxim 4 colegi. O modalitate de împărțire astfel încât fiecare coleg să primească un număr diferit de bomboane, iar diferențele dintre bomboanele primite de doi colegi consecutivi să fie distincte două câte două este (3,4,6,1). Este corectă și soluția (1, 2, 7, 4).

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

#include <iostream>
#include <fstream>
#include <math.h>

using namespace std;

long cmmdc(long a, long b)
{
    while(a!=b)
      if(a>b)
        a=a-b;
      else
        b=b-a;
    return a;
}

int main()
{
    ifstream in("bomboane3.in");
    ofstream out("bomboane3.out");
    int p,n,i,k=0,j,nb;
    long b[10001], c[10001], min, s, r, st, dr;
    in>>p>>n;
    // cout<<n<<endl;
      if(p==1) //cerinta 1
     {
       in>>b[1]; min=b[1];
       for(i=2;i<=n;i++)
         {
           in>>b[i];
           if(b[i]<min)
             min=b[i];
         }
       for(i=1;i<=n;i++)
         b[i]=b[i]-min;
       i=1;
       while(b[i]==0)
         i++;
       k=b[i];
       for(i=2;i<=n;i++)
         if(b[i]!=0)
           k=cmmdc(k,b[i]);
       out<<k;
     }
    else //cerinta 2
     {
        for(i=1;i<=n;i++)
          {
            in>>b[i];
            c[i]=sqrt(2*b[i]);
            if(c[i]*(c[1]+1)>2*b[i])
              c[i]--;
            s=0; j=0;
            do
              { j++; s=s+j; }
            while(s<=b[i]);
            if(s==b[i])
              r=j;
            else
              { s=s-j; j--; r=j+b[i]-s; }
            st=1; dr=j; p=1;
            out<<j<<' ';
            while(st<=dr)
              {
                 if(p==1)
                   out<<1<<' '<<r<<' ';
                 else
                   if(st==dr)
                     out<<st<<' ';
                    else
                       out<<st<<' '<<dr<<' ';
                 st++; dr--; p++;
              }
            out<<endl;
          }
     }
    in.close();
    out.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 #2157 Bomboane3

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