Tävlingsprogrammering/Uppgifter/Bokstäver

Bokstäver

Sofie håller på att lära sig läsa. Varje vecka lär hon sig en ny bokstav. Men otålig som hon är vill hon varje vecka välja den bokstav som gör att hon kan läsa flest nya ord (vi antar att för att kunna läsa ett ord måste man kunna alla de ingående bokstäverna). Skriv ett program som, utifrån en ordlista, bestämmer i vilken ordning Sofie ska lära sig bokstäverna.

Indata

På första raden står ett heltal N, antalet ord i ordlistan, där 1 ≤ N ≤ 10000. Därefter följer N rader med ett ord på varje rad. Varje ord består av minst 1 och högst 10 tecken. Endast versalerna A-Z förekommer.

Utdata

Programmet ska skriva en rad med de 26 bokstäverna A-Z i den ordning som gör att Sofie varje vecka kan läsa så många nya ord som möjligt. Om det någon vecka finns flera möjliga bokstäver som ger samma antal nya ord ska du välja den som står först i alfabetet.

Exempel: Indata

7
ANNA
I
KALAS
BAKA
ABBA
ARASH
PAR

Exempel: Utdata

IABKNCDEFGHJLSRPMOQTUVWXYZ

Lösning

Här står det tydligt i uppgiften att vi ska använda oss av en girig (greedy) algoritm, d.v.s. välja den bokstav som ger flest ord för stunden, utan tanke på framtiden. Observera att detta inte alltid ger den bästa kunskapsutvecklingen för Sofie: med ett för stunden sämre (eller annat lika bra) val hade hon kanske kunnat fler ord veckan därpå.

För varje vecka loopar vi över de ännu inte tagna bokstäverna och väljer en i taget, kollar hur många av orden man kan skriva med denna och de tidigare valda, samt skriver ut den bokstav som ger flest antal ord. Om vi går igenom bokstäverna i alfabetisk ordning och bara sätter en kandidat om antalet ord är strikt högre än det tidigare bästa resultatet, uppfylls automatiskt skiljeregeln vid lika antal ord.

Lösning i C:

#include <stdio.h>

char ord[10000][11];

int main() {
  char v,c,bra;
  int taken[300],i,n,j,nok,max,N;
  scanf("%d", &N);
  for(i=0;i<N;i++) scanf("%s", ord[i]);
  for(c='A';c<='Z';c++) taken[c]=0;
  for(n=1;n<=26;n++) {   //Loopa över veckorna
    max=-1;
    for(v='A';v<='Z';v++) if (!taken[v]) {    //Loopa över alla bokstäver som ännu inte är tagna
	taken[v]=1;   //Här markerar vi temporärt v som tagen
	nok=0;          //räknare för antalet ord vi kan skriva med de tagna bokstäverna
	for(i=0;i<N;i++) {     //Loopa över orden
	  for(j=0;ord[i][j]!=0;j++) if(!taken[ord[i][j]]) break;      //Bryt om det finns en bokstav i ordet som inte är tagen
	  if(ord[i][j]==0) nok++;     //Är vi vid strängens slut så kan ordet skrivas, så öka räknaren
	}
	taken[v]=0;     //Avmarkera igen, vi bara testade att markera v
	if(nok>max) {    //Om fler möjliga ord än tidigare maxantalet, så sätt v som kandidat (bra)
	  max=nok;
	  bra=v;
	}
      }
    printf("%c",bra);      //Skriv ut den bästa bokstaven
    taken[bra]=1;     //Här markerar vi den bästa bokstaven som tagen på riktigt
  }
  printf("\n");
  return 0;
}