02 - Biblioteca de Código (C++)

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <cstring>
#include <cmath>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#define MIN(a,b) ((a) < (b) ? (a) : (b))
#define MAX(a,b) ((a) > (b) ? (a) : (b))
#define ABS(a) ((a) > 0 ? (a) : (-a))
#define FOR(i,v,n) for(int i=v,_n=n;i<_n;++i)
#define FORD(i,v,n) for(int i=(n-1),_v=v;i>=_v;--i)
#define REP(i,n) FOR(i,0,n)
#define REPD(i,n) FORD(i,0,n)
#define FOREACH(it,c) for(__typeof((c).begin())
it=(c).begin();it!=(c).end();++it)
#define MP(a,b) make_pair((a),(b))
#define ALL(c) (c).begin(),(c).end()
#define PB push_back
#define MAX_V
#define MAX_A
#define INF 2147483647
#define PRINT(x) x

const double PI = acos(-1.0);
using namespace std;
int main(){
	return 0;
}

typedef struct{
...
} TReg;

while(cin.getline(str, MAXLINE))
	cout << str << endl;

while(sscanf(line, "%d %d %d", &s, &t, &w) == 3)
	printf("%d %d %d", s, t, w);

sprintf(line, "%d %d %d", a, b, c);
printf("%s\n", line);

map<string, int> m;
map<string, int>::iterator it;

m["abracadabra"] = 10;
m["yabadabadoo"] = 15;
m["hi-yo silver"] = 20;

m.erase("yabadabadoo");

for(it=m.begin(); it != m.end(); it++)
	cout << it->first << " " << it->second << endl;

cout << m["abracadabra"] << endl;

cout << m.count("hi-yo silver") << endl;

m.clear();

set<int> s;

s.insert(10);

cout << s.count(10) << endl;

s.clear();

queue<int> Q;

Q.push(10);

cout << Q.front() << endl;

Q.pop();

if(!Q.empty()){ ... }

cout << Q.size() << endl;

int v[n];
/* -1: a < b
* 0: a == b
* 1: a > b */
int cmp(const void * a, const void * b){
	return ( *(int*)a - *(int*)b );
}
qsort(v, n, sizeof(int), cmp);

typedef struct {
	int u, v, w;
} TAdj;
TAdj adj[n];
int cmp(const void *a, const void *b){
	TAdj *x, *y;
	x = (TAdj*)a;
	y = (TAdj*)b;
	if(x->w < y->w)
		return -1;
	if(x->w > y->w)
		return 1;
return 0;
}
qsort(adj, n, sizeof(TAdj), cmp);

int grau[MAX_V]; // número de arestas no vértice
int d[MAX_V]; // distância
int p[MAX_V]; // pai do vertice
int visited[MAX_V]; // vértices visitados

typedef struct{
	int v; // vértice
	double w; // peso
} TAdj;
TAdj adj[MAX_V][MAX_A];

int adj[MAX_V][MAX_A];

void aresta(int a, int b, double w){
	adj[a][ grau[a] ].v = b;
	adj[a][ grau[a] ].w = w;
	grau[a]++;
	adj[b][ grau[b] ].v = a;
	adj[b][ grau[b] ].w = w;
	grau[b]++;
}

memset(grau, 0, sizeof(grau));
memset(visited, 0, sizeof(visited));
memset(p, -1, sizeof(p));

void dfs(int s){
	int t;
	visited[s] = 1;
	for(int i=0; i<grau[s]; i++){
		t = adj[s][i];
		if(visited[t] == 0){
			p[t] = s;
			dfs(t);
		}
	}
}
void initializeDfs(){
	memset(visited, 0, sizeof(visited));
	memset(p, -1, sizeof(p));
}

void bfs(int inicio){
	int s, t;
	queue<int> Q;
	memset(visited, 0, sizeof(visited));
	memset(p, -1, sizeof(p));
	d[inicio] = 0;
	visited[inicio] = 1;
	Q.push(inicio);
	while(!Q.empty()){
		s = Q.front();
		Q.pop();
		for(int i=0; i<grau[s]; i++) {
			t = adj[s][i];
			if(visited[t] == 0){
				visited[t] = 1;
				d[t] = d[s] + 1;
				p[t] = s;
				Q.push(t);
			}
		}
	}
}

void initialize(){ // inicializar antes de ler o grafo
	for(int i=0; i<MAX_V; i++){
		for(int j=0; j<MAX_V; j++){
			adj[i][j] = INF;
			p[i][j] = -1;
		}
		adj[i][i] = 0;
	}
}
void floyd(){
	for(int k=0; k<MAX_V; k++)
		for(int i=0; i<MAX_V; i++)
			for(int j=0; j<MAX_V; j++)
				if(adj[i][k] + adj[k][j] < adj[i][j]){
					adj[i][j] = adj[i][k] + adj[k][j];
					p[i][j]= p[k][j];
	}
}

void floydMinMax(){
	int maior;
	for(int k=0; k<MAX_V; k++)
		for(int i=0; i<MAX_V; i++)
			for(int j=0; j<MAX_V; j++){
				if(adj[i][k] > adj[k][j])
					maior = adj[i][k];
				else
					maior = adj[k][j];
				if(adj[i][j] > maior){
					adj[i][j] = maior;
					adj[j][i] = maior;
		}
	}
}

void dijkstra(int inicial){
	priority_queue< pair<int,int> > heap; // peso, vertice
	int s, t, peso;
	for(int i=0; i<MAX_V; i++)
		d[i] = INF;
	memset(p, -1, sizeof(p));
	heap.push(make_pair(d[inicial] = 0, inicial));
	while(!heap.empty()){
		s = heap.top().second;
		heap.pop();
		for(int i=0; i<grau[s]; i++){
			t = adj[s][i].v;
			peso = adj[s][i].w;
			if(d[s] + peso < d[t]){
				d[t] = d[s] + peso;
				p[t] = s;
				heap.push(make_pair(-d[t], t));
			}
		}
	}
}

bool bellmanFord(int inicial, int n){
	memset(p, -1, sizeof(p));
	for(int i=0; i<n; i++)
		d[i] = INF;
	d[inicial] = 0;
	for(int i=0; i<n; i++) // todos vertices
		for(int j=0; j<n; j++) /* todas */
			for(int k=0; k<grau[j]; k++)/* arestas */
				if(d[j] + adj[j][k].w < d[adj[j][k].v]){
					d[adj[j][k].v] = d[j] + adj[j][k].w;
				p[adj[j][k].v] = j;
			}
		for(int i=0; i<n; i++)
			for(int j=0; j<grau[i]; j++)
				if(d[adj[i][j].v] > d[i] + adj[i][j].w)
					return false;
		return true;
}

int total; //armazena o custo total da MST
void prim(int inicio, int n){
	priority_queue< pair<int, int> > heap;
	int s, t, arc;
	for(int i=0; i<n; i++)
		d[i] = INF;
	memset(p, -1, sizeof(p));
	memset(visited, 0, sizeof(visited));
	heap.push(make_pair(d[inicio] = 0, inicio));
	total = 0;
	while(!heap.empty()){
		s = heap.top().second;
		heap.pop();
		if(!visited[s])
			total += d[s];
		visited[s] = 1;
		for(int i=0; i<grau[s]; i++){
			t = adj[s][i].v;
			arc = adj[s][i].w;
			if(d[t] > arc && !visited[t]){
				d[t] = arc;
				p[t] = s;
				heap.push(make_pair(-d[t], t));
			}	
		}
	}
}

typedef struct{
	int u, v, w;
} TAdj;
TAdj adj[MAX_A];
TAdj mst[MAX_A]; //armazena a MST
int nro_arestas, total, posMst;
int findSet(int x){
	if(x != p[x])
	p[x] = findSet(p[x]);
	return p[x];
}
void kruskal(){
	int u, v, u_set, v_set;
	posMst = 0;
	for(int i=0; i<MAX_V; i++) // todos vértices
		p[i] = i;
	qsort(adj, nro_arestas, sizeof(TAdj), cmp);
	for(int i=0; i<nro_arestas; i++){
		u = adj[i].u; v = adj[i].v;
		u_set = findSet(u);
		v_set = findSet(v);
		if(u_set != v_set){
			p[v_set] = p[u_set];
			mst[posMst++] = adj[i];
			total += adj[i].w;
		}
	}
}

