Old Programmer
4145 subscribers

Олимпиадные задачи по программированию. Задача о раскладывающихся столах

289 full reads
491 story viewUnique page visitors
289 read the story to the endThat's 59% of the total page views
1,5 minute — average reading time

Весь мой канал Old Programmer о программировании и программистах расположенные по темам можно найти тут. А здесь все мои ресурсы по рекурсивному и олимпиадному программированию

Задача "Столы"

Фабула

В одном учреждении собирались проводить некое мероприятие. Оно предполагало, что люди группами будут собираться за одним столом и обсуждать некие вопросы. В учреждение было такое помещение с уже прикрепленными к полу столами. Столы можно было раскладывать, так что площадь каждого увеличивалась в четыре раза. Но вот беда некоторые столы, если их разложить мешали раскладывать другие столы. Другие же столы стояли у стенок при чем так, что разложить их было не возможно. Особенность разложения столов была следующая. Если не разложенный стол можно себе представить в виде квадрата со стороной 1, то при разложении получался квадрат со стороной 2. Разложение происходило в две стороны, при чем у каждого эти стороны могли быть разные. Разложить стол частично тоже было не возможно.

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

На входе дан размер помещения. Длина n (n>0, n<=100), ширина m (m>0, m<=100). Можно рассматривать это как массив, где n строк и m столбцов. В помещении стоят столы с координатами i и j. При чем i>0 и i<=n, j>0 и j<=m. Каждому столу присваивается также параметр p, определяющий в какие стороны он раскладывается:

p = 0, стол раскладывается в сторону меньших i и j.

p = 1, стол раскладывается в сторону меньших i и больших j.

p = 2, стол раскладывается в сторону больших i и меньших j.

p = 3, стол раскладывается в торону больших i и j.

Будем считать, что стол в не разложенном состоянии занимает площадь 1, а в разложенном 4.

Входные данные представлены в виде строк. В первой строке через пробел даны размеры комнаты. В следующей строке стоит количество столов k (k>=0 и k<=100). Следующие k строк состоят из троек чисел: i j p.

Задание

Найти максимальную площадь столов, которую можно получить их разложением.

Примеры

Олимпиадные задачи по программированию. Задача о раскладывающихся столах

Решение

Как это часто и бывает, первое решение, которое приходит на ум - рекурсивное. Однако легко понять, что при увеличении количество столов время выполнения может резко увеличить до не приемлемых значений. Так что рекурсивное решение годится разве что для проверки основного решения при не больших значениях входных данных. Кстати рекурсивное решение я тоже сделал, но в силу указанных выше причин, оно не интересно и разбирать его не имеет смысл.

В действительности концепция решения задачи очень проста, хотя решение получилось несколько громоздким (olmp4002.c), но, честно говоря, не было времени оптимизировать код, а работает он и так, достаточно быстро.

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

Поэтому:

  1. Раскладываем столы, если этому не мешает стенка или стационарная часть другого стола.
  2. Затем начинаем складывать столы в таком порядке: в начале столы, у которых раскладываемая часть (три клетки) оказывается занятой раскладываемыми частями других столов, потом столы, у которых тоже самое можно сказать о двух клетках раскладываемой части, потом столы с одной клеткой занятой раскладываемой частью другого стола.
  3. После этого подсчитываем получившуюся площадь.

До скорых встреч, друзья. Подписываемся на мой канал Old Programmer, здесь много материалов по разным вопросам программирования.

Фрагмент программы olmp4002.c
Фрагмент программы olmp4002.c