Hello Programmers In this post, you will know how to solve the Chef Feeds Cats Codechef Solution.
One more thing to add, don’t directly look for the solutions, first try to solve the problems of Codechef by yourself. If you find any difficulty after trying several times, then you can look for solutions.
Problem
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 Solutions 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 Solutions 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 BrokenProgrammers. This tutorial is only for Educational and Learning purpose.
Note:- I compile all programs, if there is any case program is not working and showing an error please let me know in the comment section. If you are using adblocker, please disable adblocker because some functions of the site may not work correctly.