int indegree[MAX_V]; // grau de entrada do vértice
int used[MAX_V]; // vértice foi usado?
queue<int> L; // armazena a ordenação topológica
void topological_sort(){
	queue<int> z;
	int v, w;
	memset(indegree, 0, sizeof(indegree));
	for(int i=0; i<MAX_V; i++)
		if(grau[i])
			for(int j=0; j<grau[i]; j++)
				indegree[adj[i][j]]++;
	for(int i=0; i<MAX_V; i++)
		if(used[i] && !indegree[i])
	z.push(i);
	while(!z.empty()){
		v = z.front(); z.pop();
		L.push(v);
		for(int i=0; i<grau[v]; i++){
			w = adj[v][i];
			indegree[w]--;
			if(!indegree[w])
			z.push(w);
		}
	}
}

int nroVert, contRaiz;
vector< pair<int,int> > bridge;
set<int> artPoint;
int low[MAX_V], num[MAX_V];
void initializeArticulation(){
	memset(visited, 0, sizeof(visited));
	memset(p, -1, sizeof(p));
	contRaiz = 0;
	nroVert = 1;
}
void findArticulation(int v){
	int t;
	visited[v] = 1;
	num[v] = low[v] = nroVert++;
	for(int i=0; i<grau[v]; i++){
		t = adj[v][i];
		if(!visited[t]){
			p[t] = v;
			if(num[v] == 1) // conta filhos da raiz na árvore
				contRaiz++;
			findArticulation(t);
			if(low[t] > num[v])
				bridge.push_back(make_pair(v, t));
			if(low[t] >= num[v] && num[v] != 1)
				artPoint.insert(v);
			else if(num[v] == 1 && contRaiz > 1)
				artPoint.insert(v);
			low[v] = MIN(low[v],low[t]);
		} else if(p[v] != adj[v][i])
				low[v] = MIN(low[v],num[t]);
	}
}

int particao[MAX_V]; // marca qual conjunto está um vértice
int visited[MAX_V], grau[MAX_V];
bool is_bipartite;
void _dfsVisit(int s, int p){
	int t;
	visited[s] = 1;
	particao[s] = p;
	for(int i=0; i<grau[s]; i++){
		t = adj[s][i];
		if(!visited[t])
		_dfsVisit(t, !p);
		else
		if(particao[t] == p)
		is_bipartite = false;
	}
}
void bipartite(){
	is_bipartite = true;
	memset(visited, 0, sizeof(visited));
	for(int i=0; i<MAX_V; i++) {
		if(is_bipartite == false)
			break;
		if(grau[i] > 0 && !visited[i])
			_dfsVisit(i,0);
	}
}

int countDAGPaths(int s, int t){
	int u;
	topological_sort();
	memset(d, 0, sizeof(d));
	d[s] = 1;
	while(!L.empty()){
		u = L.front(); L.pop();
		for(int i=0; i<grau[u]; i++)
			d[adj[u][i]] = d[adj[u][i]] + d[u];
	}
	return d[t];
}

#define residue(src, dst) ( c[ (src) ][ (dst) ] -
flow( (src), (dst) ) )
#define flow(src, dst) ( f[ (src) ][ (dst) ] - f[ (dst) ]
[ (src) ])

int f[MAX_V][MAX_V]; // fluxo
int c[MAX_V][MAX_V]; // capacidade = peso das arestas

void initialize(){
	memset(f, 0, sizeof(f));
	memset(c, 0, sizeof(c));
	// se grafo possui arestas paralelas com pesos
	// diferentes, acumula capacidade
	for(int i=0; i<MAXV; i++)
		for(int j=0; j<grau[i]; j++)
			c[i][adj[i][j].v] += adj[i][j].w;
}
int maxFlowEdmondsKarp(int s, int t){
	int F = 0, minCapacity, u, v;
	while(true){
		queue<int> Q;
		memset(p, -1, sizeof(p));
		Q.push(s);
		p[s] = -2;
		// BFS
		while(!Q.empty() && p[t] == -1){
			u = Q.front();
			Q.pop();
			for(int i=0; i<grau[u]; i++){
			v = adj[u][i].v;
			if(p[v] == -1 && residue(u, v) > 0){
			p[v] = u;
			Q.push(v);
		}	
	}
}
	// não encontrou caminho até t
	if(p[t] == -1)
		return F;
	// encontra menor capacidade no caminho
	minCapacity = INF;
	for(v = t, u = p[v]; u >= 0; v = u, u = p[v])
		minCapacity = MIN(minCapacity, residue(u, v));
	// incrementa fluxo no caminho
	for(v = t, u = p[v]; u >= 0; v = u, u = p[v])
		f[u][v] += minCapacity;
	F += minCapacity;
	}
	return F;
}

stack<int> S;
void dfsVisit(int v){
	visited[v] = 1;
	for(int i = 0; i < grau[v]; i++)
		if(!visited[adj[v][i]])
	dfsVisit(adj[v][i]);
	S.push(v);
}
void dfsVisit2(int x){
	visited[x] = id;
	for(int i = 0; i < invGrau[x]; i++)
		if(!visited[invAdj[x][i]])
	dfsVisit2(invAdj[x][i]);
}
void kosaraju(int start, int end){
	memset(visited, 0, sizeof(visited));
	for(int i=start; i<end; i++)
		if(!visited[i])
	dfsVisit(i);
	memset(visited, 0, sizeof(visited)); id = 1;
	while(!S.empty()){
		int u = S.top(); S.pop();
		if(!visited[u]){
		dfsVisit2(u); id++;
	}
}
}

int weight[MAX][MAX], d[MAX+1][MAX];
int n, m;
double MMC(){
	//Initialize
	int k, u, v, s = 0;
	for(k=0 ; k<= n ; k++)
		for(u= 0 ; u<n ; u++)
			d[k][u] = INF;
	d[0][s] = 0;
	//Compute distances
	for(k=1; k<=n ; k++)
		for(v=0 ; v<n ; v++)
			for(u=0 ; u<n ; u++)
				if(weight[u][v] < INF)
					d[k][v] = MIN(d[k][v], d[k-1][u]+weight[u][v]);
	//Compute lambda using karp's theorem
	double lamda = INF;
	for(u=0 ; u<n ; u++){
		double currentLamda = -INF; // changed here
		for(int k=0 ; k<n ; k++)
			if(d[n][u] < INF && d[k][u] < INF)
				currentLamda = MIN(currentLamda, 1.0*(d[n][u]-d[k]
				[u])/(n-k) );
		lamda = MIN(lamda, currentLamda);
	}
	return lamda;
}

