Problema clasa IX

[•ilgrandere]

Salutare!
Vreau sa cer indicatii/ajutor pentru problema de mai jos.
N-am nici o idee de cum as putea sa adun de fiecare dac aun numar cat mai mare de obiecte, iar cerinta b, nu imi este prea clara.
Va rog sa ma ajutati.
   
Intr-un depozit sunt N saci cu alimente. Pentru fiecare sac se cunoaște greutatea. Avem la dispoziție un camion care poate transporta o greutate maximă G.
Să se determine:
a) Numărul maxim de saci care pot fi transportați cu ajutorul camionului la o singură cursă.
b) Să se verifice dacă modalitatea de transport a unui număr maxim de saci la o singură cursă este unică.

Date de intrare:
De la tastatură se citesc în ordine:
G – greutatea maximă ce poate fi încărcată în camion,
N – numărul de saci, apoi N numere naturale  care reprezintă greutățile sacilor.
Date de ieșire:
Pe ecran se va afișa mai întâi numărul de la cerința a).
Pe următoarea linie se va afișa mesajul DA dacă există o singură modalitate de a transporta număr maxim de saci la o singură cursă respectiv mesajul NU dacă sunt cel puțin două modalități (două transporturi se consideră distincte dacă există cel puțin un sac pe care îl folosim la un transport și nu îl folosim la celălalt).

Restrictii:
Greutățile sacilor sunt distincte
Există cel puțin un sac cu greutatea ≤ G
2<=n<=20
1<=G<=2*10^9
1<=g<=10^9

[•ilgrandere]

Ma gandeam la cerinta a, sa numar sacii astfel:

Cod:

for i:=1 to n do
    if s[i]<=g div n then k:=k+1;

[•ilgrandere]

La b, oare e atat de simplu? E destul sa calculez greutatea totala a sacilor ca sa-mi dau seama de fiecare daca daca e nevoie de un transport unic?

[•PlayLikeNeverB4]

Sortezi sacii dupa greutate si ii adaugi (incepand cu cei mai usori) in camion cat timp mai e loc. E unica posibilitatea daca nu exista saci care au aceeasi greutate cu ultimul adaugat.

[•mihaipopa12]

Nu cred ca e suficient sa nu existe saci de aceeasi greutate cu ultimul pentru ca solutia sa fie unica.

De exemplu pe testul:

1 2 3 4 cu G = 7 solutia nu este unica.

Conditia corecta pentru solutie unica ar fi v[ x+1 ] - v[ x ] > g_ramas dupa bagarea sacilor de la 1 la x, stiind ca ai putut sa bagi fix primii x saci (al x+1 - lea e primul pe care nu ai mai putut).

[•ilgrandere]

Nu cred ca e suficient sa nu existe saci de aceeasi greutate cu ultimul pentru ca solutia sa fie unica.

De exemplu pe testul:

1 2 3 4 cu G = 7 solutia nu este unica.

mihaipopa12, pentru cerinta b am spus "daca suma tuturor greutatilor este > G atunci solutia nu e unica.", se aplica si la exemplul tau: 1+2+3+4>7 => solutia nu este unica

[•ilgrandere]

De ce oare n=3 dar sunt 4 greutati pe linia 2?

[•mihaipopa12]

Nu cred ca intelegi bine cerinta b.

Solutia nu este unica pe exemplul meu pentru ca exista doua moduri de a baga un numar maxim de saci in camion:
1 2 3 respectiv 1 2 4

De ce oare n=3 dar sunt 4 greutati pe linia 2?

Unde sunt 4 greutati si unde n = 3?

[•ilgrandere]

Datele de intrare din exemplu sunt:
11 3
8 1 3 2

[•ilgrandere]

Sursa finala:

Cod:

var n,i,a,g,aux,b,k:longint;
    ok:boolean;
    s:array[1..1000] of longint;
    f1,f2:text;
Begin
assign(f1,'camion.in');reset(f1);
assign(f2,'camion.out');rewrite(f2);
readln(f1,g,n);
for i:=1 to n do read(f1,s[i]);
b:=0;

repeat
ok:=true;
for i:=1 to n-1 do
    if s[i]>s[i+1] then begin
                        aux:=s[i];
                        s[i]:=s[i+1];
                        s[i+1]:=aux;
                        ok:=false;
                        end;
until ok;

a:=0;
for i:=1 to n do
    if a + s[i]<g then begin
       a:=a+s[i];
       k:=i;
       end;


writeln(f2,k,' ',a);
if (s[k+1]-s[k])>=(g-a) then write(f2,'NU')
                        else write(f2,'DA');
close(f1);
close(f2);
End.