Algorithm
Problem Name: 2 AD-HOC - beecrowd | 2341
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/2341
Número de Envelopes
Por OBI - Olimpíada Brasileira de Informática 2009 
Brazil
Timelimit: 1
Aldo é um garoto muito esperto que adora promoções e sorteios. Como já participou de muitas promoções da forma “para participar, envie n rótulos de produtos ...”, Aldo tem o costume de guardar o rótulo de todos os produtos que compra. Dessa forma, sempre que uma empresa faz uma promoção ele já tem um monte de rótulos para mandar.
A SBC (Super Balas e Caramelos) está fazendo uma nova promoção, e, como era de se esperar, Aldo quer participar. Para participar da promoção é preciso enviar um envelope contendo um rótulo de cada tipo de bala que a SBC produz. Por exemplo, se a SBC produz 3 tipos de balas, A, B, C, e uma pessoa tem 3 rótulos de A, 3 de B e 2 de C, ela pode enviar no máximo 2 envelopes, já que falta um rótulo de C para compor o terceiro envelope. Não há limite para o número de envelopes que uma pessoa pode enviar.
Balas são a segunda coisa de que Aldo mais gosta (a primeira como você sabe são promoções). Por causa disso a quantidade de rótulos de balas que ele tem é muito grande, e ele não está conseguindo determinar a quantidade máxima de envelopes que ele pode enviar.
Como você é o melhor amigo de Aldo ele pediu sua ajuda para fazer o cálculo, de modo que ele compre o número exato de envelopes.
Você deve escrever um programa que, a partir da lista de rótulos de Aldo, calcula o número máximo de envelopes válidos que ele pode enviar.
Entrada
A entrada contém um único conjunto de testes, que deve ser lido do dispositivo de entrada padrão (normalmente o teclado).
A primeira linha contém dois números inteiros N (1 ≤ N ≤ 1000000) e K (1 ≤ K ≤ 1000) representando respectivamente a quantidade de rótulos de balas que Aldo possui e o número de tipos diferentes de bala que a SBC produz. Os tipos de balas são identificados por inteiros de 1 a K. A segunda linha contém N números inteiros Xi, cada um representando um rótulo de bala que Aldo possui (1 ≤ Xi ≤ K, para 1 ≤ i ≤ N).
Saída
Seu programa deve imprimir, na saída padrão, o número máximo de envelopes válidos que Aldo pode enviar.
| Exemplos de Entrada | Exemplos de Saída |
|
10 2 1 1 1 1 1 2 2 2 2 2 |
5 |
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <stdio.h>
#define true 1
#define false 0
#define MAX 1100
#define INF 0x3f3f3f3f3f
#define MIN(a, b) a < b ? a : b
unsigned rotulos[MAX];
int compara(unsigned *, unsigned *);
int main (void)
{
unsigned i;
unsigned n, m, tmp, ans;
scanf("%u %u", &n, &m);
for (i = 0; i < n; ++i)
scanf("%u", &tmp), rotulos[tmp]++;
ans = INF;
for (i = 1; i < = m; ++i)
ans = MIN(ans, rotulos[i]);
printf("%u\n", ans);
}
Input
1 1 1 1 1 2 2 2 2 2
Output
#2 Code Example with C++ Programming
Code -
C++ Programming
#include <cstdio>
int vetor[1010];
int min(int x, int y) {
if (x < y) return x;
return y;
}
int main() {
int n, k, resposta = 2147483647;
scanf("%d %d", &n, &k);
while (n--) {
int davez;
scanf("%d", &davez);
vetor[davez]++;
}
for (int i = 1; i < = k; i++) resposta = min(resposta, vetor[i]);
printf("%d\n", resposta);
return 0;
}
Input
1 1 1 1 1 2 2 2 2 2
Output