infoarena

infoarena - concursuri, probleme, evaluator, articole => Teme => Subiect creat de: Muntean Lucian din Mai 19, 2013, 00:56:30


Titlul: Problema clasa IX
Scris de: Muntean Lucian din Mai 19, 2013, 00:56:30
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

Titlul: Răspuns: Problema clasa IX
Scris de: Muntean Lucian din Mai 19, 2013, 01:03:54
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;


Titlul: Răspuns: Problema clasa IX
Scris de: Muntean Lucian din Mai 19, 2013, 01:13:05
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?

Titlul: Răspuns: Problema clasa IX
Scris de: George Marcus din Mai 19, 2013, 07:56:09
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.

Titlul: Răspuns: Problema clasa IX
Scris de: Popa Mihai din Mai 19, 2013, 09:26:25
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).

Titlul: Răspuns: Problema clasa IX
Scris de: Muntean Lucian din Mai 19, 2013, 10:03:44
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

Titlul: Răspuns: Problema clasa IX
Scris de: Muntean Lucian din Mai 19, 2013, 10:05:36
De ce oare n=3 dar sunt 4 greutati pe linia 2?

Titlul: Răspuns: Problema clasa IX
Scris de: Popa Mihai din Mai 19, 2013, 10:15:39
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

Citat
De ce oare n=3 dar sunt 4 greutati pe linia 2?
Unde sunt 4 greutati si unde n = 3?

Titlul: Răspuns: Problema clasa IX
Scris de: Muntean Lucian din Mai 19, 2013, 10:18:02
Datele de intrare din exemplu sunt:
11 3
8 1 3 2

Titlul: Răspuns: Problema clasa IX
Scris de: Muntean Lucian din Mai 19, 2013, 11:14:52

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.


Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines