Largest Family Codechef Solution | LARGEFAM | (100/100) FULL | Codechef July Lunchtime | AC Code

A certain parallel universe has exactly people living in it.

The -th of these people claims that they are the parent of exactly of these people.

However, some of these people might be lying — the -th person may be either telling the truth (in which case they have exactly children) or lying (in which case they can have any number of children).

It is known that each person has at most one parent. Further, as one would expect, it is not allowed for a person’s child to also be their ancestor.

What is the maximum possible number of truth-tellers in this universe?

Input Format

  • The first line of input will contain a single integer , denoting the number of test cases.
  • Each test case consists of two lines of input.
  • The first line of each test case contains a single integer the number of people.
  • The second line of each test case contains space-separated integers

    Output Format

    For each test case, output on a new line the maximum number of people that can be telling the truth.

    Sample Input 1

    4
    2
    1 0
    2
    1 1
    3
    2 0 1
    5
    2 3 1 2 3
    

    Sample Output 1

    2
    1
    2
    2
    
    				
    					#include <bits/stdc++.h>
    #define ll long long
    using namespace std;
    
    void solve()
    {
        ll ok = 1, n;
    
        if (ok != 1)
        {
            ll ji = 0;
        }
        else
        {
            cin >> n;
        }
        vector<ll> x;
        ll z = 0;
        for (ll i = 0; i < n; i++)
        {
            ll y;
            cin >> y;
            if (y == 0)
                z++;
            else
                x.push_back(y);
        }
    
        sort(x.begin(), x.end());
        for (ll i = 0; i < z; i++)
            x.push_back(0);
    
        ll o = 0, p = 1;
        for (ll i = 0; i < n; i++)
        {
            int f = 1;
            for (ll k = 0; k < x[i]; k++)
            {
                if (p < n)
                    p++;
                else
                {
                    f = 0;
                    break;
                }
            }
            o += f;
        }
        cout << o << endl;
    }
    
    int main()
    {
    #ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif
    
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        ll T;
        cin >> T;
        while (T--)
        {
            solve();
        }
        return 0;
    }
    				
    			

    0 Comments

    Leave a Reply

    Avatar placeholder

    Your email address will not be published.