Isolation Centers

-

 


Problem Link:Codechef

As a health expert, Vinay is keeping a close watch on the ongoing pandemic of coronavirus disease (COVID-19). He thought of a different situation where there are 2626 types of viruses, named "aorona", "borona", "corona", …, "zorona".

You are given a string SS with length NN. There are NN people (numbered 11 through NN) and for each valid ii, the ii-th person is infected by exactly one type of virus named SiSiorona (i.e. "corona" with the first letter replaced by the ii-th character of SS).

You should answer QQ queries. In each query:

·       You are given an integer, CC denoting the number of available isolation centers.

·       Each isolation center has an infinite capacity, but with the restriction that two people infected with the same type of virus cannot stay in the same isolation center.

·       There is also a pending queue with an infinite capacity and there are no restrictions on which people can be in the pending queue.

·       Initially, the isolation centers and pending queue are empty.

·       Each of the NN people should be placed in either the pending queue or one of the isolation centers.

·       Since Vinay is busy finding a vaccine, he asks Swapnil to find a way to place the people in the pending queue and isolation centers such that the number of people in the pending queue are the smallest possible.

·       Help Swapnil finds the size of the pending queue in that case.

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 QQ.

·       The second line contains a single string SS.

·       Each of the following QQ lines contains a single integer CC describing a query.

Output

For each query, print a single line containing one integer ― the minimum size of the pending queue.

Constraints

·       1≤T,N,Q≤1051≤T,N,Q≤105

·       0≤C≤1090≤C≤109

·       |S|=N|S|=N

·       SS contains only lowercase English letters

·       the sum of NN over all test cases does not exceed 105105

·       the sum of QQ over all test cases does not exceed 105105

Subtasks

Subtask #1 (20 points): T,N,Q,C≤10T,N,Q,C≤10

Subtask #2 (80 points): original constraints

Example Input

1

20 2

stayinghomesaveslife

1

3

Example Output

6

0

Explanation

Example case 1: In the pending queue for the first query, there should be 22 people with "eorona", 22 with "sorona", 11 with "aorona" and 11 with "iorona".

 

 

Solution:

t=int(input())

while(t>0):

    t-=1

    n,q=map(int,input().split())

    s=input()

    a=[0]*26

    for i in range(len(s)):

        a[ord(s[i])-97]+=1

    

    while(q>0):

        s=0

        q-=1

        c=int(input())

        for i in range(len(a)):

            if (a[i]>c):

                s+=(a[i]-c)

        print(s)

       

        



Comments

Post a Comment

Popular posts from this blog

Trouble with the Number System

-
Image
  Barua has developed his own Operating System known as "Barua OS" ( BOS ). One day while booting up his system he runs into a bug. You want to impress Barua so you jump in and offer to solve the bug yourself. Barua doesn't like binary numbers very much and his operating system uses a new number system called BNS ( Barua Number System ). The following are the properties of a number represented in BNS form : 1.       The number can only be made up of 2 distinct digits, one or zero. 2.       The number cannot start with zero. 3.       The number can have any number of zeroes, but only one instance of the digit one. For example 100, 1000, 10000 are Barua Numbers whereas 101, 502, 625 are not Barua Numbers. Unfortunately one decimal number has crept into a list of Barua Numbers and Barua OS cannot find its product. Can you? Input Format: First line contains an integer N, total number of elements in...
Read more

Residue Arithmetic

-
Image
  For operators with large integers, residue arithmetic is used. A residue of a number n modulo a prime p is defined as the remainder obtained when we divide a by p. For example, if the residue of 100 modulo 3 is 1. Two large primes are chosen and all numbers are expressed as modulo those primes. For example, if 7 and 3 were chosen as the primes, 25 would be represented as 4,1 in this representation, 3 would be represented as 3,3 and 30 would be represented as 2,0. Now if we do 25 * 3 - 30 in this model, we do the operation and compute the residue of the result with each of the primes in turn. SO with respect to prime 7, the result is 4 * 3 - 2 or 10 which has a residue of 3 modulo 7. With respect to 13, the operation is 12 * 3 - 4 = 32 whose residue is 6 modulo 13. Hence the result is 3,6 in the residue notation. There is only one number less than 91 which has this representation, and that is 45, which is what we expect. In this problem, we will be given 3 numbers a,b and c in res...
Read more

Perfect Peak of Array

-
Image
Problem Description Given an integer array  A  of size  N . You need to check that whether there exists an element which is  strictly greater than all the elements on the left  of it and  strictly smaller than all the elements  on the right of it. If it exists return  1  else return  0 . NOTE: Do not consider the corner elements i.e  A[0] and A[N-1]  as the answer. Problem Constraints 3 <= N <= 10 5 1 <= A[i] <= 10 9 Input Format First and only argument is an integer array  A  containing  N  integers. Output Format Return  1  if there exist a element that is  strictly greater than all the elements on left  of it and  strictly smaller than all the elements  on right of it else return  0. Example Input Input 1: A = [5, 1, 4, 3, 6, 8, 10, 7, 9] Input 2: A = [5, 1, 4, 4] Example Output Output 1: 1 Output 2: 0 Example Explanation Explanation 1: A[4] = 6 is the e...
Read more