Матч 361, Белые шляпы (WhiteHats)

Дивизион 2, Уровень 2; Дивизион 1, Уровень 1

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

Класс: WhiteHats

Метод: int whiteNumber(vector<int> count)

Ограничения: count содержит от 2 до 50 символов, 0 £ count[i] £ 50.

Вход. Массив count, содержащий количество белых шляп, подсчитанное каждым человеком, находящимся в комнате.

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

Пример входа

count

{2,1,1}

{2,2,2}

{10,10}

Пример выхода

2

3

-1

РЕШЕНИЕ

математика

Пусть в комнате находится 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 людей в белых шляпах.

ПРОГРАММА

#include <cstdio>

#include <vector>

#include <algorithm>

using namespace std;

class WhiteHats

{

public:

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;

}

};