Solve in Java or C++ Farmer John has an important task - figuring out what type...
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
Solve in Java or C++ Farmer John has an important task - figuring out what type of hay to buy for his cows. Farmer John's N cows (2 ≤ N≤ 105) are numbered 1 through N and each cow likes exactly one type of hay hị (1 ≤ hi ≤ N). He wants all his cows to like the same type of hay. To make this happen, Farmer John can host focus groups. A focus group consists of getting all cows in a contiguous range numbered i to j, inclusive, together for a meeting. If there is a type of hay that more than half the cows in the group like, then after the focus group finishes meeting, all cows end up liking that type of hay. If no such type of hay exists, then no cows change the type of hay they like. For example, in focus group consisting of a range of 16 cows, 9 or more of them would need to have the same hay preference to cause the remaining cows to switch their preference to match. Farmer John wants to know which types of hay can become liked by all cows simultaneously. He can only host one focus group at a time, but he can run as many focus groups as necessary to get all cows to like the same type of hay. INPUT FORMAT (input arrives from the terminal / stdin): The first will consist of an integer T, denoting the number of independent test cases (1 ≤ T ≤ 10). The first line of each test case consists of N. The second line consists of N integers, the favorite types of hay hi for the cows in order. It is guaranteed that the sum of N over all test cases does not exceed 2. 105. OUTPUT FORMAT (print output to the terminal / stdout): Output T lines, one line per test case. If it possible to make all cows like the same type of hay simultaneously, output all possible such types of hay in increasing order. Otherwise, output -1. When printing a list of numbers on the same line, separate adjacent numbers with a space, and be sure the line does not end with any extraneous spaces. SAMPLE INPUT: 5 5 1 2 2 2 3 6 1 2 3 1 2 3 6 1 1 1 2 2 2 3 32 3 2 21 SAMPLE OUTPUT: 2 -1 1 2 3 -1 In the sample input, there are 5 test cases. In the first test case, it is only possible to make all cows like type 2. FJ can do this by running a single focus group with all cows. In the second test case, we can show that no cows will change which type of hay they like. In the third test case, it is possible to make all cows like type 1 by running three focus groups - first by having cows 1 through 4 in a focus group, then by having cows 1 through 5 in a focus group, then by having cows 1 through 6 in a focus group. By similar logic, using cows 3 through 6, cows 2 through 6, then cows 1 through 6, we can make all cows like type 2. In the fourth test case, it is possible to make all cows like type 3 by running a single focus group with all cows. In the fifth test case, we can show that no cows will change which type of hay they like. SCORING: ● ● ● Input 2: N = 2. Inputs 3-4: N < 50. Inputs 5-6: h₂ ≤ hi+1 for all 1 ≤ i ≤N-1. Inputs 7-15: No additional constraints. Solve in Java or C++ Farmer John has an important task - figuring out what type of hay to buy for his cows. Farmer John's N cows (2 ≤ N≤ 105) are numbered 1 through N and each cow likes exactly one type of hay hị (1 ≤ hi ≤ N). He wants all his cows to like the same type of hay. To make this happen, Farmer John can host focus groups. A focus group consists of getting all cows in a contiguous range numbered i to j, inclusive, together for a meeting. If there is a type of hay that more than half the cows in the group like, then after the focus group finishes meeting, all cows end up liking that type of hay. If no such type of hay exists, then no cows change the type of hay they like. For example, in focus group consisting of a range of 16 cows, 9 or more of them would need to have the same hay preference to cause the remaining cows to switch their preference to match. Farmer John wants to know which types of hay can become liked by all cows simultaneously. He can only host one focus group at a time, but he can run as many focus groups as necessary to get all cows to like the same type of hay. INPUT FORMAT (input arrives from the terminal / stdin): The first will consist of an integer T, denoting the number of independent test cases (1 ≤ T ≤ 10). The first line of each test case consists of N. The second line consists of N integers, the favorite types of hay hi for the cows in order. It is guaranteed that the sum of N over all test cases does not exceed 2. 105. OUTPUT FORMAT (print output to the terminal / stdout): Output T lines, one line per test case. If it possible to make all cows like the same type of hay simultaneously, output all possible such types of hay in increasing order. Otherwise, output -1. When printing a list of numbers on the same line, separate adjacent numbers with a space, and be sure the line does not end with any extraneous spaces. SAMPLE INPUT: 5 5 1 2 2 2 3 6 1 2 3 1 2 3 6 1 1 1 2 2 2 3 32 3 2 21 SAMPLE OUTPUT: 2 -1 1 2 3 -1 In the sample input, there are 5 test cases. In the first test case, it is only possible to make all cows like type 2. FJ can do this by running a single focus group with all cows. In the second test case, we can show that no cows will change which type of hay they like. In the third test case, it is possible to make all cows like type 1 by running three focus groups - first by having cows 1 through 4 in a focus group, then by having cows 1 through 5 in a focus group, then by having cows 1 through 6 in a focus group. By similar logic, using cows 3 through 6, cows 2 through 6, then cows 1 through 6, we can make all cows like type 2. In the fourth test case, it is possible to make all cows like type 3 by running a single focus group with all cows. In the fifth test case, we can show that no cows will change which type of hay they like. SCORING: ● ● ● Input 2: N = 2. Inputs 3-4: N < 50. Inputs 5-6: h₂ ≤ hi+1 for all 1 ≤ i ≤N-1. Inputs 7-15: No additional constraints.
Expert Answer:
Answer rating: 100% (QA)
To solve this problem we can iterate through each test case and use a counting algorithm to determin... View the full answer
Related Book For
Introduction To Mathematical Statistics And Its Applications
ISBN: 9780321693945
5th Edition
Authors: Richard J. Larsen, Morris L. Marx
Posted Date:
Students also viewed these business communication questions
-
solve a somewhat larger problem whose solution incorporates the programming concepts that you have been studying: Variables, Data Types, Control Structures (if-then, if-then-else, loops, switch,...
-
The system shown consists of 3 cables. For example; cable C12 joins points 1 and 2. The coordinates of point 1 are (6.4, 0, 0) m, those of point 2 are (0, 9.5, -6.1) m, and those of point 3 are (0,...
-
Discuss the types of operational conflicts that could occur in an international context because of differences in attitudes towards time, change, material factors, and individualism. Give examples...
-
Journalize the entries to record the following: a. Check No. 6300 is issued to establish a petty cash fund of $1,200. b. The amount of cash in the petty cash fund is now $200. Check No. 6527 is...
-
Cat Auto Tech. Corp. purchased 10,000 gift certificates from DeJesus. Cat Auto Tech. Corp., an Amoco gasoline station operator, contracted with DeJesus to make 10,000 gift certificates of various...
-
House Station, Inc., is a nationwide hardware and furnishings chain. The manager of the House Station Store in Portland is evaluated using ROI. House Station headquarters requires an ROI of 10...
-
You have been assigned to be the Data Architect at your company. Your company is trying to create a baseline governance process for multiple systems and you have been tasked with preparing a review...
-
Part A Read Dean v. Dickey in Appendix A. Identify the issue regarding the validity of the will. Part B Read United States v. Martinez-Jimenez in Appendix A. Identify the issue concerning whether the...
-
Given economic service lives for both defender and challenger, and i = 15%. Find the most plausible/economical replacement strategy by considering the next 8 years. 12 25% IV Annual Equivalent Cost...
-
ODonnell & Joyce purchases components from three suppliers. Components purchased from Supplier A are priced at 7 each and used at the rate of 18,000 units per month. Components purchased from...
-
Weekly demand for jeans at a Zara store is normally distributed, with a mean of 170 and a standard deviation of 85. The supply plant takes two weeks to supply a Zara order. The store manager monitors...
-
Weekly demand for smartphones at an Apple store is normally distributed, with a mean of 500 and a standard deviation of 300. Foxconn, the assembler, takes four weeks to supply an Apple order. Apple...
-
Reconsider the Best Buy store in Exercise 3. The store manager has decided to follow a periodic review policy to manage inventory of cell phones. She plans to order every three weeks. Given a desired...
-
Motorola obtains cell phones from its contract manufacturer located in China to supply the U.S. market, which is served from a warehouse located in Memphis, Tennessee. Daily demand at the Memphis...
-
In Richard's Field, design a wide filter using broadband techniques and computer simulate the circuit using ADS, ANSYS, or AWR environment. The band ranges you are asked to design are 4.4-4.99 GHz...
-
Show that if A is any m n matrix, then Im A = A and AIn = A.
-
Suppose that 1% of all items in a supermarket are not priced properly. A customer buys ten items. What is the probability that she will be delayed by the cashier because one or more of her items...
-
Four men and four women are to be seated in a row of chairs numbered 1 through 8. (a) How many total arrangements are possible? (b) How many arrangements are possible if the men are required to sit...
-
Players A, B, and C toss a fair coin in order. The first to throw a head wins. What are their respective chances of winning?
-
Is Fairmont in compliance with company policy that requires explicit approval of all hours of eighty hours or more.
-
d that Fairmont is not in complianThe forensic audit has determinece with Federal withholding requirements for FICA and Medicare because FICA and Medicare were not withheld from employee paychecks...
-
Which of the following is not a technique to conceal inventory shrinkage? 1. Counting and valuing the physical inventory at the end of each year 2. Writing off inventory after physical inventory...
Study smarter with the SolutionInn App