/*
Datei............: Aufg0443.java
Projekt..........: Einführung in die Java-Programmierung
Erstellt.........: 04.10.97, Guido Krüger
Geändert.........: --
Aufgabe..........: Musterlösung zu Aufgabe 04.43
Kommentare.......:

Das folgende Programm gibt eine einfache Implementierung des
d'Hondtschen Höchstzahlenverfahrens. Aus Gründen der
Übersichtlichkeit wurde kein Fehlerchecking eingebaut und
auch der Algorithmus zur Berechnung der Höchstzahlen ist
sehr einfach gehalten. Das Programm arbeitet in folgenden
Schritten:

1. Zunächst muß der Anwender die Anzahl der Parteien,
   die Anzahl der zu verteilenden Sitze und die auf jede Partei
   entfallene Stimmenzahl eingeben.
2. Nun wird die Größe der Höchstzahltabelle abgeschätzt.
   Wir multiplizieren dazu den prozentualen Anteil der stärksten
   Partei mit der Gesamtsitzzahl, erhöhen den Wert um 20 % und
   zählen 1 hinzu. Dieses einfache Verfahren sollte in den
   meisten Fällen funktionieren.
3. Nun erzeugt das Programm das Array mit den Höchstwerten. Es
   ist ein dreidimensionales Array mit folgender Aufteilung:
   1. Dimension: Ein Element je dividierter Stimmenzahl
   2. Dimension: Ein Element je Partei
   3. Dimension: Zwei Elemente, das erste für die dividierte
                 Stimmenzahl, das zweite für die Rangfolge unter
                 allen Höchstwerten (0, wenn noch nicht verwendet).
   Der Berechnungsalgorithmus durchläuft eine Schleife über alle
   zu vergebenden Sitze, sucht jeweils das größte noch nicht
   verwendete Element und macht es zum nächsten Höchstwert.
4. Nun wird die Höchstwerttabelle ausgegeben. Zur Ausgabeformatierung
   verwenden wir die Methode printFormatted, die einen String in einem
   Feld fester Länge ausgeben kann.
5. Zum Schluß wird die Anzahl der Sitze je Partei berechnet und
   auf dem Bildschirm ausgegegen.
*/
import java.io.*;

public class Aufg0443
{
  static final int MAXVALUES = 20;

  public static void main(String args[])
  {
    BufferedReader din = new BufferedReader(new InputStreamReader(System.in));
    int numparties;
    int numseats;
    int aResults[];
    int aTable[][][];

    try {
      //---Eingabeschleife---
      System.out.print("Anzahl der Parteien: ");
      numparties = Integer.parseInt(din.readLine());
      System.out.print("Anzahl der Sitze: ");
      numseats = Integer.parseInt(din.readLine());
      aResults = new int[numparties];
      for (int i = 0; i < numparties; ++i) {
	System.out.print("Stimmen für Partei " + (i+1) + ": ");
	aResults[i] = Integer.parseInt(din.readLine());
      }

      //Größe der Höchstzahlentabelle abschätzen
      int max = 0;
      int sum = 0;
      for (int i = 0; i < numparties; ++i) {
	sum += aResults[i];
	max = (aResults[i] > max) ? aResults[i] : max;
      }
      int tabsize = (int)(1 + (((double)max / sum) * numseats * 1.2));

      //---Tabelle der Höchstzahlen erzeugen
      aTable = new int[tabsize][numparties][2];
      for (int i = 0; i < numparties; ++i) {
	for (int j = 1; j <= tabsize; ++j) {
	  aTable[j-1][i][0] = aResults[i] / j;
	  aTable[j-1][i][1] = 0;
	}
      }

      //Höchstzahlen berechnen
      for (int i = 1; i <= numseats; ++i) {
	max = -1;
	int maxposx = 0;
	int maxposy = 0;
	for (int j = 0; j < tabsize; ++j) {
	  for (int k = 0; k < numparties; ++k) {
	    if (aTable[j][k][0] > max && aTable[j][k][1] == 0) {
	      max = aTable[j][k][0];
	      maxposy = j;
	      maxposx = k;
	    }
	  }
	}
	aTable[maxposy][maxposx][1] = i;
      }

      //---Tabelle der Höchstzahlen ausgeben
      System.out.println();
      for (int j = 0; j < numparties; ++j) {
	printFormatted("Partei " + (j+1), 10);
	System.out.print("  ");
      }
      System.out.println();
      for (int j = 0; j < numparties; ++j) {
	System.out.print("------------");
      }
      System.out.println();
      for (int i = 0; i < tabsize; ++i) {
	for (int j = 0; j < numparties; ++j) {
	  printFormatted(aTable[i][j][0] + " ", 8);
	  printFormatted(aTable[i][j][1] + "  ", 4);
	}
	System.out.println();
      }

      //Sitzverteilung ausgeben
      System.out.println();
      for (int i = 0; i < numparties; ++i) {
	int seats = 0;
	for (int j = 0; j < tabsize; ++j) {
	  if (aTable[j][i][1] > 0) {
	    ++seats;
	  }
	}
	System.out.println("Partei " + (i+1) + ": " + seats + " Sitze");
      }

    } catch (IOException e) {
      System.out.println("  Fehler beim Lesen der Eingabe");
    }
  }

  public static void printFormatted(String msg, int fieldwidth) 
  {
    for (int i = fieldwidth - msg.length(); i >= 1; --i) {
      System.out.print(" ");
    }
    System.out.print(msg);
  }
}