fbpx

Problema #1378 – Flori2 – Rezolvari PBInfo

de Mihai-Alexandru

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

5 4
1 2 3 4
5 6 9 6
1 1 1 1 
2 4 4 3
7 7 7 7

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.

#include<iostream>
#include<stdio.h>
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);
}
Comentarii

S-ar putea sa iti placa