Задача про переключатели

[Night]

Подскажите, пожалуйста, алгоритм решения:

Есть N лампочек и M переключателей, каждый из которых какие-то лампочки переключает, а какие-то нет. Сначала часть лампочек включена. Договоримся горящие лампочки обозначать 1, а выключенные - 0. Для переключателей будем писать 1, если переключатель меняет состояние данной лампочки, и 0, если не меняет. Тогда любой переключатель можно представить строкой из N нолей и единиц. Начальное и конечное состояние лампочек также закодируем строкой из 0 и 1. «Применение» переключателя к лампочкам приводит к тому, что включенные лампочки становятся выключенными, а выключенные - включенными (естественно, это справедливо только для лампочек, к которым есть доступ от этого переключателя).

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

Входные данные: Вводятся числа N и M (1=50, 1=50). Вводится строка, характеризующая начальное состояние лампочек. Вводится строка, характеризующая конечное состояние лампочек. Вводится M строк, характеризующих переключатели.

Выходные данные: Номера переключателей, которые нужно применить, причем каждый переключатель можно применить не более 1 раза, либо сообщение "Нет решения".

Пример: Входные данные: 5 3 10010 11000 11100 10001 10110 Выходные данные: 1 3

[SuperVisor]

В принципе, задача не так уж и сложна, я вот только не понял про входящие данные: N и M - можно поточнее?

[AVer]

Сообщение от SuperVisor

В принципе, задача не так уж и сложна, я вот только не понял про входящие данные: N и M - можно поточнее?

Ответ в предидущем посте:

Сообщение от Night

Есть N лампочек и M переключателей...

[Virtson]

1)
10010 XOR 11000 = 01010
2) Ищем комбинацию переключателей,
для которой Xor (поэлементный)
дает состояние 01010

[проблема в том, что сначала комбинируем по 2,
ответа нет - по 3, и так до 50 - но это полный перебор]
у кого есть другой принцип решения ?

[SuperVisor]

Сообщение от AVer

Ответ в предидущем посте

Прошу прощения...

Сообщение от Virtson

у кого есть другой принцип решения ?

Скорее всего в данной ситуации это - единственный выход.

[Night]

Сообщение от Virtson

1)
10010 XOR 11000 = 01010
2) Ищем комбинацию переключателей,
для которой Xor (поэлементный)
дает состояние 01010

[проблема в том, что сначала комбинируем по 2,
ответа нет - по 3, и так до 50 - но это полный перебор]
у кого есть другой принцип решения ?

У меня такая идея была, но здесь нам придется перебирать очень много вариантов. Наверняка существует более совершенный способ, ведь для того подобные задачи и предназначены