[C언어] CodeForces 1032A Kitchen Utensils 문제

A. Kitchen Utensils

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

The king's birthday dinner was attended by k$k$ guests. The dinner was quite a success: every person has eaten several dishes (though the number of dishes was the same for every person) and every dish was served alongside with a new set of kitchen utensils.

All types of utensils in the kingdom are numbered from 1$1$ to 100$100$. It is known that every set of utensils is the same and consist of different types of utensils, although every particular type may appear in the set at most once. For example, a valid set of utensils can be composed of one fork, one spoon and one knife.

After the dinner was over and the guests were dismissed, the king wondered what minimum possible number of utensils could be stolen. Unfortunately, the king has forgotten how many dishes have been served for every guest but he knows the list of all the utensils left after the dinner. Your task is to find the minimum possible number of stolen utensils.

Input

The first line contains two integer numbers n$n$ and k$k$ (1≤n≤100,1≤k≤100$1\le n\le 100,1\le k\le 100$)  — the number of kitchen utensils remaining after the dinner and the number of guests correspondingly.

The next line contains n$n$ integers a1,a2,…,an$a_1,a_2,\dots ,a_n$ (1≤ai≤100$1\le a_i\le 100$)  — the types of the utensils remaining. Equal values stand for identical utensils while different values stand for different utensils.

Output

Output a single value — the minimum number of utensils that could be stolen by the guests.

Examples

input

Copy

5 2
1 2 2 1 3

output

Copy

1

input

Copy

10 3
1 3 3 1 3 5 5 5 5 100

output

Copy

14

Note

In the first example it is clear that at least one utensil of type 3 has been stolen, since there are two guests and only one such utensil. But it is also possible that every person received only one dish and there were only six utensils in total, when every person got a set (1,2,3) of utensils. Therefore, the answer is 1.

One can show that in the second example at least 2dishes should have been served for every guest, so the number of utensils should be at least 24: every set contains 4 utensils and every one of the 3 guests gets two such sets. Therefore, at least 14 objects have been stolen. Please note that utensils of some types (for example, of types 2 and 4  in this example) may be not present in the set served for dishes.

글을 다썼는데 티스토리가 멈춰서 다시쓴다.ㅜㅜ

이문제는 해석하자면 

왕의 생일의 K명의 손님을 초대한다. 왕은 손님에게 요리를 해주는데 요리에 맞는 식사도구(untensil)을 제공한다. ex ) 스테이크는 포크,나이프 가필요함

그 요리에는 몇가지 도구의 식사도구를 제공할지는 모른다.

식사 대접이후 K명의 손님들은 떠나고 왕은 남은 N개의 식사도구를 모은다.

그 도구들을 (정수값) 들을 분석하여 최소 몇개의 식사도구가 없어졌는지 찾는것이다.

입출력을 보고 이해하는데 조금시간이걸렸지만 1번 입출력에대해서 간단하게설명하자면

input

5 2

1 2 2 1 3

ouput

1

이다.

N개 (5개)의 식사도구가 걷어졌고 몇개의 접시가 제공됐는지는 알수없음 K명의 손님(2명) 이 떠났고.

1 번도구는 2개 2번도구는 2개 3번 도구는 1개가 걷어졌다.

그 이후 2명은 한번의 한도구씩만 사용하므로 (1,2,3) 이라는 하나의 집합이 완성됨 근데 나머지 집합을 만들면 (1,2) 가 되고 

3이 부족하다그러면 1개의 도구가 사라진것이다.

그러므로 문제를 풀려면 가장 많은 값의 도구를 K로 나누어서 (나누기이후 또 K로나눴을때 나머지가0이되도록 처리해야함)

최소 필요한 접시와 K명의 수를 곱하고 그값을 가장많은 도구의 집합의 갯수만큼 곱한다음 N만큼 빼주면

답이나온다. 설명을 잘못한거같지만.. 직접이해해야 뭔가 이해할수있는 문제인것 같다.

#include <stdio.h>
 
void kitchen_utensils()
{
    int N, K;
    scanf("%d %d", &N, &K);
    int i;
    int cnt[101] = { 0 };
    int max_index = 0;
    int U_cnt = 0; //도구종류 cnt
    int num;
    int K2 = 1;
    for (i = 0; i < N; i++)
    {
        scanf("%d", &num);
        if (cnt[num] == 0)
        {
            cnt[num]++;
            U_cnt++; 
        }
        else
        {
            cnt[num]++;
        }
        if (cnt[num] > cnt[max_index])
        {
            max_index = num;
        }
    }
    while (1) // 만약 K가 3이고 cnt가 4이면 2개의Set 이되야하는데 1이되므로 %K가 0이될때까지 ++시킨다
    {
        if (cnt[max_index] % K == 0)
        {
            K2 = cnt[max_index] / K;
            break;
        }
        else
            cnt[max_index]++;
    }
    printf("%d", (K*U_cnt*K2)-N);
}
int main()
{
    kitchen_utensils();
}