Enunt

Fetiţele din grupa mare de la grădiniţă culeg flori şi vor să împletească coroniţe pentru festivitatea de premiere. În grădină sunt mai multe tipuri de flori. Fiecare dintre cele n fetiţe culege un buchet având acelaşi număr de flori, însă nu neapărat de acelaşi tip. Pentru a împleti coroniţele fetiţele se împart în grupe. O fetiţă se poate ataşa unui grup numai dacă are cel puţin o floare de acelaşi tip cu cel puţin o altă fetiţă din grupul respectiv.

Cerința

Fiind dat un număr natural n reprezentând numărul fetiţelor şi numărul natural k reprezentând numărul de flori dintr-un buchet, să se determine grupele care se formează.

Date de intrare

Fişierul de intrare flori2.in conţine pe prima linie, separate printr-un spaţiu, numerele naturale n şi k, reprezentând numărul de fetiţe şi respectiv numărul de flori din fiecare buchet. Fiecare dintre următoarele n linii conţine, pentru fiecare fetiţă, câte k valori separate prin câte un spaţiu reprezentând tipurile de flori culese.

Date de ieșire

Fişierul de ieşire flori2.out va conţine pe fiecare linie câte o grupă formată din numerele de ordine ale fetiţelor separate prin câte un spaţiu, în ordine crescătoare, ca în exemplu.

Restricții și precizări

1<=n<=150
1<=k<=100
Tipul unei flori este un număr întreg din intervalul [0,100].
Într-o grupă numerele de ordine ale fetiţelor trebuie date în ordine strict crescătoare.
În fişierul de ieşire grupele vor fi afişate în ordinea crescătoare a numărului de ordine al primei fetiţe din grupă.

Exemplu

flori2.in

flori2.out

1 3 4 
2
5

Explicație

Fetiţele 1 şi 3 au cules amândouă flori de tipul 1, iar fetiţele 1 şi 4 au cules amândouă flori de tipurile 2, 3 şi 4, deci toate cele trei fetiţe (1, 3, 4) se vor afla în aceiaşi grupă. Fetiţele 2 şi 5 vor forma fiecare câte o grupă deoarece nu au cules flori de acelaşi tip cu nici una dintre celelalte fetiţe.

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

#include<iostream>
#include<cstdio>
FILE *f=fopen("flori2.in","r");
FILE *g=fopen("flori2.out","w");

int n,k,a[150][150];

int irelj(int i,int j) //verifica daca fata i e in relatie cu j(au cel putin o floare in comun)
{int u,v;
 for(u=1;u<=a[i][0];u++)   //a[i][0] e numarul de elemente pe linia i
    for(v=1;v<=a[j][0];v++)
      if (a[i][u]==a[j][v])
         return 1;
 return 0;
}
int apartine(int val,int linie) //caut val in multimea de pe linia linie
{int j,lg=a[linie][0];
 for(j=1;j<=lg;j++)
    if (val==a[linie][j])
        return 1;
 return 0;
}

void reuneste(int i,int j) //reuneste in linia i linia j
{int u;
 for(u=1;u<=a[j][0];u++)
    if(!apartine(a[j][u],i))
      {a[i][0]++;
        a[i][ a[i][0] ]=a[j][u];
      }
}

int main()
{int viz[150],i,j,val,ok;
 fscanf(f,"%d %d",&n,&k);
 for(i=1;i<=n;i++)
  for(j=1;j<=k;j++)
    {fscanf(f,"%d",&val);
     if(!apartine(val,i))
        {a[i][0]++;  //pe prima coloana am nr. de tipuri distincte de flori
         a[i][ a[i][0] ]=val;  //in multimea de pe linia i am tipurile distincte de flori al fetitei i
        }
    }
 for(i=1;i<=n;i++)
  viz[i]=i;     //initial exista n grupe
 for(i=1;i<=n;i++)
  {ok=0;
    if(a[i][0])
    {
     for(j=i+1;j<=n;j++)
        if(irelj(i,j))
            {
                viz[j]=viz[i];  //j trebuie sa ajunga in grupa cu i
                reuneste(i,j);  //reunesc in linia i linia j
                a[j][0]=0;//consider ca in multimea j am 0 elemente acuma
                ok=1;
                }
            }
     if (ok) i--;//faptul ca am reunit in i cel putin o multime j implica sa continui cu aceeasi linie i
                     //daca as lasa i sa se incrementeze conform for-ului,ar gresi in sensul ca
                     //pt. i rel j si i nu e in rel cu k si j rel k
                     //ar pune j in grupa i dar k ar ajunge in alta grupa
  }


 for(i=1;i<=n;i++)
    if(viz[i])
     {fprintf(g,"%d ",i);
      for(j=i+1;j<=n;j++)
    if(viz[i]==viz[j])
        {fprintf(g,"%d ",j);
         viz[j]=0;       //ca sa nu mai fie prelucrat
        }
      fprintf(g,"\n");
     }
 fclose(g);
return 0;
}

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 #1378 Flori2

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