Chef Feeds Cats Codechef Solution

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.

Leave a Comment