Emschercoast Contest History

Wie man die Anzeigetafel pflastern kann

Mit diesem kleinen C Programm haben wir die beste Lösung gefunden. Ein paar Annahmen stecken darin: Die linke untere Eintrittskarte schließt bündig mit der Anzeigetafel ab und ragt nicht über sie hinaus. Man bekommt die beste Lösung, wenn man die Anzeigetafel in fünf Teile zerlegt wie auf der Skizze und alle Eintrittskarten in einem Teil gleich orientiert sind (hoch oder quer). Mehr Fälle muss man nicht untersuchen. Ganz genau wissen wir das nicht. Hoffen wir mal, dass es stimmt. Das Programm testet alle Kombinationen durch, wie die Eintrittskarten unter diesen Bedingungen plaziert werden können.

#include <stdio.h>

void schleife(int B,int H,int b[5],int h[5]);
void anzahl(int B,int H,int b[5],int h[5],int m[5],int n[5]);
int min=999999;

int main(int argc, char *argv[]) {

  int lage,l;
  int i,h[5],b[5];

  for (lage=0;lage<32;lage++) {
     l = lage;
     for (i=0;i<5;i++) {
       h[i] = (l%2) ? 105 : 74;
       b[i] = (h[i] == 105) ? 74 : 105;
       l /= 2;
     }
     schleife(6420,17740,b,h);
     schleife(17740,6420,b,h);
  }
}

void schleife(int B,int H,int b[5],int h[5]) {

  int n[5],m[5];

  for (m[0]=0;m[0]*b[0]<=B+b[0]-1;m[0]++) {

    for (m[3]=0;m[3]*b[3]<=B+b[3]-1;m[3]++) {

      for (n[0]=0;n[0]*h[0]<=H+h[0]-1;n[0]++) {

        for (n[2]=0;n[0]*h[0]+n[2]*h[2]<=H+h[2]-1;n[2]++) {

          anzahl(B,H,b,h,m,n);

        }
      }
    }
  }
}

void anzahl(int B,int H,int b[5],int h[5],int m[5],int n[5]) {

  int i,zahl;

  m[1] = (B-(b[0]*m[0]))/b[1];
  if (b[0]*m[0]+b[1]*m[1]<B) m[1]++;
  if (m[1]<0) m[1]=0;

  m[2] = B/b[2];
  if (b[2]*m[2]<B) (m[2])++;

  m[4] = (B-(b[3]*m[3]))/b[4];
  if (b[3]*m[3]+b[4]*m[4]<B) m[4]++;
  if (m[4]<0) m[4]=0;

  n[1] = (n[0]*h[0])/h[1];
  if (n[1]*h[1] < n[0]*h[0]) n[1]++;

  n[3] = (H-n[0]*h[0]-n[2]*h[2])/h[3];
  if (n[0]*h[0]+n[2]*h[2]+n[3]*h[3]<H) n[3]++;
  if (n[3]<0) n[3]=0;

  n[4] = (n[3]*h[3])/h[4];
  if (n[4]*h[4] < n[3]*h[3]) n[4]++;

  zahl = 0;
  for (i=0;i<5;i++) zahl += m[i]*n[i];
 
  if(zahl<min) {
    min=zahl;
    printf("\nH = %d  B = %d\n",H,B);
    printf("i   b   h   m   n\n");
    for(i=0;i<5;i++) {
      printf("%1d %3d %3d %3d %3d\n",i,b[i],h[i],m[i],n[i]);
    }
    printf("Bisher beste Loesung: %d\n",min);
  }

}
        

Natürlich hat das Programm nicht diese Skizze gemalt, aber die Ausgabe unten kann man mit der Skizze besser erklären.

Bild

