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

@Alsus_ultima · Регистрация: 31.08.2023

Студворк — интернет-сервис помощи студентам

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

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

Пример:

Допустим, у нас есть 4 лампочки и 5 переключателей:

4 5
3 1 2 3
3 1 3 4
2 3 4
2 2 3
1 3

Первая строка описывает, что у нас есть 4 лампочки и 5 переключателей.

Далее следуют 5 строк, каждая из которых описывает переключатель и номера лампочек, которые он изменяет. Например, первый переключатель изменяет состояния трех лампочек с номерами 1, 2 и 3.

В результате работы программы должна быть выведена информация о том, на какие переключатели необходимо нажать, чтобы включить все лампочки. Если такая комбинация переключателей не существует, то выводится -1.

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

@KSergey9 · 05.09.2023, 08:41

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

Например, первый переключатель изменяет состояния трех лампочек с номерами 1, 2 и 3.

Как это следует из приведённых входных данных?
Даже с copy-paste не справился парень. Это фиаско.

@мама Стифлера · 05.09.2023, 09:04

KSergey9, правильное замечание, ибо:

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

Например, первый переключатель изменяет состояния трех лампочек с номерами 1, 2 и 3

а я понимаю первый переключатель: 3-1-2-3.

В итоге пояснительный пример полностью вводит в заблуждение и хочется быстрее покинуть эту тему.

@KSergey9 · 05.09.2023, 09:11

С началом учебного года!

@mmi1814 · 05.09.2023, 09:58

Code
1
2
3
4
5
6
7
1234
----
1011 №2
0110 №4
0010 №5
----
1111

Alsus_ultima, в задач даются ограничения на размер данных, где они?

@Alsus_ultima · 05.09.2023, 10:03 **[ТС]**

Корректное условие вот
У вас есть n лампочек и k переключателей. Каждый переключатель изменяет состояния определенных лампочек. Вам нужно определить, на какие переключатели нужно нажать, чтобы включить все лампочки.

Формат входных данных:
- Первая строка содержит два целых числа n и k - количество лампочек и переключателей соответственно (1 ≤ n, k ≤ 15).
- Далее следуют k строк, описывающие переключатели. В каждой строке сначала указывается количество лампочек, состояние которых изменяется данным переключателем (не более n). За этим следуют номера этих лампочек. Номера не повторяются.

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

Ограничение времени: 1 с
Ограничение реального времени: 5 с
Ограничение памяти: 256M

Вот еще раз пример вводных данных

Входные данные

4 5
3 1 2 3
3 1 3 4
2 3 4
2 2 3
1 3
Результат работы

3
2 4 5

