Матч 378, Истинные выражения (TrueStatements)

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

Профессор Смит учит студентов логике. Он записал набор выражений:

В точности a из этих выражений истинны;

В точности b из этих выражений истинны;

В точности c из этих выражений истинны;

. . .

Числа a, b, c, … заданы в массиве statements. Необходимо определить, сколько их этих выражений истинны. Если этого установить невозможно, вернуть -1. Если ответов может быть несколько, то вернуть наибольший.

Класс: TrueStatements

Метод: int numberTrue(vector<int> statements)

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

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

Выход. Наибольшее возможное количество истинных выражений.

Пример входа

statements

{0, 1, 2, 3}

{0}

{0, 3, 1, 3, 2, 3}

{1, 1}

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

1

-1

3

0

РЕШЕНИЕ

элементарные вычисления

Максимальное количество истинных выражений может принимать значение от 0 до statements.size(). Перебираем это количество в цикле по i, начиная с наибольшего возможного значения. Для каждого значения i подсчитываем количество statements[j], равных i. Если это количество равно i, то в точности i выражений истинны. Если ни одно из перебираемых значений i не подходит, то возвращаем -1.

ПРОГРАММА

#include <cstdio>

#include <vector>

#include <algorithm>

using namespace std;

class TrueStatements

{

public:

int numberTrue(vector<int> statements)

{

int i;

for(i = statements.size(); i >= 0; i--)

if (count(statements.begin(),statements.end(),i) == i) return i;

return -1;

}

};