Und hier haben wir die Ausgabe des Programms. H und B sind Höhe und Breite der Anzeigetafel (man kann die drei Strefen auch vertikal anordnen), i ist der Index des Feldes in der Anzeigetafel, 0 links oben, 1 rechts oben, 2 mitte, 3 links unten, 4 rechts unten. h und b sind Höhe und Breite der EIntrittskarte (horizontal oder vertikal angeordnet), m ist die Anzahl an Karten in horizontaler Richtung und n in vertikaler Richtung für jeden Teil der Anzeigetafel:


H = 17740  B = 6420
i   b   h   m   n
0 105  74   0   0
1 105  74  62   0
2 105  74  62   0
3 105  74   0 240
4 105  74  62 240
Bisher beste Loesung: 14880

H = 6420  B = 17740
i   b   h   m   n
0 105  74   0   0
1 105  74 169   0
2 105  74 169   0
3 105  74   0  87
4 105  74 169  87
Bisher beste Loesung: 14703

H = 17740  B = 6420
i   b   h   m   n
0  74 105   6 162
1 105  74  57 230
2 105  74  62   0
3 105  74   0  10
4 105  74  62  10
Bisher beste Loesung: 14702

H = 17740  B = 6420
i   b   h   m   n
0  74 105   6 167
1 105  74  57 237
2 105  74  62   0
3 105  74   0   3
4 105  74  62   3
Bisher beste Loesung: 14697

H = 17740  B = 6420
i   b   h   m   n
0  74 105   6 169
1 105  74  57 240
2 105  74  62   0
3 105  74   0   0
4 105  74  62   0
Bisher beste Loesung: 14694

H = 17740  B = 6420
i   b   h   m   n
0  74 105  13 157
1 105  74  52 223
2 105  74  62   0
3 105  74   0  17
4 105  74  62  17
Bisher beste Loesung: 14691

H = 17740  B = 6420
i   b   h   m   n
0  74 105  13 162
1 105  74  52 230
2 105  74  62   0
3 105  74   0  10
4 105  74  62  10
Bisher beste Loesung: 14686

H = 17740  B = 6420
i   b   h   m   n
0  74 105  13 167
1 105  74  52 237
2 105  74  62   0
3 105  74   0   3
4 105  74  62   3
Bisher beste Loesung: 14681

H = 17740  B = 6420
i   b   h   m   n
0  74 105  13 169
1 105  74  52 240
2 105  74  62   0
3 105  74   0   0
4 105  74  62   0
Bisher beste Loesung: 14677

H = 17740  B = 6420
i   b   h   m   n
0  74 105  30 167
1 105  74  40 237
2 105  74  62   0
3 105  74   0   3
4 105  74  62   3
Bisher beste Loesung: 14676

H = 17740  B = 6420
i   b   h   m   n
0  74 105  30 169
1 105  74  40 240
2 105  74  62   0
3 105  74   0   0
4 105  74  62   0
Bisher beste Loesung: 14670

H = 17740  B = 6420
i   b   h   m   n
0  74 105  74 169
1 105  74   9 240
2 105  74  62   0
3 105  74   0   0
4 105  74  62   0
Bisher beste Loesung: 14666

H = 6420  B = 17740
i   b   h   m   n
0  74 105 227  40
1 105  74   9  57
2 105  74 169   0
3 105  74   0  30
4 105  74 169  30
Bisher beste Loesung: 14663

H = 6420  B = 17740
i   b   h   m   n
0  74 105 200  31
1 105  74  28  44
2  74 105 240   9
3 105  74   0  30
4 105  74 169  30
Bisher beste Loesung: 14662

H = 6420  B = 17740
i   b   h   m   n
0  74 105 200  31
1 105  74  28  44
2 105  74 169  30
3  74 105 237   9
4 105  74   2  13
Bisher beste Loesung: 14661
        

Wer das Programm selbst testen möchte, muss etwas Geduld haben. Auf einem iBook G4 mit 1,2GHz läuft es etwa eine Stunde.

Zur Hauptseite / zum aktuellen Rätsel.