Majoritatea copiilor sunt sociabili și relaționează ușor cu cei de vârsta lor dar sunt și copii mai timizi sau mai puțin atrași de activitățile de grup. În urma studierii comportamentului unui eșantion de n copii, s-a stabilit, pentru fiecare doi copii dacă relaționează sau nu. Pentru serbarea de sfârșit de an, s-a propus realizarea unei scenete și este necesară selectarea unei grupe cât mai numeroase de micuți dar fără a depăși k, numărul maxim de personaje. Rolurile presupun interacțiunea fiecărui copil selectat cu toți ceilalți mici actori care joacă în scenetă.

Cerința

Cunoscând n – dimensiunea eșantionului studiat, capacitatea fiecărui copil de a relaționa cu ceilalți și k – numărul maxim de personaje din scenetă, să se determine cel mai mare număr de copii care pot fi implicați în serbare, știind ca fiecare dintre aceștia trebuie să relaționeze cu toți ceilalți copii din scenetă.

Date de intrare

Fișierul de intrare serbare2.in conţine n + 1 linii şi are structura:
n k
a11 a12 ... a1n
a21 a22 ... a2n
...
an1 an2 ... ann

Unde n este dimensiunea eșantionului; k este numărul maxim de personaje
a[i,j] = 1, dacă copilul i relaționează cu copilul j sau
a[i,j] = 0, în caz contrar

Date de ieșire

Fișierul de ieșire serbare2.out conține o singură linie pe care se va scrie numărul maxim de copii care vor selectați pentru a juca în scenetă.

Restricții și precizări

2 ≤ n ≤ 100
2 ≤ k ≤ 10
Se consideră că un copil NU relaționează cu el însuși.

Exemplul 1:

serbare2.in

serbare2.out

Exemplul 2:

serbare2.in

serbare2.out

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

#include <bits/stdc++.h>
using namespace std;

const int MAX=100;
int G[MAX][MAX],n,k,i,j,S[MAX],maxk=0;
int ok(int i)
{
    if(i>1&&S[i-1]>=S[i])
        return 0;
    for(j=1;j<i;j++)
        if(G[S[i]][S[j]]==0)
            return 0;
    return 1;
}
int main()
{
    ifstream fin("serbare2.in");
    ofstream fout("serbare2.out");
    fin>>n>>k;
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            fin>>G[i][j];
    i=1;
    S[i]=0;
    while(i>0)
        if(S[i]<n)
        {
            S[i]++;
            if(ok(i))
            {
                if(k==i)
                {
                    maxk=i;
                    break;
                }
                else
                {
                    maxk=maxk<i?i:maxk;
                    S[++i]=0;
                }
            }
        }
        else i--;
    fout << maxk << "\n";
    fin.close();
    fout.close();
    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 #2706 serbare2

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