Liceul Naţional Anonim (LNA) este invitat să participe la olimpiada de matematică-română cu o echipă formată din m elevi. La această olimpiadă elevii lucrează în echipă şi trebuie să rezolve două subiecte: unul de română şi altul de matematică.
Au fost testaţi şi punctaţi la cele două materii n elevi, numerotaţi de la 1 la n. Aşa cum era de aşteptat, în general, elevii buni la matematică s-au dovedit cam slăbuţi la română şi viceversa.
Pentru a maximiza şansele de câştig ale echipei LNA, directorul a decis să trimită m elevi dintre cei n elevi testaţi, astfel încât diferenţa în modul dintre suma punctajelor de la limba română ale elevilor din echipă şi suma punctajelor la matematică ale elevilor din echipă să fie minimă. Dacă există mai multe echipe de elevi care îndeplinesc condiţia precedentă, va fi selectată dintre acestea o echipă pentru care suma tuturor notelor să fie maximă.

Cerința

Scrieţi un program care să determine în conformitate cu decizia directorului, diferenţa în modul dintre suma punctajelor de la limba română ale elevilor din echipa LNA şi suma punctajelor la matematică ale elevilor din echipă, precum şi suma tuturor punctajelor elevilor din echipa LNA.

Date de intrare

În fişierul de intrare materom.in se află pe prima linie numerele naturale n şi m separate printr-un spaţiu, având semnificaţia din enunţ.
Pe fiecare dintre următoarele n linii se află două numere naturale separate printr-un spaţiu. Mai exact linia i din fişier (i=2, n+1) conţine mi ri, unde mi este punctajul obţinut la matematică, iar ri este punctajul obţinut la limba română de elevul i-1.

Date de ieșire

Fişierul de ieşire materom.out conţine două linii. Pe prima linie se va afişa diferenţa (în modul) dintre suma punctajelor de la limba română ale elevilor din echipă şi suma punctajelor la matematică ale elevilor din echipă. Pe cea de a doua linie se va afişa suma punctajelor elevilor selectaţi în echipa LNA.

Restricții și precizări

1 ≤ m < 20
1 ≤ n ≤ 500
m ≤ n
0 ≤ mi,ri ≤ 20

Exemplu

materom.in

materom.out

2
10

Explicație

Dintre cei 4 elevi trebuie să selectăm 2. Avem 6 posibilităţi, dintre care 3 au diferenţa (în modul) dintre suma notelor la matematică şi suma notelor la română 2.
Acestea sunt:
– (1, 2) pentru care suma punctajelor este 8.
– (1, 4) pentru care suma punctajelor este 10.
– (2, 4) pentru care suma punctajelor este 8.
Alegem combinaţia 1 4 deoarece are suma maximă.

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

program cna;
const nmax=200;
      nota=21;
      grup=19;
var mat,rom:array[0..nmax] of integer;
    l,s:array[0..grup,0..2*nota*grup+1] of integer;
    sol:set of byte;{solutia}
 n,m,suma,diferenta,sm,sr:integer;
procedure citire;
var f:text;i:byte;
begin
 assign(f,'materom.in');reset(f);
 readln(f,n,m);
 for i:=0 to n-1 do readln(f,mat[i],rom[i]);
 close(f);
end;
procedure rezolva;
var i,j,k,p,p2,v:integer;
begin
for i:=0 to m do
 for j:=0 to 2*nota*m+1 do l[i,j]:=-1;
s:=l;{rez. pt. un elev}
for i:=0 to n-1 do
  if mat[i]+rom[i]>s[0,m*nota+mat[i]-rom[i]] then
   begin
    l[0,m*nota+mat[i]-rom[i]]:=i;
    s[0,m*nota+mat[i]-rom[i]]:=mat[i]+rom[i];
   end;
{restul}
for j:=0 to m-2 do
 for k:=0 to 2*nota*m-1 do
  if l[j,k]>=0 then
    for i:=0 to n-1 do
     if s[j+1,k+mat[i]-rom[i]]<s[j,k]+mat[i]+rom[i] then
      begin
       p2:=k;p:=j;{cautam daca l-am mai folosit}
       while (p>=0)and(l[p,p2]<>i)do
        begin
         p2:=p2-(mat[l[p,p2]]-rom[l[p,p2]]);
         p:=p-1;
        end;
       {daca nu il folosim}
       if p<0 then
        begin
          l[j+1,k+mat[i]-rom[i]]:=i;
          s[j+1,k+mat[i]-rom[i]]:=s[j,k]+mat[i]+rom[i];
        end;
      end;
    {determinare diferenta minima}
    v:=nota*m+1;
    for i:=0 to nota*m do
     if (s[m-1,nota*m+i]>=0) or(s[m-1,nota*m-i]>=0) then
      begin
       if s[m-1,nota*m+i]>s[m-1,nota*m-i] then v:=nota*m+i
                                          else v:=nota*m-i;
       break;
      end;
     {det solutie}
     sol:=[];sm:=0;sr:=0;
     for j:=m-1 downto 0 do
      begin
       sol:=sol+[l[j,v]+1];
       sm:=sm+mat[l[j,v]];
       sr:=sr+rom[l[j,v]];
       v:=v-(mat[l[j,v]]-rom[l[j,v]]);

      end;
end;
procedure scrie;
var i:byte;f:text;
begin
assign(f,'materom.out');rewrite(f);
{calculeaza diferenta}

{calculeaza suma}
suma:=sr+sm;
diferenta:=abs(sr-sm);
writeln(f, diferenta);
writeln(f, suma);
close(f);
end;

BEGIN
citire;
rezolva;
scrie;
END.

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 #2544 materom

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