Решение задачи «Гирлянды», ДонНУ?

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

Среди заданий есть очень интересная задачка, которая называется «Гирлянды», связана с физикой.

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



Ограничения

Ограничения по памяти: 64 МБ

Ограничения по времени: 2 c.

Разрешено использовать: Pascal (FreePascal 2.4.2/Delphi Compiler 15.0), C/C++ (MinGW 3.4.2, Microsoft Visual C++ 2008/2010/2012)



Текст задачи

К Новому Году роботы наряжали компьютер светящейся гирляндой из лампочек, закрепленных на квадратной сетке макетной платы. Напряжение подведено к верхнему левому и нижнему правому углу макетной платы. Все лампочки одинаковые и светятся даже при очень слабых токах. В самый разгар подготовки одна из лампочек перегорела. Роботы очень заняты подготовкой, поэтому поручили Вам ответственную задачу — определить, какие лампочки в гирлянде останутся светиться постоянно, пусть и слабо. Напряжение считать постоянным (гирлянду запитали от блока питания компьютера), поэтому эффекты ёмкости и индуктивности учитывать не нужно.



Формат входных данных

В первой строке задано два целых числа: N — число ячеек сетки по вертикали и M — по горизонтали. Далее следует (2N+1) строка. В каждой нечётной строке записано M чисел — значения горизонтальных проводников. В каждой чётной строке записано (M+1) число — значения вертикальных проводников. Число 0 в строке означает, что проводник отсутствует (на рисунке представлено пунктирной линией), число 1 — присутствует проводник с лампочкой, число 2 обозначает перегоревшую лампочку (на рисунке — пунктирная лампочка). Гарантируется, что среди входных данных есть ровно одна двойка.



0 ≤ N ≤ 10, 0 ≤ M ≤ 10.



Формат выходных данных

Вывод должен содержать матрицу (подобную входной матрице), в которой число 0 означает отсутствие проводника с лампочкой, 1 — проводник есть и лампочка горит, 2 — проводник с лампочкой есть, но лампа не горит.

task11.png



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

70c39cbd8edac68898ba4c77f3318440.png
  • Вопрос задан
  • 5180 просмотров
Пригласить эксперта
Ответы на вопрос 6
Arktos
@Arktos
Некорректно обсуждать задачу до окончания олимпиады
Ответ написан
Brand
@Brand
FilimoniC
@FilimoniC
Рисунок не соответствует данным вроде бы
Ответ написан
FilimoniC
@FilimoniC
Кстати, очень странное ограничение в 64 мегабайта. Многовато. за указанные 2с не кажддый жесткий диск успеет прочитать эту программу, не то что исполнить
Ответ написан
есть эта задача на каком-нибудь online judge чтобы проверить решение?
Ответ написан
ivnik
@ivnik
Алгоритм Флойда — Уоршелла?
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы