Scandura

[•wefgef]

Aici se pot pune intrebari legate de problema Scandura de la Runda 1 a concursului Algoritmiada 2009.

Timpul alocat intrebarilor este de 1 ora. Intrebarile vor fi formulate astfel incat sa se poate raspunda cu DA sau NU. In caz contrar sau in cazul in care intrebarea isi gaseste raspuns in enuntul problemei, raspunsul va fi FARA COMENTARII.

[•marcelcodrea]

Dimensiunile finale ale scandurilor sunt distincte doua cate doua ?

[•bogdan2412]

Dimensiunile finale ale scandurilor sunt distincte doua cate doua ?

NU

[•mihai0110]

in urma taierilor, pot ramane bucati in plus?

[•bogdan2412]

in urma taierilor, pot ramane bucati in plus?

NU,

a cumparat o scandura de lungime L egala cu suma lungimilor tuturor scandurilor necesare.

[•marcelcodrea]

Cod:

Scandura de lungime 6 o taie apoi in 2 scanduri de lungme 3. (din exemplu)

Se pot efectua astfel de taieri tinand cont ca

Cod:

aceasta o taie in maxim M bucati diferite (din enunt)

[•bogdan2412]

Lungimile in care se taie nu trebuie sa fie diferite (scuze ca nu se intelege bine din enunt)

[•onoffrei]

cine e M din fisierul de inrare?
toate scandurile au lungimea 10?

[•bogdan2412]

cine e M din fisierul de inrare?

Citeste enuntul mai atent:

El are o masina speciala in care poate introduce o scandura de orice lungime si aceasta o taie in maxim M bucati.

toate scandurile au lungimea 10?

Citeste enuntul mai atent.

[•mihai0110]

testul
4 3
1 2 3 4
are solutie?

[•bogdan2412]

Are solutie. O scandura in taiata e maxim M bucati

[•onoffrei]

ms de raspuns , ai dreptate ,
sa inteleg ca masina poate taia o scandura si in mai mult de 2 bucati odata...

[•wefgef]

Timpul alocat intrebarilor a expirat. Bafta in continuare!

[•onoffrei]

poate cineva sa imi spune ce am gresit de nu a trecut nici un test?
codul este

Cod:

#include <fstream>
#include <stdio.h>

using namespace std;

int main() {
  ifstream fin("scandura.in");
  ofstream fout("scandura.out");
  
  int n, m, NrBucati=0,i=0;
  int * bucati;
  fin>>n;
  bucati=new int[n];
  fin>>m;
  m--;
  int LungTotala=0;
  while (!fin.eof())
  {
        NrBucati++;
        fin>>bucati[NrBucati];
        LungTotala = LungTotala + bucati[NrBucati];
  }
  int cost=0,chop=0,j;
  for (i=NrBucati;i>1;i=i-m)
  {
      cost=cost+LungTotala;
	  if (m>1)
	  {
		chop = 0; 
		for (j=1;j<=m;j++)
		{
			chop=chop + bucati[(i - j)+1];
			//printf("chop(%d)",chop);
		}
	  }
	  else 
	  {
		chop=bucati[i];
	  }
      LungTotala=LungTotala-chop;
	  //printf("cutt lt(%d)\n",LungTotala);
  }
  //printf("\ncost(%d)",cost);
  //system("pause");
  fout<<cost;
  return 0;  
}

[•octav]

onofrei: ai facut o rezolvare Greedy. Incearca testul:

Cod:

4 2
1 1 1 1

Raspunsul cu algoritmul tau cred ca o sa fie 4 + 3 + 2 = 9, raspunsul corect e 4 + 2 + 2 = 8 (tai in jumatate bucata initiala si apoi fiecare bucata din nou in jumatate).

Intrebarea mea e de ce algoritmul la care m-am gandit si eu si mai multi se pare, pica jumatate din teste...

[•bogdan2412]

Daca ai facut huffman si iei 35 incearca testul N=6 M=3 si 1 2 3 4 5 6. La primul pas nu trebuie sa alegi tot timpul M (se pot adauga cateva 0-uri pana cand obtii un arbore complet cu huffman). Probabil ca-ti da 42 si tb sa dea 34

[•emy2704]

Programul asta ce are de nu merge?

Cod:

#include<stdio.h>
int main()
{
long l,lpart,efort=0,m,n,i,a,p[1000000],rest;
FILE *fin,*fout;
fin=fopen("scandura.in","r");
fscanf(fin,"%ld %ld",&n,&m);
for(i=1;i<=n;i++)
{
fscanf(fin,"%ld",&a);
efort+=a;
p[i]=a;
}
l=efort;
while(n!=1)
{
for(i=0;i<=m-2;i++)
lpart=l-p[n-i];
rest=p[n-m+2];
efort+=rest;
n=n-m+1;
}
fout=fopen("scandura.out","w");
fprintf(fout,"%ld",efort);
fclose(fin);
fclose(fout);
return 0;
}

Editat de admin: Foloseste tagul code cand postezi surse.

[•onoffrei]

ms pt raspuns, 
cum pot vedea si alte rezolvari?

[•octav]

Bogdan Tataroiu:
Da, ai dreptate. Pacat totusi ca au fost grupate ultimele teste (cele mari). Asa nu s-a facut diferenta intre cine a rezolvat problema incorect si cine a rezolvat-o incorect si ineficient

Sandu Octav-Emilian:
e tot Greedy, citeste reply-ul meu precedent.

[•onoffrei]

Programul asta ce are de nu merge?
long l,lpart,efort=0,m,n,i,a,p[1000000],rest;
//p este prea mare nu cred ca ai atata memorie

for(i=0;i<=m-2;i++)
lpart=l-p[n-i];
rest=p[n-m+2];
//aici  se introduce un index negativ in interogarea vectorului
efort+=rest;
n=n-m+1;
}

[•wefgef]

Pentru ca nu e bun. Asteapta pana se vor publica solutiile oficiale si te vei lamuri de ce rezolvarile pe care le postezi sunt proaste.