3. HOI, 2. svibnja 1997. ZADATAK 1 - LJUDI 50 bodova Za zadanu skupinu ljudi treba naći najveći broj P takav da u toj skupini postoji grupa od P ljudi u kojoj se svake dvije osobe međusobno poznaju i najveći broj N takav da u skupini postoji grupa od N ljudi u kojoj se nikoje dvije osobe međusobno ne poznaju. Pretpostavlja se da se osobe koje imaju zajedničkog poznanika također uzajamno poznaju. ULAZNI PODACI Ulazna datoteka s imenom LJUDI.DAT u svojoj prvoj liniji sadrži prirodni broj S (broj osoba u zadanoj skupini ljudi) koji nije veći od 2500. U idućih S linija se nalaze imena tih osoba, po jedno u svakom retku; u različitim linijama se nalaze različita imena. Duljina svakog imena je najviše 20 znakova. Nakon zadnjeg imena slijedi linija s prirodnim brojem P (manjim ili jednakim od 12,000) i iza nje P linija od kojih svaka sadrži dva različita imena razdvojena točno jednim razmakom. Svako ime u tim parovima je jedno od S imena ljudi iz zadane skupine. Svaki par označava međusobne poznanike, tj. dvoje ljudi od kojih svaki poznaje onog drugog. IZLAZNI PODACI Program mora na ekran ispisati tražene brojeve ovako : Broj clanova u najvecoj grupi medjusobnih poznanika : 58 Broj clanova u najvecoj grupi medjusobnih nepoznanika : 12 PRIMJER LJUDI.DAT 6 borna zomberle mirko slavko kresimir tomislav 4 tomislav kresimir kresimir zomberle borna zomberle mirko slavko Ispis na ekran Broj clanova u najvecoj grupi medjusobnih poznanika : 4 Broj clanova u najvecoj grupi medjusobnih nepoznanika : 2 Program mora generirati rješenje unutar 10 sekundi. Program snimiti pod imenom LJUDI.C ili LJUDI.PAS i LJUDI.EXE u direktorij C:ĐDMIHĐLJUDI i na disketu. 3. HOI, 2. svibnja 1997. ZADATAK 1 - LJUDI 50 bodova Za zadanu skupinu ljudi treba naći najveći broj P takav da u toj skupini postoji grupa od P ljudi u kojoj se svake dvije osobe međusobno poznaju i najveći broj N takav da u skupini postoji grupa od N ljudi u kojoj se nikoje dvije osobe međusobno ne poznaju. Pretpostavlja se da se osobe koje imaju zajedničkog poznanika također uzajamno poznaju. ULAZNI PODACI Ulazna datoteka s imenom LJUDI.DAT u svojoj prvoj liniji sadrži prirodni broj S (broj osoba u zadanoj skupini ljudi) koji nije veći od 2500. U idućih S linija se nalaze imena tih osoba, po jedno u svakom retku; u različitim linijama se nalaze različita imena. Duljina svakog imena je najviše 20 znakova. Nakon zadnjeg imena slijedi linija s prirodnim brojem P (manjim ili jednakim od 12,000) i iza nje P linija od kojih svaka sadrži dva različita imena razdvojena točno jednim razmakom. Svako ime u tim parovima je jedno od S imena ljudi iz zadane skupine. Svaki par označava međusobne poznanike, tj. dvoje ljudi od kojih svaki poznaje onog drugog. IZLAZNI PODACI Program mora na ekran ispisati tražene brojeve ovako : Broj clanova u najvecoj grupi medjusobnih poznanika : 58 Broj clanova u najvecoj grupi medjusobnih nepoznanika : 12 PRIMJER LJUDI.DAT 6 borna zomberle mirko slavko kresimir tomislav 4 tomislav kresimir kresimir zomberle borna zomberle mirko slavko Ispis na ekran Broj clanova u najvecoj grupi medjusobnih poznanika : 4 Broj clanova u najvecoj grupi medjusobnih nepoznanika : 2 Program mora generirati rješenje unutar 10 sekundi. Program snimiti pod imenom LJUDI.C ili LJUDI.PAS i LJUDI.EXE u direktorij C:\DMIH\LJUDI i na disketu.