Tävlingsprogrammering/Uppgifter/Kontaktförmedlingen
Kontaktförmedlingen - Uppgift 6 - Onlinekvalet till PO 2007
En kontaktförmedling har specialiserat sig på att para ihop människor med avseende på hur många intressen personerna har gemensamt. Personernas kön spelar däremot ingen roll. I en förmedlingsomgång deltar n personer. Var och en av dessa får fylla i ett frågeformulär med m stycken ja/nej-frågor av typen "Tycker du om katter?", "Programmerar du för nöjes skull?", etc. Målet är att varje person ska paras ihop med den av de andra personerna som har maximal överensstämmelse med de egna svaren, eller, om det finns flera som har maximal överensstämmelse, vem som helst av dessa.
Tyvärr är detta inte alltid möjligt. Två personer kanske båda passar bäst ihop med en tredje, medan denna tredje egentligen passar bäst ihop med någon helt annan person. Kontaktförmedlingen har dock kommit på en lösning på detta problem. Man väljer ut en mindre grupp personer och ser till att alla personerna i denna grupp paras ihop två och två så att önskemålet att alla får sin optimala partner bland personerna i den mindre gruppen tillgodoses. Då är dessa glada och nöjda eftersom de aldrig får veta att det kanske fanns någon person utanför den utvalda gruppen som egentligen passade ännu bättre.
Kontaktförmedlingen får betalt per antal nöjda kunder och man vill därför naturligtvis göra den utvalda gruppen så stor som möjligt. Du ska skriva ett program som beräknar det största antalet personer som kan ingå i gruppen.
Indata
På första raden står två heltal n och m, (4 ≤ n ≤ 20 och 10 ≤ m ≤ 100), där n är antalet personer och m är antalet frågor i formuläret. Därefter följer n rader, som var och en ger svaren för en person. Varje rad består av en sträng med m tecken som kan vara antingen j eller n. Det första tecknet anger svaret på första frågan, det andra tecknet anger svaret på andra frågan o.s.v. Alla personerna får naturligtvis frågorna i samma ordning.
Utdata
Programmet ska skriva ut ett heltal: det maximala antalet personer som kan väljas ut och paras ihop enligt ovanstående kriterium. Observera att talet alltid måste vara jämnt.
Exempel: Indata
5 10
njjjnnnnnj
nnjnnnnnnn
jnjjnnjjnn
njjnnjjjjn
njnjjnjnjj
Exempel: Utdata
4
Exempel: Förklaring
Låt oss kalla personerna A, B, C, D och E i den ordning de ges i indata. Det enda sättet att få fyra nöjda kunder är att para ihop A med E (6 identiska svar) och C med D (5 identiska svar). Detta kan man göra trots att A egentligen passar bäst ihop med B (7 identiska svar), för B finns inte med i den utvalda gruppen. Observera att om man skulle para ihop A och B så skulle det inte bli något mer par eftersom C föredrar B, och E föredrar A.