Programmeringsolympiadens onlinekval 2019

Start

2018-10-15 21:00 UTC

Programmeringsolympiadens onlinekval 2019

End

2018-12-02 21:00 UTC
The end is near!
Contest is over.
Not yet started.
Contest is starting in -97 days 3:31:06

Time elapsed

1152:00:00

Time remaining

0:00:00

Problem C
Skolavslutningen

Skolledningen har stött på ett problem med den kommande skolavslutningen, ett problem som de hoppas att du kan hjälpa dem att lösa. Under skolavslutningen kommer eleverna stå uppställda i $N$ rader med $M$ elever i varje. Ledningen vill att avslutningen ska vara så färgglad som möjligt och kommer därför att dela ut hattar i olika färger till eleverna.

För att uppställningen ska se fin ut är det viktigt att alla elever i samma kolumn har samma hattfärg. För att ingen ska känna sig utanför är det också viktigt att alla elever i samma klass har samma hattfärg. Rad och kolumn för varje elev är redan bestämt, men inte hattfärg. Ledningen behöver din hjälp med att tilldela hattfärger till eleverna så att avslutningen blir så färgglad som möjligt.

Skriv ett program som, givet hur eleverna kommer vara uppställda på avslutningen, beräknar det maximala antalet unika hattfärger som kan tilldelas eleverna.

Indata

Den första raden innehåller tre heltal $N$, $M$ ($1 \leq N, M \leq 700$) och $K$ ($1 \leq K \leq 26$) – antalet rader, antalet kolumner och antalet klasser.

De följande $N$ raderna har $M$ tecken i varje och beskriver hur eleverna kommer vara uppställda på avslutningen. Tecknet på rad $i$, kolumn $j$ är en stor bokstav mellan A och den $K$:e bokstaven i alfabetet – den klass som eleven på rad $i$, kolumn $j$ går i. Det finns garanterat minst en elev från varje klass.

Utdata

Skriv ut ett heltal – det maximala antalet unika hattfärger som kan tilldelas eleverna så att alla elever i samma kolumn, respektive samma klass, har samma hattfärg.

Poängsättning

Grupp

Poäng

Gränser

$1$

$15$

$N, M \leq 5 $

$2$

$15$

$K = 2$

$3$

$35$

$N, M \leq 50 $

$4$

$35$

Inga ytterligare begränsningar.

Förklaring av exempelfall

I första exempelfallet står en från klass A och en från klass B i den andra kolumnen. Då båda dessa elever måste ha samma färg på hatten måste hela klass A ha samma färg som hela klass B. Slutsatsen är att alla elever på avslutningen måste ha samma färg, vilket gör att svaret blir $1$.

I andra exempelfallet måste klass A och B ha samma färg, då det finns en elev från vardera av dessa två klasser i den första kolumnen. Klass C kan däremot få en annan färg på sina hattar. Svaret blir då $2$.

I det tredje exempelfallet kan vi ge varje klass varsin färg, eftersom det inte förekommer två elever från olika klasser i samma kolumn. Svaret blir $3$

I det sista exempelfallet kan vi tilldela alla elever från klass A, B och C en färg, och alla elever från klass D och E en annan färg. Svaret blir $2$.

Sample Input 1 Sample Output 1
2 3 2
AAB
ABB
1
Sample Input 2 Sample Output 2
2 2 3
AC
BC
2
Sample Input 3 Sample Output 3
2 3 3
ABC
ABC
3
Sample Input 4 Sample Output 4
3 5 5
ABECE
BCDAE
CADBD
2