//Informação sobre uma aresta
typedef struct{
	int label; //contém um label
	int dest; //e o destino da aresta
}TInfoAr;
int vertices_visitados[MAX_V], //marca vértices visitados - BFS
grau[MAX_V], //grau de cada vértice
vertice_presente[MAX_V], //vértices presentes no grafo achouCiclo, //marca se encontrou um ciclo euleriano
nvt, //Número de vértices
nar, //Número de arestas
inicioCiclo; //Vértice inicial em busca do ciclo euleriano
/* Representação do grafo: Cada elemento guarda um vértice e as
arestas que são adjacentes.
Ex: 1 -> 0 1 2
2 3 2
Vértice 1 está ligado às arestas 0, 1, 2 e estas arestas têm
como destino os vértices
2, 3, 2, respectivamente
*/
TInfoAr va[MAX_V][MAX_A];
//Ciclo euleriano
deque< int > cicloEuleriano;
//Inicializa o grafo
void ini_grafo(int n=0){
	nar = 0;
	nvt = n;
	memset(vertice_presente, 0, sizeof(vertice_presente));
	memset(grau, 0, sizeof(grau));
}
void printGrafo(){
	cout<<nvt<<" "<<nar<<endl;
	for(int i=0; i<MAX_V; i++){
		if(vertice_presente[i]==0) continue;
	cout<<i<<" -> ";
	for(int j=0; j<grau[i]; j++){
		cout<<"("<<va[i][j].dest<<","<<va[i][j].label<<")";
	}
		cout<<endl;
	}
}
//Insere uma aresta no grafo
void aresta(int u, int v){
	//Verifica se os vértices u e v estão no grafo, atualizando o
	//número de vértices e o vetor vertice_presente
	if(vertice_presente[u]==0){ vertice_presente[u]=1; nvt++; }
	if(vertice_presente[v]==0){ vertice_presente[v]=1; nvt++; }
	//Insere a aresta u-v e v-u no grafo
	va[u][ grau[u] ].dest = v; va[u][ grau[u] ].label = nar;
	grau[u]++;
	va[v][ grau[v] ].dest = u; va[v][ grau[v] ].label = nar;
	grau[v]++;
	//Incrementa o número de arestas
	nar++;
}
//Verifica usando o BFS se o grafo é conexo
bool eh_conexo(int inicio){
	queue<int> fila;
	int u, vAux;
	memset(vertices_visitados, 0, sizeof(vertices_visitados));
	fila.push(inicio);
	vertices_visitados[inicio] = 1;
	while(fila.empty()==false){
		u = fila.front(); fila.pop();
		for(int i=0; i<grau[u]; i++){
			vAux = va[u][i].dest;
			if(vertices_visitados[vAux]==0){
			vertices_visitados[vAux]=1;
			fila.push(vAux);
		}
	}
}
	for(int i=0; i<MAX_V; i++)
		if(vertice_presente[i]==1 && vertices_visitados[i]==0)
			return false;
	return true;
}
//Rotaciona o ciclo e obtêm o vértice onde deverá encontrar o novo ciclo
void rotacionaCiclo(){
	//retira o primeiro elemento *1 2 3 4 1 -> 2 3 4 1
	cicloEuleriano.pop_front();
	//Procura um vértice no ciclo euleriano cujo grau seja maior que 0
	int posRot=0;
	for(int i=0; i<cicloEuleriano.size(); i++)
		if(grau[ cicloEuleriano[i] ]>0){ posRot = i;
		inicioCiclo=cicloEuleriano[i]; break; }
	//Coloca o elemento com grau>0 presente no cicloEuleriano no início do ciclo
	rotate(cicloEuleriano.begin(), cicloEuleriano.begin() 
	+posRot, cicloEuleriano.end());
	//Põe no final do ciclo o elemento inicial
	cicloEuleriano.push_back( cicloEuleriano[0] );
	//Tira o elemento inicial que será usado para encontrar o próximo ciclo
	cicloEuleriano.pop_front();
}
void remove_aresta(int u, int v, int lb){
	for(int i=0; i<grau[u]; i++){
		if(va[u][i].label == lb){
			grau[u]--;
			va[u][i].dest = va[u][ grau[u] ].dest;
			va[u][i].label = va[u][ grau[u] ].label;
			break;
	}
}
	for(int i=0; i<grau[v]; i++){
		if(va[v][i].label == lb){
			grau[v]--;
			va[v][i].dest = va[v][ grau[v] ].dest;
			va[v][i].label = va[v][ grau[v] ].label;
			break;
	}
}
	nar--; //decrementa o número de arestas
}
void get_ciclo_euleriano(int u){
	int prox, lb;
	//ainda não achou o ciclo achouCiclo=0;
	// se o grafo não tem arestas, termina
	if(nar==0) return;
	//Enquanto não achou um ciclo euleriano
	while(achouCiclo==0){
		//Insere o vértice no ciclo
		cicloEuleriano.push_front(u);
		//Obtém o próximo vértice do ciclo
		prox = va[u][0].dest;
		lb = va[u][0].label;
		//Remove a aresta do vértice
		remove_aresta(u, prox, lb);
		//atribui ao u o prox
		u = prox;
		//Se o vértice destino da aresta sendo visitada é igual ao
		vértice inicial
		if(u==inicioCiclo)
			achouCiclo=1; //encontrou um ciclo
	}
	//Coloca no cicloEuleriano o vértice inicial novamente, fechando o ciclo
	cicloEuleriano.push_front(u);
}
/* Verifica se o grafo possui ciclo euleriano.
1. Se o grafo não é conexo, termina.
2. Se possui vértice com grau ímpar, termina.
3. Encontra o primeiro ciclo euleriano partindo de u.
4. Se não encontrar um vértice no ciclo euleriano com
grau>1, termina. Senão,
atribui o vértice encontrado à variável inicioCiclo
5. u = inicioCiclo
6. Volta ao passo 3.
*/
void ciclo_euleriano(int u){
	//Verifica se o grafo é conexo
	if(eh_conexo(u)==false){ return; }
		//Verifica se existe algum vértice com grau ímpar
		for(int i=0; i<MAX_V; i++)
			if(vertice_presente[i]==1 && grau[i]%2!=0){ return; }
		//Limpa o ciclo euleriano
		cicloEuleriano.clear();
		inicioCiclo=u;
		while(1){
			//Não achou ciclo
			achouCiclo = 0;
			//Obtém o ciclo euleriano começando em inicioCiclo
			get_ciclo_euleriano(inicioCiclo);
			//Se acabaram as arestas
			if(nar==0) return;
			//Rotaciona o ciclo e encontra o novo inicioCiclo
			rotacionaCiclo();
	}
}
int main(){
	int t, n, u, v;
	scanf("%d", &t);
	for(int iT=0; iT<t; iT++){
		scanf("%d", &n);
		ini_grafo();
		for(int iN=0; iN<n; iN++){
			scanf("%d %d", &u, &v);
			aresta(u, v);
		}
		ciclo_euleriano(u);
		printf("Case #%d\n",iT+1);
		if(cicloEuleriano.size()==0)
			printf("some beads may be lost\n");
		else
		for(int iC=0; iC< cicloEuleriano.size() - 1; iC++)
			printf("%d %d\n",cicloEuleriano[iC],
		cicloEuleriano[iC+1]);
		if(iT!=t-1)
			printf("\n");
	}
}

