Programming & Computer Science Answers

Anik’s family has a very strange eid tradition. On the day of eid, each member of the family has to offer some kind of gifts to each person they greet for the second time. The first time they meet they share only eid greetings and hug each other. Every time after that, they exchange gifts. Now, Anik has bought a lot of Toblerone chocolates as gifts. But after eating one himself, he finds that he doesn’t want to giveaway those chocolates. He knows who are visiting his room and in which order. He wants to know for each person in his list if he has to give a chocolate or not. He is not good at coding and not familiar with your coding expertise. Therefore, he came to you for help.

He has names of n people who will visit him in the given order. You need to tell, for each person, if Anik has to give gift or not.

Input Format

First line of input contains an integer n (1 ≤ n ≤ 100) — the number of names in Anik’s list. Next n lines each contain a string, consisting of lowercase English letters. The length of each string is between 1 and 100.

Constraints

n (1 ≤ n ≤ 100)

Output Format

Output n lines each containing either "YES" or "NO" (without quotes), depending on whether Anik need to give gift or not for the ith person in the list.

Sample Input 0

6
tom
lucius
ginny
harry
ginny
harry

Sample Output 0

NO
NO
NO
NO
YES
YES

Sample Input 1

3
a
a
a

Sample Output 1

NO
YES
YES

For the New Year's eve, you and your friends are going to fly sky lanterns ('Fanush') at the university campus. You have planned to do it at the night on January 14, 2021. Unfortunately, only one of your friends came to join. Another problem is that one cannot prepare the lantern alone and needs help from another person. So you two together will have to prepare each lanterns. After setting the fire, when one lantern starts to fly, you start to prepare another. You have bought a number of lanterns and they need different amount of times (bigger lanterns need more time) to start flying. As you are not allowed to stay for a long period, the university permitted you for a limited amount of time. You know the amount of time needed to fly for each lanterns. Your target is to fly as many sky lanterns as possible.

Determine the maximum number of lanterns that you will be able to fly.

Sample input:

2

7

3

1 4 9

100

3

150 200 101

Sample output:

2

Bad day!

Input Format

The first line contains an integer T, the number of test cases.

The first line of each test cases will contain an integer t, the allowed time in minutes.

The second line of the test case will contain an integer n, the number of sky lanterns.

Then the following line will contain a sequence of n numbers a1, a2 ... an where ai denotes the amount of time (in minute) needed to fly for i-th lantern.

Constraints

t>=0 and t<=1000

n>0

ai>=0

Output Format

For each test case, print a single integer N which denotes the maximum number of lanterns that you will be able to fly.

If you are unable to fly any lantern within the alotted time, then print "Bad day!".

Sample Input 0

2
7
3
1 4 9
100
3
150 200 101

Sample Output 0

2
Bad day!

Suppose you are a billionaire businessman and have recently bought a football club. You have also bought many star players from over the world. But for some reasons, you have not selected a coach yet to run your football club. One day, you had a thought, "Why don’t I coach my own team?!!" Now, you want to act upon this thought and want to coach your own team in your own style. You have n players in your team under your control and you have to compose exactly two teams of the same size (two teams because, you want to test each of the team’s strengths by playing them against each other) consisting of some subset of your players. Each player has his own skill in football and the i-th player’s skill is denoted by an integer ai . Naturally, different players can have the same skills.

Now, the match will be valid if

• The first team should consist of players with distinct skills (i.e. all skills in the first team are unique).
• The second team should consist of players with the same skills (i.e. all skills in the second team are equal).

Note that it is permissible that some player of the first team has the same skill as a player of the second team.

Consider some formation:

• [1,2,3], [4,4] is not a good pair of teams because sizes should be the same;
• [1,1,2], [3,3,3] is not a good pair of teams because the first team should not contain players with the same skills;
• [1,2,3], [3,4,4] is not a good pair of teams because the second team should contain players with the same skills;
• [1,2,3], [3,3,3] is a good pair of teams;
• [5], [6] is a good pair of teams.

