Question

У Поликарпа есть n монет, достоинство i-й монеты равно ai. Поликарп хочет распределить монеты по своим карманам, но он не может класть две монеты одинакового достоинства в один и тот же карман. Например, елси у Поликарпа есть шесть монет, представленных в виде массива a=[1,2,4,3,3,2], он может распределить их по двум карманам следующим образом: [1,2,3],[2,3,4]. Поликарп хочет распределить все имеющиеся у него монеты, используя минимально возможное количество карманов. Помогите ему сделать это. Входные данные Первая строка входных данных содержит одно целое число n (1≤n≤100) — количество монет. Вторая строка входных данных содержит n целых чисел a1,a2,…,an (1≤ai≤100) — достоинства монет. Выходные данные Выведите одно целое число — минимальное возможное количество карманов, необходимое Поликарпу, чтобы распределить все имеющиеся у него монеты таким образом, что никакие две монеты с одинаковым достоинством не лежат в одном и том же кармане. Примеры входные данные 6 1 2 4 3 3 2 выходные данные 2 входные данные 1 100 выходные данные 1

Answer 1

Ответ:

Объяснение:

Python

input()

a = list(map(int, input().split()))

print(max(a.count(i) for i in a))

C++ 17

#include<bits/stdc++.h>

using namespace std;

main(){

   int a[1001],b[10001],n,i,m=0;

   cin>>n;

   for(i=1;i<=n;i++){

       cin>>a[i]; b[a[i]]++;

   }

   for(i=1;i<=1000;i++){

       m=max(m,b[i]);

   }

   cout<<m;

}

Answer 2

Для решения этой задачи мы можем использовать подход с использованием словаря (dictionary) или частотного анализа. Сначала мы пройдемся по всем монетам и подсчитаем, сколько монет каждого достоинства у нас есть. Затем мы посчитаем количество различных достоинств монет и это количество будет минимальным количеством карманов, необходимых Поликарпу.

Вот решение на Python:

pythonCopy code
n = int(input())
coins = list(map(int, input().split()))

coin_counts = {}
for coin in coins:
    if coin in coin_counts:
        coin_counts[coin] += 1
    else:
        coin_counts[coin] = 1

min_pockets = len(coin_counts)
print(min_pockets)

Пример использования:

Copy code
Входные данные:
6
1 2 4 3 3 2

Выходные данные:
2

Copy code
Входные данные:
1
100

Выходные данные:
1

В первом примере у нас есть 6 монет различных достоинств: [1, 2, 4, 3, 3, 2]. Мы можем распределить их по двум карманам: [1, 2, 3] и [2, 3, 4].

Во втором примере у нас есть только одна монета достоинством 100, поэтому нужен только один карман.

Таким образом, мы считаем количество различных достоинств монет и выводим это количество как ответ.