Problem z zadaniem Impreza.
Witam mam problem z poniższym zadaniem.
"Chcesz zorganizować dużą imprezę dla swoich znajomych. Niestety niektórzy z nich się nie lubią — zaproszenie
nielubiącej się pary osób do wspólnej zabawy zakończy się popsuciem atmosfery na imprezie wszystkim gościom.
Wiesz którzy znajomi się nie lubią. Chcesz wybrać taki podzbiór znajomych, aby był on jak największy
(im huczniejsza impreza, tym lepiej!) oraz aby wszyscy znajomi w tym podzbiorze się lubili.
Wejście:
W pierwszym wierszu standardowego wejścia znajduje się liczba N (3 ≤ N ≤ 18), oznaczająca liczbę znajomych.
W i-tym z kolejnych N wierszy znajduje się opis relacji i-tego znajomego w postaci ciągu N znaków 0 i 1.
j-ty z tych znaków oznacza w jakich stosunkach pozostają znajomi i, j — jeśli 0, to się lubią, a jeśli 1, to się
nie lubią. Można przyjąć, że każda osoba lubi samą siebie oraz że jeśli dana osoba lubi (lub nie) inną, to tamta
odwzajemnia uczucie.
Wyjście:
W pierwszym wierszu standardowego wejścia wypisz jedną liczbę, oznaczającą ile najwięcej lubiących się znajomych
można zaprosić na imprezę. W drugim wierszu wypisz listę tych znajomych w postaci liczb z przedziału
od 1 do N, oddzielonych pojedynczą spacją. Jeśli jest wiele poprawnych odpowiedzi, wypisz leksykograficznie
minimalną."
Napisałem program i sprawdzałem wyniki dla kilku przykładów.
np:
n = 5
0 1 0 1 1
1 0 0 0 0
0 0 0 1 1
1 0 1 0 0
1 0 1 0 0
lub
n = 6
0 1 1 0 1 1
1 0 0 0 0 0
1 0 0 1 1 1
0 0 0 0 0 0
1 0 1 0 0 0
1 0 1 0 0 0
Wyniki jakie podał program był poprawne. (Wynosiły odpowiednio: 3, 2 4 5 oraz 4, 2 4 5 6)
Lecz gdy dałem program do sprawdzenia, komputer podał mi taką informacje:
1 wiersz 1: wczytano '12', a oczekiwano '6'
2 wiersz 1: wczytano '7', a oczekiwano '5'
3 wiersz 1: wczytano '5', a oczekiwano '3'
4 wiersz 1: wczytano '6', a oczekiwano '4'
5 wiersz 1: wczytano '2', a oczekiwano '3'
6 wiersz 1: wczytano '2', a oczekiwano '1'
7 wiersz 1: wczytano '4', a oczekiwano '3'
8 wiersz 1: wczytano '3', a oczekiwano '2'
9 wiersz 1: wczytano '11', a oczekiwano '7'
10 wiersz 1: wczytano '4', a oczekiwano '3'
11 wiersz 1: wczytano '9', a oczekiwano '6'
12 wiersz 1: wczytano '2', a oczekiwano '1'
13 wiersz 2: wczytano '2', a oczekiwano '3'
14 wiersz 1: wczytano '5', a oczekiwano '4'
15 wiersz 1: wczytano '8', a oczekiwano '5'
16 wiersz 1: wczytano '6', a oczekiwano '4'
17 wiersz 1: wczytano '7', a oczekiwano '5'
19 wiersz 1: wczytano '16', a oczekiwano '9'
20 wiersz 1: wczytano '7', a oczekiwano '5'
21 wiersz 1: wczytano '8', a oczekiwano '5'
22 wiersz 1: wczytano '6', a oczekiwano '4'
Wynik był zgodny tylko w przykładzie 18.
Oto kod mojego programu:
#include <iostream>
using namespace std;
int T[ 20 ][ 20 ];
bool pierwsza = true, znalezione = false;
int ZAPROSZENI[ 20 ];
bool czy_lubi( int kto, int ktora )
{
for( int i = 1; i < ktora; ++i )
if( T[ kto ][ ZAPROSZENI[ i ] ] == 1 )
return false;
return true;
}
void wybierz_gosci( int kto, int limit, int n, int ktora )
{
while( n > 0 ) {
if( znalezione )
return;
else if( pierwsza )
{
ZAPROSZENI[ ktora ] = kto;
pierwsza = false;
for( int i = 1; i < n - limit; ++i )
wybierz_gosci( kto + i, limit - 1, n, ktora + 1 );
pierwsza = true;
return;
}
else if( !pierwsza && limit > 1 )
{
if( !czy_lubi( kto, ktora ) )
{
if( kto + limit <= n )
wybierz_gosci( kto + 1, limit, n, ktora ), kto++;
else
return;
}
else
{
ZAPROSZENI[ ktora ] = kto;
wybierz_gosci( kto + 1, limit - 1, n, ktora + 1 );
kto++;
}
}
else
{
if( !czy_lubi( kto, ktora ) )
{
if( kto + limit <= n )
wybierz_gosci( kto + 1, limit, n, ktora ), kto++;
else
{
return;
}
}
else
{
ZAPROSZENI[ ktora ] = kto;
cout << ktora << endl;
for( int i = 1; i <= ktora; ++i )
cout << ZAPROSZENI[ i ] << " ";
znalezione = true;
}
}
} }
int main()
{
int n, wyn = 1;
cin >> n;
for( int i = 1; i <= n; ++i )
for( int j = 1; j <= n; ++j )
cin >> T[ i ][ j ];
for( int i = n; i > 0; --i )
for( int j = 1; j + i <= n + 1; ++j )
wybierz_gosci( j, i, n, 1 );
return 0;
}
Czy widzicie jakiś błąd powodujący tą niezgodność w moim programie?
PS:
Opiszę tutaj pokrótce jak moj program działa:
Sprawdza po kolei czy czy można zaprosić N osób. Jeżeli nie to powtarza czynność dla N-1 itd.
Podczas sprawdzania bierze pierwszą osobę i sprawdza czy może zaprosić w tedy następne osoby.
Program kończy działanie kiedy znajdzie największą liczbę < N osób które może zaprosić.