7415. Белые шляпы

В комнате находится несколько людей. На каждом одета белая или черная шляпа. Каждый человек подсчитывает количество белых шляп, которое он видит на головах других. Вычислить число людей, носящих белые шляпы или сообщить, что входные данные не могут соответствовать реальной ситуации.

Вход. Каждая строка представляет собой один тест. В каждой строке задана последовательность чисел a₁, a₂, ..., a_n, где a_i содержит число белых шляп, подсчитанных i - ым человеком.

Выход. Для каждого теста в отдельной строке вывести число людей, носящих белые шляпы или -1, если входные данные не соответствуют реальной ситуации.

Пример входа	Пример выхода
2 1 1 2 2 2 10 10	2 3 -1

РЕШЕНИЕ

математика + STL

Анализ алгоритма

Пусть в комнате находится len людей и пусть a из них носит белые шляпы. Тогда a людей (те, на ком находятся белые шляпы) при подсчете должны выдать результат в a – 1 шляп (так как они не видят единственной шляпы, находящуюся у них на голове), а остальные len – a людей, которые носят черные шляпы, должны дать результат в a белых шляп.

Отсортируем массив чисел count. Положим в b наименьший элемент массива, а в w – наибольший. Если они равны, то черных шляп ни у кого нет. При этом значение b (или w) должно быть на 1 меньше чем len. В таком случае возвращаем len.

Допустимая ситуация может быть еще в одном случае – когда b отличается от w на 1. Если это не так, то возвращаем -1. Иначе массив count имеет вид

w, w, , …, w, b, b, …, b

Находим позицию pos, с которой в массиве count начинаются значения b. При этом в комнате будет находиться в точности pos людей с белыми шляпами, если pos = count[pos]. Последнее равенство означает, что человек в черной шляпе должен насчитать в точности pos людей в белых шляпах.

Реализация алгоритма

Функция whiteNumber возвращает ответ для последовательности, содержащейся в векторе с.

int whiteNumber(vector<int> &count)

{

sort(count.begin(),count.end());

int len = count.size(),w = count[len-1],b = count[0];

if ((w == b) && (w + 1 == len)) return len;

if (w - b > 1) return -1;

int pos = (int)(find(count.begin(),count.end(),w) - count.begin());

if (pos == count[pos]) return pos;

return -1;

}

Основная часть программы. Читаем входные данные. Количество чисел в каждой строке нам неизвестно. Читаем данные каждого теста до конца строки. Числа заносим в вектор с.

while(scanf("%d%c",&a,&ch) == 2)

{

c.clear();

c.push_back(a);

while(ch != '\n')

{

scanf("%d%c",&a,&ch);

c.push_back(a);

}

Вычисляем и выводим ответ.

int res = whiteNumber(c);

printf("%d\n",res);

}