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