Light OJ 1148 – Mad Counting [hints+solution]

Posted on March 16, 2019 by Mobarak Hosen Shakil — Leave a comment

Hints:

Mad Counting , It’s really a mad counting problem. To solved this problem, you have to think in a different way while you are counting. Since we have to count the minimum possible populations, It’s only possible when we can minimize the teams they are supported. Let’s discuss with an example:-

if N = 1; and poll result = 2. The minimum possible population will be 3. Since the person who is answered poll without including him.
if N = 2; and poll result = 2, 2. the minimum possible population will be 3. SInce both of them said same answer, so we can say that both them in same team and another one.
if N = 3; and poll result = 2, 2, 2. Then the minimum possible population will be also 3. Since all the three members said same answers, so similarly we can say that all of them in same team.
if N = 4; and poll result = 2, 2, 2, 2. what will be the minimum possible population now? Here answer is 6. Why? Because 1st person was predicted that the 2nd and 3rd person also supports same team as s/he does. The 4th person supports another team and including another two person.So, 3 + 3 = 6.

I hope you will understand now. Also i have attached my solution. Don’t see before try by yourself

Code:

/******************************************
          Mobarak Hosen Shakil
        ICE, Islamic University
     ID: mhiceiuk(all), 29698(LOJ)
   E-mail: mhiceiuk @ (Gmail/Yahoo/FB)
 Blog: https://iuconvergent.wordpress.com
*******************************************/

#include<bits/stdc++.h>
using namespace std;
#define IOS ios_base::sync_with_stdio(0);cin.tie(0)
#define LL long long int
#define ULL unsigned LL

const int inf=1<<30;
const LL INF=1e18;
const int MOD=1e9+7;

int main()
{
    int tn;
    scanf("%d", &tn);
    for(int cs=1; cs<=tn; cs++)
    {
        int n;
        scanf("%d", &n);
        int a[n+2];
        for(int i=0; i<n; i++)
        {
            scanf("%d", &a[i]);
            a[i] = a[i]+1;
        }
        sort(a, a+n);
        int res=0;


        for(int i=0; i<n;)
        {
            int x = a[i];
            int cnt = 0;
            while(x==a[i] && i<n)
            {
                cnt++;
                i++;
            }

            if(cnt>x)
            {
                int y = (cnt+x-1)/x;
                res  += (y*x);
            }
            else res += x;
        }

        printf("Case %d: %d\n", cs, res);
    }
    return 0;
}