#include <cstdlib>
#include <vector>
#include <algorithm>
#include <iostream>
#include <fstream>
#include <string>
#include <sstream>
#include <climits>

using namespace std;

/* Náhodné cislo z intervalu [0, 1) */
double randdouble() {
	return rand()/(double(RAND_MAX)+1);
}

/* Parametry algoritmu */
int N = 50;		// Velikost populace
int D;			// Velikost jedince
double PK = 0.9;	// Pravděpodobnost zavisle mutace
double PM = 0.1;	// Pravděpodobnost mutace
double PB = 0.01;	// Pravděpodobnost mutace na jednom bitu
double PE = 0.1;	// Velikost elitismus
int IT = 10000;		// Maximalní počet iterací
int BEHY = 5;		// Počet běhů celého algoritmu
const int L = 10;	// Jendou za kolik iterací se loguje

int K;
vector<int> w;

/* Jedinci */
struct Jedinec {
	vector<int> geny;
	double fitness;
	/* Zařídí, že jedinci se třídí na základě fitness od největšího */
	bool operator<(const Jedinec &x) const {
		return fitness > x.fitness;
	}
};
/* Třída pro logování výpočtů -- té není nutné ji rozumět */
class Logovani {
	ofstream ofs;
public:
	/* Otevře soubor pro logování */
	void open(int x) {
		stringstream name;
		name << "beh" << x << ".log";
		ofs.open(name.str().c_str());
	}
	/* Ukončí logování */
	void close() {
		ofs.close();
	}
	/* Udělá zápis z generace gen z iterace it */
	void write(vector<Jedinec> gen, int it) {
		double maxi = 0;
		double total = 0;
		for (int i=0; i<gen.size(); i++) {
			total += gen[i].fitness;
			maxi = max(maxi, gen[i].fitness);
		}
		ofs << it << "\t" << total/gen.size() << "\t" << maxi << endl;
	}
} log;

/* Generování náhodného binárního jedince */
Jedinec generuj_jedince(int d) {
	Jedinec j;
	j.geny = vector<int>(d, 0);
	for (int i=0; i<d; i++)
		j.geny[i] = rand()%K;
	return j;
}

/* Spočítá fitness a uloží ji do jedince */
void spocitej_fitness(Jedinec &x) {
	vector<int> v(K, 0);
	for (int i=0; i< x.geny.size(); i++)
		v[x.geny[i]] += w[i];
	int miny = INT_MAX; int a;
	int maxy = 0;	int b;
	for (int i=0; i<K; i++) {
		miny = min(miny, v[i]);
		maxy = max(maxy, v[i]);
	}
	x.fitness = 1.0/(maxy-miny+1);
}

/* Zmutuje jedince */
void mutace(Jedinec &x) {
	for (int i=0; i<x.geny.size(); i++) {
		double p = randdouble();
		if (p < PB) {
			// Prohozeni bitu
			x.geny[i] = rand()%K;
		}
	}
}

/* Zavisla mutace */
void zavisla_mutace(Jedinec &x) {
	vector<int> v(K);
	vector<vector<int> > ix(K);
	for (int i=0; i<x.geny.size(); i++) {
		v[x.geny[i]] += w[i];
		ix[x.geny[i]].push_back(i);
	}
	// Nejtezsi a nejlehci hromadka
	int A = INT_MAX; int a;
	int B = INT_MIN; int b;
	for (int i=0; i<K; i++) {
		if (A > v[i]) {
			A = v[i]; a = i;
		}
		if (B < v[i]) {
			B = v[i]; b = i;
		}
	}
	// Presun predmet z nejtezsi na nejlehci
	x.geny[ix[b][rand()%ix[b].size()]] = a;
}

/* Zkříží dva jedince */
/*void krizeni(Jedinec &x, Jedinec &y) {
	// Náhodný bod jednobodového křížení
	int k = rand()%D;
	for (int i=k; i<D; i++) {
		swap(x.geny[i], y.geny[i]);
	}
}*/

/* Ruletová selekce */
vector<Jedinec> ruletova_selekce(vector<Jedinec> &gen, int n) {
	// Spočítej celkovou fitness
	double total = 0;
	for (int i=0; i<gen.size(); i++)
		total += gen[i].fitness;
	// Vyber n jedinců
	vector<Jedinec> vyber;
	for (int i=0; i<n; i++) {
		// "Hozeni kulicky do rulety"
		double d = randdouble() * total;
		// Výběr příslušného jedince
		int j = 0;
		while (gen[j].fitness < d) {
			d -= gen[j].fitness;
			j++;
		}
		vyber.push_back(gen[j]);
	}
	return vyber;
}

Jedinec geneticky_algoritmus() {
	// Vygeneruj náhodnou populaci
	vector<Jedinec> generace;
	for (int i=0; i<N; i++)
		generace.push_back(generuj_jedince(D));
	// Spočítej její fitness
	for (int i=0; i<N; i++)
		spocitej_fitness(generace[i]);
	sort(generace.begin(), generace.end());
	Jedinec best = generace[0];
	// Iterace algoritmu
	for (int it=0; it<IT; it++) {
		// Logování jednou za L iterací
		if (it%L==0) {
			log.write(generace, it);
		}
		vector<Jedinec> vyber = ruletova_selekce(generace, N);
		// Zavisla mutace
		for (int i=0; i<vyber.size(); i++) {
			double p = randdouble();
			if (p < PK)
				zavisla_mutace(vyber[i]);
		}
		// Mutace
		for (int i=0; i<vyber.size(); i++) {
			double p = randdouble();
			if (p < PM)
				mutace(vyber[i]);
		}
		for (int i=0; i<vyber.size(); i++)
			spocitej_fitness(vyber[i]);
		// Elitismus -- přidá do výběru část předchozí generace
		for (int i=0; i<N*PE; i++)
			vyber.push_back(generace[i]);
		// Setřídí podle fitness
		sort(vyber.begin(), vyber.end());
		// Smaže minulou generaci
		generace.clear();
		// Vezmi N nejlepších do další generace
		generace = vector<Jedinec>(vyber.begin(), vyber.begin()+N);
		if (generace[0].fitness > best.fitness)
			best = generace[0];
	}
	log.write(generace, IT);
	return best;
}

/* Zapíše do souboru fitness a geny nejlepšího jedince */
void zaloguj_nejlepsiho(Jedinec best) {
	ofstream ofs("best.log");
	ofs << "Fitness: " << best.fitness << endl;
	ofs << "Geny:" << endl;
	for (int i=0; i<best.geny.size(); i++)
		ofs << best.geny[i] << " ";
	ofs << endl;
}

int main() {
	cin >> K >> D;
	w = vector<int>(D);
	for (int i=0; i<D; i++) cin >> w[i];

	// Zadejte svůj datum narození jako DDMMYYYY
	srand(26111990);
	Jedinec best;
	best.fitness = 0;
	for (int b=0; b<BEHY; b++) {
		cout << "Beh " << b << endl;
		// Otevře logování b-tého běhu
		log.open(b);
		// Spustí běh genetického algoritmu a vrátí z něj nejlepšího jedince
		Jedinec j = geneticky_algoritmus();
		// Zavře logování b-tého běhu
		log.close();
		if (j.fitness > best.fitness) {
			best = j;
			zaloguj_nejlepsiho(best);
		}
	}
	return 0;
}