Chef Feeds Cats Codechef Solution: Chef owns NN cats (numbered 11 through NN) and he wants to feed them. There are MM identical cans of cat food; each can must be used to feed exactly one cat and Chef can only feed one cat at a time. Chef wrote down the order in which he wants to feed the cats: a sequence A1,A2,…,AMA1,A2,…,AM.
An order of feeding cats is fair if there is no moment where Chef feeds a cat that has already been fed strictly more times than some other cat. Help Chef — tell him if the order in which he wants to feed the cats is fair.
Input
- The first line of the input contains a single integer TT denoting the number of test cases. The description of TT test cases follows.
- The first line of each test case contains two space-separated integers NN and MM.
- The second line contains MM space-separated integers A1,A2,…,AMA1,A2,…,AM.
Output
For each test case, print a single line containing the string "YES" if the order is fair or "NO" if it is unfair.
Constraints
- 1≤T≤1001≤T≤100
- 2≤N≤1002≤N≤100
- 1≤M≤1031≤M≤103
Sample Input 1
7 3 9 1 2 3 1 2 3 1 2 3 3 9 1 2 3 3 2 1 1 2 3 3 5 2 3 1 1 2 3 6 2 1 1 3 2 3 2 8 1 2 1 2 1 2 1 1 5 3 5 3 1 4 5 1 2 3 1 4
Sample Output 1
YES YES YES NO NO YES NO
Explanation
Example case 4: Cat 11 will eat twice before cat 33 eats even once, so the order is unfair.
Example case 5: The order is unfair because cat 11 will eat its fifth can before cat 22 eats its fourth can.
Example case 7: The order is unfair because cat 11 will eat twice before cat 44 eats even once.
Chef Feeds Cats CodeChef Solution in JAVA
import java.util.*;
import java.lang.*;
import java.io.*;
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
// your code goes here
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while(t-->0)
{
int n = sc.nextInt();
int m = sc.nextInt();
ArrayList<Integer> al = new ArrayList<Integer>();
int [] arr = new int[m];
boolean flag = false;
for(int i=0;i<m;i++)
{
arr[i] = sc.nextInt();
if (al.size() == n) al.clear();
if (!al.contains(arr[i])) al.add(arr[i]);
else flag = true;
}
System.out.println(flag ? "NO" : "YES");
}
}
}
Chef Feeds Cats CodeChef Solution in CPP
#include <iostream>
#define ll long long int
#include <vector>
#include <map>
#include <unordered_map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#define mod 1000000007
#include <cmath>
#define run(a, m) for(int i = 0 ; i <m; i++ ) cin>>a[i]
#define run2(a, m) for(int i = 0 ; i <m; i++ ){ll v,u; \
cin>>u>>v; \
a[u]push_back(v);}
#define cl cout<<"\n";
using namespace std;
// C++ implementation of Naive method to print all
// divisors
#include <iostream>
using namespace std;
// function to print the divisors
void printDivisors(int n)
{
for (int i = 1; i <= n; i++)
if (n % i == 0)
cout <<" " << i;
}
ll power(ll x, ll y)
{
ll temp;
if( y == 0)
return 1;
temp = power(x%mod, y / 2);
if (y % 2 == 0)
return ((temp%mod )* (temp%mod))%mod;
else
return ((((x%mod) * (temp%mod))%mod) * (temp%mod))%mod;
}
ll power2(ll x, ll y)
{
ll temp;
if( y == 0)
return 1;
temp = power(x, y / 2);
if (y % 2 == 0)
return ((temp )* (temp));
else
return ((((x) * (temp))) * (temp));
}
ll countWays(ll n)
{
ll count = 0;
for (ll i = 1; i * i < n; i++)
if (n % i == 0)
count++;
return count;
}
ll gcd(ll i,ll m)
{
ll k = __gcd(i, m);
cout<<"k:"<<k<<endl;
if( k == 1&&i !=1)return 0;
else if( k == 1&&i==1)return 1;
else if(i/k == m)return 1;
else return gcd(i/k,m);
}
vector<vector<ll>>adj_list;
void getthebinarystring(ll k, string &p)
{
if(k == 0 )
return ;
else if(k%2==0)
{
p='0'+p;
}
else p='1'+p;
getthebinarystring(k>>1,p);
}
vector<pair<ll, ll>>boo;
ll solve()
{
ll k , m ;
cin>>k>>m ;
ll vb = 1;
bool truth = true;
vector<bool>n(k+1, false);
while( vb <= m ){
ll p ; cin>>p;
if(!n[p]){ n[p] = true ; }
else { truth = false ; }
if( vb %k == 0)n.assign(k+1, false);
vb+=1;
}
if(truth)cout<<"YES\n";
else cout <<"NO\n";
}
int main()
{
ll t= 1;
cin>>t ;
while(t--)
{
solve();
}
return 0;
}
Chef Feeds Cats CodeChef Solution in Python
from math import *
import sys
def input():
return sys.stdin.readline().replace('\n','').strip()
sys.setrecursionlimit(10**9)
for _ in range(int(input())):
n,m = list(map(int,input().split()))
l = list(map(int,input().split()))
d = {}
for i in range(m):
if l[i] not in d:
d[l[i]] = 1
else:
d[l[i]]+= 1
for j in d.keys():
if d[j] > d[l[i]]:
print("NO")
break
else:
continue
break
else:
print("YES")
Disclaimer: The above Problem (Chef Feeds Cats) is generated by CodeChef but the solution is provided by Chase2learn.This tutorial is only for Educational and Learning purpose.