int length[MAX_V]; // armazena o comprimento maximo na posição
int p[MAX_V]; // pai
int v[MAX_V]; // vetor com a sequência
int n;
void lis(){
	for(int i=0; i<n; i++)
		length[i] = 1;
	memset(p, -1, sizeof(p));
	for(int i=0; i<n-1; i++)
		for(int j=i+1; j<n; j++)
			if(v[j] > v[i])
				if(length[i] + 1 > length[j]){
					length[j] = length[i] + 1;
					p[j] = i;
			}
}

int table[MAX_V][MAX_V];
char a[MAX_V], b[MAX_V];
int lcs(){
	int m, n;
	m = strlen(a); n = strlen(b);
	for(int i=0; i<m; i++)
		for(j=0; j<n; j++)
			table[i][j]=0;
	for(int i=1; i<m+1; i++)
		for(int j=1; j<n+1; j++)
			if(a[i-1]==b[j-1])
				table[i][j] = table[i-1][j-1]+1;
			else
				table[i][j] = MAX(table[i][j-1], table[i-1][j]);
	return table[m][n];
}
void printPath(int i, int j){
	if(i == 0 || j==0)
		return;
	if(a[i-1] == b[j-1]){
		printPath(i-1, j-1);
		printf("%c", a[i-1]);
	}
	else if(table[i-1][j] <= table[i][j-1])
		printPath(i, j-1);
	else
		printPath(i-1, j);
}

int m[MAX_V][MAX_V]; // custos
int s[MAX_V][MAX_V]; // caminho
int p[MAX_V]; // dimensões das matrizes
void initializeMcm(int n){
	for(int i=1; i<n+1; i++)
		for(int j=i; j<n+1; j++)
			m[i][j] = INF;
}
void printPath(int i, int j){
	if(i==j)
		cout << "A" << i;
	else{
		cout << "("; printPath(i,s[i][j]);
		cout << " x "; printPath(s[i][j]+1, j);
		cout << ")";
	}
}
int mcm(int i, int j){ // primeira chamada: mcm(1, n)
	int k, q;
	if(m[i][j] < INF)
		return m[i][j];
	if(i == j)
		m[i][j] = 0;
	else
		for(int k=i; k<j; k++){
			q = mcm(i,k) + mcm(k+1,j) + p[i-1]*p[k]*p[j];
		if(q < m[i][j]){
			m[i][j] = q; s[i][j] = k;
		}
	}
	return m[i][j];
}

int c[MAX_V][MAX_V];
int weight[MAX_V], price[MAX_V];
void knapsack(int n, int w){
	for(int i=0; i<n+1; i++) c[i][0] = 0; // para todos produtos
		for(int i=0; i<w+1; i++) c[0][i] = 0; // para todos pesos
			for(int i=1; i<n+1; i++)
				for(int j=1; j<w+1; j++)
					if(weight[i] > j)
						c[i][j] = c[i-1][j];
					else
						c[i][j] = MAX(c[i-1][j],
	c[i-1][j-weight[i]] + price[i]);
}

