Матч 432, Решетка ламп (LampsGrid)

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

Имеется прямоугольная решетка ламп, каждая из которых может находиться в двух состояниях: “ON” и “OFF”. Возле каждой колонки находится переключатель, который может менять состояние всех ее ламп на противоположный (состояние “ON” меняется на “OFF” и наоборот).

Строка решетки является зажженной, если все ее лампы находятся в положении “ON”. Массив initial описывает начальное состояние ламп решетки (‘1’ – лампа горит, ‘0’ – лампа выключена). Вычислить наибольшее количество строк, которое можно зажечь совершив в точности k переключений. Каждый из переключателей можно переключать произвольное количество раз.

Класс: LampsGrid

Метод: int mostLit(vector<string> initial, int k)

Ограничения: initial содержит от 1 до 50 строк, каждая из которых содержит от 1 до 50 символа ‘0’ и ‘1’, длины всех строк initial равны, 0 £ k £ 1000.

Вход. Массив initial, описывающий начальное состояние ламп решетки (‘1’ – лампа горит, ‘0’ – лампа выключена) и значение k.

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

Пример входа

initial	k
{"01", "10", "10"}	1
{"00", "11"}	999
{"01", "10", "01", "01", "10"}	1

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

2

0

3

РЕШЕНИЕ

перебор

Можно заметить, что одинаковые строки остаются одинаковыми в процессе любой последовательности переключений. То есть если в некоторый момент существует зажженная строка, то зажженными будут и те строки, которые равнялись ей изначально.

Рассмотрим i - ую строку. Чтобы ее зажечь, следует совершить как минимум zeroes переключений, где zeroes равно количеству нулей в ней. Если k < zeroes или четность k и zeroes разная, то зажечь i - ую строку сделав в точности k переключений невозможно. Если за k переключений i - ую строку можно зажечь, то одновременно с ней зажгутся и те строки, которые равнялись ей первоначально.

Перебираем все строки. Проверяем, можно ли очередную строку зажечь за k переключений. Если ответ утвердительный, то находим количество строк, равных ей. Ответом задачи будет наибольшее количество изначально равных между собой строк (при условии что эти строки можно зажечь за k переключений).

ПРОГРАММА

#include <cstdio>

#include <vector>

#include <string>

#include <algorithm>

using namespace std;

class LampsGrid

{

public:

int mostLit(vector<string> initial, int k)

{

int i, zeroes, res;

for(res = i = 0; i < initial.size(); i++)

{

zeroes = count(initial[i].begin(),initial[i].end(), '0');

if (zeroes % 2 == k % 2 && zeroes <= k)

res = max(res, count(initial.begin(),initial.end(),initial[i]));

}

return res;

}

};