@mmi1814 · 05.09.2023, 11:15

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
int k, sum, lmp, *a, *b;
bool stop;
void func(int idx)
{
    for (int i = 0; !stop && i < 2; i++)
    {
        b[idx] = i;
        if (i) sum ^= a[idx];
        if (!(stop = sum == lmp))
            if (idx + 1 < k)
                func(idx + 1);
        if (i) sum ^= a[idx];
    }
    if(!stop) b[idx] = 0;
}
int main(int argc, char** argv)
{
    int n;
    cin >> n >> k;
    a = new int[k];
    b = new int[k];
    for (int i = 0; i < k; i++)
        a[i] = b[i] = 0;
    for (int nt, i = 0; i < k; i++)
    {
        cin >> nt;
        for (int t, j = 0; j < nt; j++)
        {
            cin >> t;
            a[i] += 1 << (n - t);
        }
        //cout << a[i] << endl;
    }
    lmp = 1;
    for (int i = 1; i < n; i++)
        lmp += 1 << i;
    sum = 0;
    stop = false;
    func(0);
    if (stop)
    {
        n = 0;
        for (int i = 0; i < k; i++)
            n += b[i];
        cout << n << endl;
        n = 0;
        for (int i = 0; i < k; i++)
            if (b[i])
                cout << (n++ ? " " : "") << i + 1;
        cout << endl;
    }
    else cout << "-1\n";
    delete[] a;
    delete[] b;

@mmi1814 · 05.09.2023, 18:37

Alsus_ultima, ну чего, результаты есть? или эту задачу сами придумали?

@Alsus_ultima · 05.09.2023, 18:41 **[ТС]**

Да, задачка пошла как надо!
Благодарю!

@SmallEvil · 05.09.2023, 20:07

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

Да, задачка пошла как надо!

Куда она пошла ?
И что вы в итоге научились ? Копипастить ?

Добавлено через 1 минуту

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

Ограничение времени: 1 с
Ограничение реального времени: 5 с

И как это понимать ?
Есть две линии времени? Реальное и ... какое ещё ?

@Alsus_ultima · 05.09.2023, 21:50 **[ТС]**

задачу я осознал.
а вот про время это реальная загадка. видимо составители живут в 2х временных линиях

@Polina23062007 · 06.09.2023, 17:02

Можете пожалуйста кратко описать алгоритм?

Новые блоги и статьи Все статьи Все блоги /
PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Access VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .

@Alsus_ultima 0 / 0 / 0 Регистрация: 31.08.2023 Сообщений: 17

	Задачка про переключение лампочек 04.09.2023, 23:34. Показов 2708. Ответов 11 Метки олимпиадная задача, олимпиадное программирование (Все метки) Суть задачи заключается в нахождении комбинации переключателей, чтобы нажатие на них позволило включить все лампочки. В задаче дано количество лампочек n и количество переключателей k. Каждый переключатель изменяет состояние некоторых лампочек. Вам требуется определить, на какие переключатели нужно нажать, чтобы включить все лампочки. Пример: Допустим, у нас есть 4 лампочки и 5 переключателей: 4 5 3 1 2 3 3 1 3 4 2 3 4 2 2 3 1 3 Первая строка описывает, что у нас есть 4 лампочки и 5 переключателей. Далее следуют 5 строк, каждая из которых описывает переключатель и номера лампочек, которые он изменяет. Например, первый переключатель изменяет состояния трех лампочек с номерами 1, 2 и 3. В результате работы программы должна быть выведена информация о том, на какие переключатели необходимо нажать, чтобы включить все лампочки. Если такая комбинация переключателей не существует, то выводится -1. Например, в данном примере решением будет нажатие на 2, 4 и 5 переключатели, чтобы включить все 4 лампочки. 0

@KSergey9 631 / 526 / 104 Регистрация: 05.08.2022 Сообщений: 2,810
	05.09.2023, 09:11
	С началом учебного года! 0

@Alsus_ultima 0 / 0 / 0 Регистрация: 31.08.2023 Сообщений: 17
	05.09.2023, 10:03 [ТС]
	Корректное условие вот У вас есть n лампочек и k переключателей. Каждый переключатель изменяет состояния определенных лампочек. Вам нужно определить, на какие переключатели нужно нажать, чтобы включить все лампочки. Формат входных данных: - Первая строка содержит два целых числа n и k - количество лампочек и переключателей соответственно (1 ≤ n, k ≤ 15). - Далее следуют k строк, описывающие переключатели. В каждой строке сначала указывается количество лампочек, состояние которых изменяется данным переключателем (не более n). За этим следуют номера этих лампочек. Номера не повторяются. Формат результата: - Если решения не существует, выведите -1. - Иначе, в первой строке должно быть записано количество переключателей, на которые нужно нажать, а в следующей строке - их номера. Номера переключателей должны быть попарно различны и указываться в порядке, в котором они описаны во входных данных. Если решений несколько, выведите любое из них. Ограничение времени: 1 с Ограничение реального времени: 5 с Ограничение памяти: 256M Вот еще раз пример вводных данных Входные данные 4 5 3 1 2 3 3 1 3 4 2 3 4 2 2 3 1 3 Результат работы 3 2 4 5 0

@mmi1814 Заблокирован
	05.09.2023, 18:37
	Alsus_ultima, ну чего, результаты есть? или эту задачу сами придумали? 0

@Alsus_ultima 0 / 0 / 0 Регистрация: 31.08.2023 Сообщений: 17
	05.09.2023, 18:41 [ТС]
	Да, задачка пошла как надо! Благодарю! 0

@Alsus_ultima 0 / 0 / 0 Регистрация: 31.08.2023 Сообщений: 17
	05.09.2023, 21:50 [ТС]
	задачу я осознал. а вот про время это реальная загадка. видимо составители живут в 2х временных линиях 0

@Polina23062007 0 / 0 / 0 Регистрация: 09.01.2022 Сообщений: 7
	06.09.2023, 17:02
	Можете пожалуйста кратко описать алгоритм? 0