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.