#define MATCH 0
#define INSERT 1
#define DELETE 2
#define MAXLEN 1000
typedef struct{
	int c; //custo
	int p; //pai
}TCelula;
TCelula m[MAXLEN+1][MAXLEN+1]; //tabela da programacao dinamica
char s[MAXLEN], t[MAXLEN]; //strings de entrada
int comparaStrings(){
	int i, j, k, opt[3];
	for(i=0; i<MAXLEN; i++){
		m[0][i].c = m[i][0].c = i;
		m[0][i].p = INSERT;
		m[i][0].p = DELETE;
	}
	m[0][0].p = -1;
	for(i=1; i<strlen(s); i++)
		for(j=1; j<strlen(t); j++){
			//os custos podem ser alterados aqui.
			opt[MATCH] = m[i-1][j-1].c +
			(s[i]==t[j] ? 0 : 1); //c = 0 ou 1
			opt[INSERT] = m[ i ][j-1].c + 1; //deleta t[j], c = 1
			opt[DELETE] = m[i-1][ j ].c + 1; //deleta s[i], c = 1
			//Agora começa a escolha da opção menos custosa...
			m[i][j].c = opt[MATCH]; m[i][j].p = MATCH;
			for(k = INSERT; k<=DELETE; k++)
				if(opt[k] < m[i][j].c){
					m[i][j].c = opt[k]; m[i][j].p = k;
		}
	}
	i = strlen(s) - 1;
	j = strlen(t) - 1;
	return( m[i][j].c );
}
// deve ser chamado com i = strlen(s) - 1 e j = strlen(t) - 1;
void reconstroiCaminho(int i, int j){
	if( m[i][j].p == -1 ) 
		return;
	if( m[i][j].p == MATCH ){
		reconstroiCaminho(i-1, j-1);
		if(s[i]==t[j]) 
			printf("M"); //match!
		else 
			printf("S"); //substitution
		return;
	}
	if( m[i][j].p == INSERT ){
		reconstroiCaminho(i, j-1);
		printf("I");
		return;
	}
	if( m[i][j].p == DELETE ){
		reconstroiCaminho(i-1, j);
		printf("D");
		return;
	}
}
int main(){
	int i, j;
	s[0] = t[0] = ' '; //char em 0 nas strings deve ser ' '
	while(true){
		gets(&(s[1]));
		if(feof(stdin))
			break;
		gets(&(t[1]));
		printf("Menor custo para transformar %s em %s: %d
		\n", &(s[1]), &(t[1]), comparaStrings());
		i = strlen(s) - 1; j = strlen(t) - 1;
		reconstroiCaminho(i, j);
		printf("\n");
	}
return 0;
}

map<pair<int, int>, int > tem_sucessor;
map<pair<int, int>, pair<int, int> > sucessor;
map<pair<int, int>, int> cache;
map<pair<int, int>, int> esta_em_cache;
int max_qtd(int n, int i, const VI &ele){
	if(n<=0 || i<=0 || ele.size()==0)
		return 0;
	if(esta_em_cache[make_pair(n,i)]==1)
		return cache[make_pair(n,i)];
	int aux, maximo=0, iMaximo=-1;
	for(int k=0; k<ele.size(); k++){
		VI temp = ele; temp.erase(temp.begin()+k);
		aux=0;
		if(ele[k]<=n)
			aux=ele[k] + max_qtd(n-ele[k], i-1, temp);
		if(aux>maximo)
			maximo=aux, iMaximo=k;
	}
	if(iMaximo>=0){
		sucessor[make_pair(n,i)]=make_pair(n-ele[iMaximo], i-1);
		tem_sucessor[make_pair(n,i)]=1;
	}
	esta_em_cache[make_pair(n,i)] = 1;
	return (cache[make_pair(n,i)]=maximo);
}
void imprimeSol(int n, int t){
	int auxN, auxT;
	while(tem_sucessor[make_pair(n,t)]==1){
		cout<<n-sucessor[make_pair(n,t)].first<<" ";
		auxN=sucessor[make_pair(n,t)].first;
		auxT=sucessor[make_pair(n,t)].second;
		n=auxN;
		t=auxT;
	}
}
int main(){
	while(1){
		int n, t, aux;
		vector<int> durations;
		if(!(cin>>n))
			return 0;
		cin>>t;
		for(int i=0; i<t; i++)
			cin>>aux, durations.push_back(aux);
		sucessor.erase(all(sucessor));
		cache.erase(all(cache));
		esta_em_cache.erase(all(esta_em_cache));
		tem_sucessor.erase(all(tem_sucessor));
		int maximo = max_qtd(n, t, durations);
		imprimeSol(n, t);
		cout<<"sum:"<<maximo<<endl;
	}
	return 0;
}

int coins[] = {1, 3, 4, 5}, coins_length = 4;
int minCoins[MAX];
int coinsChangeMemo(int money){
	if(minCoins[money] > 0)
		return minCoins[money];
	if(money == 0)
		return 0;
	int v = INF;
	for(int c=0; c<coins_length; c++){
		if(coins[c] > money) continue;
		v = min(v, coinsChangeMemo(money - coins[c]) + 1);
	}
	return minCoins[money] = v;
}
int coinsChangeDP(int money){
	minCoins[0] = 0;
	for(int m=1; m <= money; m++){
		minCoins[m] = INF;
		for(int c=0; c<coins_length; c++){
			if(coins[c] > money) continue;
			minCoins[m] = min(minCoins[m], minCoins[m - coins[c]] + 1);
		}
	}
return minCoins[money];
}

#define MAXMONEY 7500 // máximo dinheiro que pode trocar
#define MAXCOINS 5 // máximo número de moedas
int ways[MAXMONEY + 1];
int moedas[MAXCOINS] = { 50, 25, 10, 5, 1 }; //vetor ordenado
void coinsWays(){
	int c;
	ways[0] = 1;
	for(int i=1; i<=MAXMONEY; i++)
		ways[i]=0;
	for(int i=0; i<MAXCOINS; i++){
		c = moedas[i];
	for(int j=c; j<=MAXMONEY; j++)
		ways[j] += ways[j-c];
	}
}
int main(){
	int money;
	coinsWays();
	while(cin>>money)
	printf("%llu\n", ways[money]);
}

#define MAXSIZE 20003
int v[MAXSIZE];
void maxIntervalSum(int n, int &a, int &b, int &maxSum){
	int max[MAXSIZE], start[MAXSIZE];
	for(int i=1; i<=n; i++)
		max[i] = start[i] = 0;
	start[0] = 1;
	for(int i=1; i<=n; i++)
		if(max[i-1] >= 0){
			max[i] += max[i-1] + v[i];
			start[i] = start[i-1];
	} else {
			max[i] += v[i];
			start[i] = i;
	}
	b = 1;
	for(int i=2; i<=n; i++)
	if(max[i] > max[b])
	b = i;
	a = start[b];
	maxSum = max[b];
}
int v[10] = { -INF, -2, 1, -3, 4, -1, 2, 1, -5, 4};
int a, b, maxSum;
maxIntervalSum(9, a, b, maxSum);
//retorna: a = 4, b = 7, maxSum = 6

/* Recebe como parametros o numero de objetos n,
o array de objetos com seus respectivos pesos e valores,
e a capacidade W da mochila */
double mochilaFracNlogN(int n, Object * obj, int W){
	double weight = 0.0; // Peso armazenado na mochila
	double total = 0.0; // Valor total armazenado na mochila
	int i;
	// Ordena os objetos com relacao a razao entre valor/peso
	qsort(obj, n, sizeof(Object), ratioCmp);
	/* Coloca o maior numero de objetos de forma completa na
	mochila, em ordem de razao valor/peso */
	for(i=0; i<n; i++){
		/* Caso nao seja possivel colocar o objeto atual na
		mochila, entao sai do laco */
		if(obj[i].weight + weight > W)
			break;
		obj[i].frac = 1.0; // Coloca todo o objeto i na mochila
		total += obj[i].value; // Atualiza o valor total
		weight += obj[i].weight;// Atualiza o peso total
	}
	/* Se nem todos os objetos couberam na mochila,
	coloca apenas uma fracao do melhor objeto, em termos de
	valor/peso, ainda nao considerado */
	if(i < n){
		/* Coloca apenas a fracao possivel do objeto i */
		obj[i].frac = (W - weight)/(double)obj[i].weight;
		// Atualiza o valor total da mochila
		total += ((double) obj[i].value) * obj[i].frac;
	}
	return total;
}

#define X first
#define Y second

typedef pair<double, double> TPoint;

typedef vector< TPoint > TPolygon;

typedef struct{
	double A, B, C;
}TLine;

typedef struct{
	TPoint c;
	double r;
}Tball;

double point_point_dist(TPoint a, TPoint b){
	return(sqrt( (a.X-b.X)*(a.X-b.X) + (a.Y-b.Y)*(a.Y-b.Y)));
}

/* Distância de ponto a reta
2*A = |AB|*h = |AxB| => h = |AxB|/|AB| */
double signed_point_line_dist(TPoint a, TPoint b, TPoint c){
	return (is_left(a,b,c)/point_point_dist(a,b));
}

double prod_escalar(TPoint a, TPoint b, TPoint u, TPoint v){
	return ((b.X-a.X)*(v.X-u.X) + (b.Y-a.Y)*(v.Y-u.Y));
}