CountryGroup
SRM 653 · 2015-01-29 · by dreamoon
Problem Statement
Some people are sitting in a row. Each person came here from some country. You have a theory that people from the same country are all sitting together. You decided to test this theory. You asked each person the same question: "How many people from your country (including you) are here?"
You are given a
If all the answers are consistent with your theory, return the number of different countries that are present. (Given that all answers are consistent with the theory, the number of countries can always be uniquely determined.) Otherwise, return -1.
Constraints
- The number of elements in a will be between 1 and 100, inclusive.
- All elements of a will be between 1 and 100, inclusive.
{2,2,3,3,3}
Returns: 2
These answers are consistent with your theory. The first two people are from one country, the other three are from a different country. Thus, there are two countries and the correct return value is 2.
{1,1,1,1,1}
Returns: 5
Here, each person comes from a different country.
{3,3}
Returns: -1
These answers do not correspond to your theory. In particular, they are not even correct: there are only two people but each of them claims that there are three people from their country.
{4,4,4,4,1,1,2,2,3,3,3}
Returns: 5
{2,1,2,2,1,2}
Returns: -1
These answers do not correspond to your theory. It is possible that these are people from four different countries, but even if that were the case, we can tell that people from some countries are not sitting together. For example, consider the leftmost person. According to her answer, there are two people from her country. However, the person sitting next to her cannot be from the same country.
Submissions are judged against all 88 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class CountryGroup with a public method int solve(vector<int> a) · 88 test cases · 2 s / 256 MB per case