#include <stdlib.h>
#include <stdio.h>
#include <string.h>

#define maxboeken 30              /* maximum hoeveelheid boeken op een plank */
#define maxlen 20                 /* maximum lengte van een titel */

/* De naam kast ten spijt, gaat het hier niet om de kasten in de opgave,
   maar ja, de naam plankstruct is zo mogelijk nog waardelozer */
typedef struct kast {
  char prefix[maxlen+1];          /* gebruikte prefix in de boom */
  char grootste[maxlen+1];        /* prefix van alle boeken op deze plank */
  unsigned int boeken;
  char boek[maxboeken][maxlen+1]; /* De titels op deze plank */
  struct kast *child;
  struct kast *next;
  int echt;
} kast;


unsigned int planken;
kast *plank=NULL;
unsigned int plankenperkast,boekenperplank;
int debug;

void Init(kast *pl,char *titel) {
  strcpy(pl->prefix,"");          /* prefix in deze ``boom'' is leeg */
  strcpy(pl->grootste,titel);     /* prefix op deze plank is de titel */
  pl->boeken=1;
  strcpy(pl->boek[0],titel);     /* Dit boek STAAT op de plank */
  pl->child=NULL;
  pl->next=NULL;
  pl->echt=1;
  planken++;
}

void Print(kast *pl) {
  static int tab=0;
  unsigned int i;
/*  if ((pl!=NULL) && (debug)) {
  fprintf(stderr,"%*sprefix: ``%s'', grootste: ``%s''\n",
            tab,"",pl->prefix,pl->grootste);
    for (i=0;i<pl->boeken;i++) fprintf(stderr,"%*s%s\n",tab,"",pl->boek[i]);
    tab+=3;
    Print(pl->child);
    tab-=3;
    Print(pl->next);
  } */
}

void Quit(kast **pl) {
  if ((*pl)!=NULL) {
    Quit(&((*pl)->child));
    Quit(&((*pl)->next));
    free(*pl);
    (*pl)=NULL;
  }
}

kast *Zoek(kast *pl,char *titel) {
  /* Neem aan dat er tenminste 1 kind is */
  kast *plch=pl->child,*pln;
  if (strncmp(plch->prefix,titel,strlen(plch->prefix))>0) return(NULL);
  pln=plch->next;
  while ((pln!=NULL) && (strncmp(pln->prefix,titel,strlen(pln->prefix))<=0)) {
    plch=pln;
    pln=pln->next;
  }
  return(plch);
}

void Herverdeel(kast *pl) {
  unsigned int i,j;
  kast *nwpl,*zpl;

  strcpy(pl->prefix,pl->grootste);
  pl->echt=0;
  /* Voor elk boek op deze plank moet een kind-plank gevonden worden */
  for (i=0;i<pl->boeken;i++) {
    zpl=Zoek(pl,pl->boek[i]);
    if (zpl==NULL) {
      nwpl=malloc(sizeof(kast));
      Init(nwpl,pl->boek[i]);
      for (j=0;pl->prefix[j]==pl->boek[i][j];j++) ;
      strncpy(nwpl->prefix,pl->boek[i],j+1);
      nwpl->prefix[j+1]='\0';
      nwpl->next=pl->child;
      pl->child=nwpl;
    } else {
      if (strncmp(zpl->prefix,pl->boek[i],strlen(zpl->prefix))<0) {
        nwpl=malloc(sizeof(kast));
        Init(nwpl,pl->boek[i]);
        for (j=0;pl->prefix[j]==pl->boek[i][j];j++) ;
        strncpy(nwpl->prefix,pl->boek[i],j+1);
        nwpl->prefix[j+1]='\0';
        nwpl->next=zpl->next;
        zpl->next=nwpl;
      } else {
        /* Het boek hoort op deze plank thuis */
        strcpy(zpl->boek[zpl->boeken++],pl->boek[i]);
        for (j=0;zpl->grootste[j]==pl->boek[i][j];j++);
        zpl->grootste[j]='\0';
      }
    }
/*    Print(pl); */
  }
  pl->boeken=0;
  planken--; /* pl is nu geen ``echte'' plank meer */
} /* Herverdeel() */

void VolgendeBoek(char *titel) {
  kast *pl,*nwpl,*zpl;
  unsigned int i;

  if (plank==NULL) {
    plank=malloc(sizeof(kast));
    Init(plank,titel);
    return;
  }

  pl=plank;
  while (!pl->echt) { /* oftewel, er ZIJN kinderen */
    zpl=Zoek(pl,titel);
    if (zpl==NULL) {
      /* Maak nieuwe plank vooraan in lijst van kinderen */
      nwpl=malloc(sizeof(kast));
      Init(nwpl,titel);
      for (i=0;pl->child->prefix[i]==titel[i];i++) ;
      strncpy(nwpl->prefix,titel,i+1);
      nwpl->prefix[i+1]='\0';
      nwpl->next=pl->child;
      pl->child=nwpl;
      return;
    } else {
      if (strncmp(zpl->prefix,titel,strlen(zpl->prefix))<0) {
        nwpl=malloc(sizeof(kast));
        Init(nwpl,titel);
        for (i=0;pl->prefix[i]==titel[i];i++) ;
        strncpy(nwpl->prefix,titel,i+1);
        nwpl->prefix[i+1]='\0';
        nwpl->next=zpl->next;
        zpl->next=nwpl;
        return;
      } else {
        pl=zpl;
      }
    }
  }

  /* We zijn nu aangekomen bij een ``echte'' plank. Het boek moet hierbij */
  for (i=0;pl->grootste[i]==titel[i];i++);
  pl->grootste[i]='\0';
  if (pl->boeken<boekenperplank) {
    /* boeken hoeven niet gesorteerd op de plank te staan */
    strcpy(pl->boek[pl->boeken++],titel);
  } else {
    /* Leg de nieuwe titel vast op zijn eigen plank,
       zodat Zoek gebruikt mag worden */
    nwpl=malloc(sizeof(kast));
    Init(nwpl,titel);
    strncpy(nwpl->prefix,titel,strlen(pl->grootste)+1);
    nwpl->prefix[strlen(pl->grootste)+1]='\0';
    pl->child=nwpl;
    Herverdeel(pl);
  }
}

int main() {
  unsigned int runs,r;
  unsigned int boeken,b;
  char titel[maxlen+1];

  scanf("%d",&runs);
  for (r=0;r<runs;r++) {
    if (r!=9) debug=1; else debug=0;
    planken=0;
    plank=NULL;
    scanf("%d %d %d",&plankenperkast,&boekenperplank,&boeken);
    for (b=0;b<boeken;b++) {
      scanf("%s",titel); /* Hoezo niet netjes maxlen tekens?
        Die opmerking over spaties is slechts bedoeld om ambiguiteiten
        in het probleem te vermijden :*/
      VolgendeBoek(titel);
      Print(plank);
    }
    printf("%d\n",(planken+plankenperkast-1)/plankenperkast);
    Quit(&plank); /* This REALLY s*cks, maar 'k heb geen tijd meer om de echte fout op te zoeken */
  }
  return(0);
}

Generated by Java2Html