`Всеукраїнський центр проведення олімпіад в мережі Інтернет

 Задача Lamps2

Дискусія навколо задачі Lamps породила наступну задачу: Є гірлянда з лампочок, що не перегорають ні при яких умовах і світяться при будь-яких ненульових напругах.
Лампочки цієї моделі мають 2 контакти (1 і 2) та нитку розжарення між ними. Лампочки з'єднані провідниками з нульовим опором. Фізики знають, що в цьому випадку схема не матиме точок з однаковим потенціалом, що не з'єднані провідником напряму. Визначіть, скільки (та які саме) лампочок не світитимуться через помилки монтажу.Гірлянда підключена до мережі 2-ма додатковими провідниками, що під'єднані до перших контактів першої та останньої лампи.

Технічні умови: Ви вводите К (50>= K>=3)-кількість ламп в гірлянді,Т-кількість відрізків провідника,що з'єднують лампи, а далі -Т груп по 4 числа : номер_лампочки, номер_контакту, номер_лампочки, номер_ контакту - для кожного провідника. Всі величини вводяться з клавіатури через пропуск.
Ви виводите на екран кількість лампочок,що не світяться, а потім їх номери в порядку зростання. Якщо помилок в схемі немає, вивести 0.
Приклад:
Введення:
6 7 1 1 2 1 1 2 2 1 2 2 3 1 2 2 4 1 3 2 5 1 4 2 5 1 5 1 6 2 
Виведення:
2 1 5


Задача Lamps2

Дискуссия вокруг задачи Lamps породила следующую задачу: Есть гирлянда из лампочек, не перегорающих ни при каких условиях и светящихся при любом напряжении. Лампочки этой модели имеют 2 контакта (1 и 2) и нить накала между ними. Лампочки соединены проводами с нулевым сопротивлением. Физики догадались, что в такой схеме не существует 2-х точек с одинаковым потенциалом, не соединенных напрямую проводом. Определить, сколько (и какие именно) лампочек изначально не светилось из-за ошибок монтажа. Гирлянда подключена к сети 2-мя дополнительными проводами к первым контактам первой и последней лампы.

Технические условия:
Вы вводите К (3<=K<=50) - количество ламп в гирлянде, Т - количество отрезков провода, соединяющих лампы, а далее Т груп по 4 числа - номер_ламочки, номер_контакта, номер_лампочки,номер_контакта - для каждого провода. Все величины вводятся с клавиатуры через пробел. Вы выводите на экран количество негорящих лампочек, а потом их номера в порядке возрастания. Если ошибок в схеме нет, вывести 0.
Пример:
Ввод:
6 7 1 1 2 1 1 2 2 1 2 2 3 1 2 2 4 1 3 2 5 1 4 2 5 1 5 1 6 2
Вывод:
2 1 5

© LIKT 1998-2024