Матч 194, Нечетные и четные (OddsAndEvens)

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

Целое число может быть нечетным и четным. Рассмотрим операции сложения и умножения на четных и нечетных числах:

EVEN + EVEN = EVEN

EVEN + ODD = ODD

ODD + ODD = EVEN

EVEN * EVEN = EVEN

EVEN * ODD = EVEN

ODD * ODD = ODD

Выбран некоторый набор целых чисел и вычислены все их попарные суммы и произведения. Все суммы занесены в массив sums, а произведения – в products. Причем заносятся не суммы и произведения чисел, а слова “ODD” и “EVEN” в зависимости от того, являются ли они нечетным или четным числом.

В задаче необходимо вернуть строку "EVEN <x> ODD <y>", где <x> – количество четных чисел в наборе, а <y> – количество нечетных чисел.

Класс: OddsAndEvens

Метод: string find(vector<string> sums, vector<string> products)

Ограничения: sums содержит n*(n-1)/2 элементов, где 0 £ n £ 100.

Вход. Массив попарных сумм sums и произведений products чисел.

Выход. Строка "EVEN <x> ODD <y>", где <x> – количество четных чисел в наборе, а <y> – количество нечетных чисел.

Пример входа

sums	products
{"EVEN"}	{"ODD"}
{"EVEN","ODD","ODD"}	{"ODD","EVEN","EVEN"}
{"ODD","EVEN","ODD","EVEN","ODD","EVEN"}	{"ODD","EVEN","EVEN","EVEN","ODD","ODD"}

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

"EVEN 0 ODD 2"

"EVEN 1 ODD 2"

"EVEN 1 ODD 3"

РЕШЕНИЕ

математика

Подсчитаем в переменной OddSums количество нечетных чисел в массиве сумм sums, а в переменной OddProducts количество нечетных чисел в массиве произведений products. Поскольку sums содержит n * (n – 1 ) / 2 элементов, то простым перебором находим количество чисел в исходном наборе n.

Произведение чисел может быть нечетным тогда и только тогда, когда оба числа нечетные. Поэтому если набор чисел содержит i нечетных чисел, то количество пар произведений, которые будут нечетными, равно i * (i – 1) / 2. Остальные n – i чисел будут четными. Сумма будет нечетной, если одно из чисел четно, а другое – нечетно. Но у нас имеется i нечетных и n – i четных чисел, поэтому нечетных сумм будет i * (n – i). Перебираем все возможные значения i от 0 до n и если оба выше приведенные равенства имеют место, то возвращаем результат. Иначе возвращаем "IMPOSSIBLE".

ПРОГРАММА

#include <cstdio>

#include <string>

#include <vector>

#include <algorithm>

using namespace std;

class OddsAndEvens

{

public:

string find(vector<string> sums, vector<string> products)

{

char res[50];

int i, OddSums = count(sums.begin(),sums.end(),"ODD");

int n, OddProducts = count(products.begin(),products.end(),"ODD");

for(n = 0; n*(n-1)/2 != sums.size(); n++);

for(i = 0; i <= n; i++)

if (i*(i-1)/2 == OddProducts && i*(n-i) == OddSums)

{

sprintf(res, "EVEN %d ODD %d", n - i, i);

return res;

}

return "IMPOSSIBLE";

}

};