Your task is to find the maximum possible size p for which it is possible to compose a valid pair of teams, where each team size is p. A player cannot be part of more than one team.

Input Format

The first line of the input contains one integer t (1≤t≤10^4) — the number of test cases. Then t test cases follow.

The first line of the test case contains one integer n (1≤n≤2⋅10^5) — the number of players. The second line of the test case contains n integers a1,a2,…,an (1≤ai≤n), where ai is the skill of the i-th player.

Constraints

t (1≤t≤10^4), n (1≤n≤2⋅10^5)

Output Format

For each test case, print the answer — the maximum possible size p for which it is possible to compose a valid pair of teams, where each team size is p.

Sample Input 0

4
7
4 2 4 1 4 3 4
5
2 1 5 4 3
1
1
4
1 1 1 3

Sample Output 0

3
1
0
2

Aarong is a chain of Bangladeshi department stores and owned by BRAC. It provides the market linkage through different retail outlets. Recently, they have decided to build several storehouse along the highway, each one located at an outlets and supplying several of the outlets with the needed goods. Generally, these storehouses should be placed so that the average distance between a outlet and its assigned storehouse is minimized. You are to write a program that computes the optimal positions and assignments of the storehouses.

To make this more precise, the management of Aarong has issued the following specification: You will be given the positions of n restaurants along the highway as n integers d1 < d2 <……< dn (these are the distances measured from the company’s head outlet, which happens to be at the same highway). Furthermore, a number k (k ≤ n) will be given, the number of storehouse to be built.

The k storehouses will be built at the locations of k different restaurants. Each outlet will be assigned to the closest storehouse, from which it will then receive its supplies. To minimize shipping costs, the total distance sum, defined as

must be as small as possible.

Write a program that computes the positions of the k storehouses, such that the total distance sum is minimized.

Input Format

The input file contains several descriptions of Aarong chains. Each description starts with a line containing the two integers n and k. Following this will n lines containing one integer each, giving the positions di of the restaurants, ordered increasingly.

The input file will end with a case starting with n = k = 0. This case should not be processed.

Constraints

1 ≤ n ≤ 200

1 ≤ k ≤ 30

k ≤ n.

Output Format

For each chain, first output the number of the chain. Then output an optimal placement of the storehouse as follows: for each storehouse output a line containing its position and the range of outlets it serves. If there is more than one optimal solution, output any of them. After the storehouse descriptions output a line containing the total distance sum, as defined in the problem text. Output a blank line after each test case.

Sample Input 0

6 3
5
6
12
19
20
27
0 0

Sample Output 0

Chain 1
Total distance sum = 8

Zahir is a young skating newbie, and he is learning to how to skate at the Chandrima Udyan each morning. As he is just learning the basics he can only move from one pathway to another by drifting north, east, south or west until he lands in another pathway. He has noticed that it’s impossible to get from some paths to some other by any sequence of moves if he follows that drifting rule. He now wants to go to some additional pathways, so that he can get from any pathway to any other one. He asked you to find the minimal number of pathways that need to be created. Assume all pathways to be at integer coordinates.

Input Format

The first line of input contains a single integer n (1 ≤ n ≤ 55) — the number of pathways. Each of the following n lines contains two integers xi and yi (1 ≤ xi, yi ≤ 1000) — the coordinates of the i-th pathway. Note that the north direction coinсides with the direction of y axis, so the east direction coinсides with the direction of the x axis. All pathway’s locations are distinct.

Constraints

n (1 ≤ n ≤ 55) (1 ≤ xi, yi ≤ 1000)

Output Format

Output the minimal number of pathways that need to be created in order for Zahir to be able to reach any pathway from any other one.

Sample Input 0

2
2 1
1 2

Sample Output 0

1

Sample Input 1

2
2 1
4 1

Sample Output 1

0