775 Scandura

[•wefgef]

Aici puteti discuta despre problema Scandura.

[•stocarul]

De ce sursa asta i-a 0 pct?

Cod:

#include<stdio.h>
#define infile "scandura.in"
#define outfile "scandura.out"
#define nmax 1000*1000+1
long v[nmax]; //vom salva toate lungimile de scandura ce trebuie obtinute (in ordine crescatoare)
long n; //numarul de lungimi de scanduri
long m; //numarul maxim de bucati ce se pot obtine dintr-o data
long long l; //lungimea totala a scandurii

void citire(long v[nmax], long *n, long *m, long long *l)
	{
	long i;
	scanf("%ld %ld",n,m);
	for(i=1;i<=*n;i++) //luam fiecare lungime ce trebuie obtinuta
		{
		scanf("%ld",&v[i]); //citim lungimea
		*l+=v[i]; //adaugam la lungimea totala
		}
	}

long long calculeaza_efort(long v[nmax], long n, long m, long long l)
	{
	long i;
	long long e=0; //aici vom calcula efortul minim
	while(l>v[1]) //cat timp mai avem de taiat din scandura
		{
		e+=l; //adaugam costul operatiei, adica efortul
		for(i=1;i<m && n>0;i++,n--) //se rezolva m-1 bugati
			l-=v[n];
		}
	return e;
	}

int main()
{
freopen(infile,"r",stdin);
freopen(outfile,"w",stdout);

citire(v,&n,&m,&l); //citim datele si calculam lungimea totala a scandurii
printf("%lld\n",calculeaza_efort(v,n,m,l));

fclose(stdin);
fclose(stdout);
return 0;
}

[•Pepelea_Flaviu]

pt ca nu-i buna rezolvarea....de-aia

pt testul:
4
1 1 1 1 tie iti da 9....iar rezultatul corect e 8
             

[•stocarul]

pt ca nu-i buna rezolvarea....de-aia

pt testul:
4
1 1 1 1 tie iti da 9....iar rezultatul corect e 8
             

Daca te refereai pentru testul :
4 2
1 1 1 1

Se efectueaza o taiere cu costul de 4, si se obtin doua scanduri de lungime 1 si 3.
Se efectueaza o taiere cu costul de 3, si se obtin doua scanduri de lungime 1 si 2.
Se efectueaza o taiere cu costul de 2, si se obtin doua scanduri de lungime 1.
deci se obtin 4 scanduri de lungime 1, cu costul 4+3+2=9.

Am inteles cumva eu gresit enuntul?

[•gabitzish1]

Pentru testul

Cod:

4 2
1 1 1 1

Se face o taiere cu costul 4 si se obtin 2 scanduri de lungime 2 fiecare.
Se taie fiecare scandura de lungime 2 (cost 2 * 2) si se obtin 4 scanduri de lungime 1.
deci se obtin 4 scanduri de lungime 1 cu costul 4 + 2 + 2 = 8.

[•crawler]

nu inteleg de ce nu imi merg testele 3 si 4 nici cu brut ... este vreo sansa sa se puna pe forum testul 3 sau 4 ?

[•wefgef]

Pai ce brut ai facut?

[•stocarul]

Am facut si eu o rezolvare cu Codul lui Huffman...

Am o lista initiala (cu nodurile cu lungimile din fisierul de intrare)
Si o lista in care adaug nodurile care se formeaza....

Cat timp in cele doua liste am mai mult de un nod....
  - creez un nod nou
  - selectez k=max(m,numarul_nodurilor_din_liste) noduri. (nodurile se selecteaza ca un fel de interclasare.....adica se selecteaza intotdeauna minimul din capatul celor doua liste)
  - pentru fiecare din cele k noduri, adaug costul la nodul creeat nou
  - costul minim total primeste costul care s-a adaugat la noul nod
  - adaug nodul cel nou in lista a 2-a.

Ce anume nu fac bine in acest algoritm?....primesc doar 35 pct 

[•Mishu91]

Vezi cat iti da pe testu

Cod:

8 4
1 1 2 2 2 3 3 3

[•stocarul]

Imi da 34

[•Mishu91]

27 tre sa dea

[•stocarul]

Imi poti explica te rog care sunt taieturile?

[•Mishu91]

Pai la inceput am o scandura de lungime 17, pe care o tai in 3 de 3 si una de 8.
Aia de 8 o tai in 4 de 2.
Una de 2 o tai in 2 de 1.

2 + 8 + 17 = 27   

[•stocarul]

Multumesc mult pentru raspunsuri...
Am observat ce greseam )
Nu adaugam nodurile de cost 0.......

[•ooctav]

Imi poate zice cineva daca este un caz special pe testele 16 si 18 ?