|
|
|
|
|
|
|
Вернуться
| 1 Mиша Панявин [PML], 15 ноября 2010 г. 19:25:18 | |
|
Огромное !!!СПАСИБО!!!
|
|
|
| 2 Ким Вячеслав Олегович, 12 ноября 2010 г. 12:09:25 | |
|
спасибо
|
|
|
| 3 Сыскаев А.С. (Ch0W [MSU]), 11 ноября 2010 г. 13:18:02 | |
_Задача D. Шоколадки.
_Самая интересная задача контеста (ИМХО). Для начала нужно разобраться с простой
задачей: сколько существует способов выписать подряд N цифр (0 или 1), так чтобы
не встречалось больше двух одинаковых цифр подряд. Это одна из известнейших задач
на Динамику, предположим, что мы знаем ответ (если это не так, советую почитать
литературу, там объяснят лучше чем я). Итак ответ на эту (простую) задачу 2*F(N+1),
где F(N) - n-ое число Фибоначчи.
_Теперь к нашей настоящей задаче, рассмотрим первую строчку, она обязана соответствовать
строкам из рассмотренной простой задачи. Если где-то в ней идут два 0/1 подряд (например
i-ая и i+1-ая цифры), то это полностью определяет значения в i-1, i, i+1, i+2 столбцах
(проверяется на примере, листок в клеточку Вам в помощь), кроме того если есть хотя бы
два 0/1 подряд в некой строке, то этого не может быть ни в одном столбце (тоже проверяется)
Таким образом мы выбираем: либо такое бывает в строках, либо в столбцах, либо все замощено
в шахматном порядке. Итак: любой один столбец или одна строка (кроме ..0101010101010..)
полностью определяет что будет в любой клетке доски. Их соответственно 2*F(N+1)-2 и 2*F(M+1)-2,
плюс к этому два вида заполнения в шахматном порядке. Итог: 2*(F(N+1)+F(M+1)-1).
_СлоЖность задачи O(max(N, M))=O(N+M), но не стоит забывать, что ответ может быть много
больше 2^64, и потребуется длинная арифметика, что внесет коррективы и в сложность написания
программы, и в ее быстродействие.
|
|
|
| 4 Сыскаев А.С. (Ch0W [MSU]), 11 ноября 2010 г. 13:17:50 | |
_Задача С. Булева алгебра.
_Задача также на технику. Я делал так: в отдельной строке хранил само выражение.
Затем для каждого ввода данных (его разбор не должен вызвать затруднений,
переменные можно например хранить в массиве) вычислял значение выражения отдельно
(размер ввода позволял это). Теперь собственно о вычисление выражения, это
делается рекурсивно, рекурсивная функция получает на вход кусок выражения, который
нужно посчитать и при необходимости вызывает себя для "куска от куска", первый
вызов осуществляется от всего выражения. При этом в куске содержится либо переменная,
тогда ее значение и нужно вернуть, либо функция, тогда требуется вызвать рекурсивную
функцию от каждого ее аргумента, а потом (или в процессе) провести над результатами
необходимые вычисления.
_Сложность задачи O(N*(log(_размер выражения_)+K). Впрочем в этом я не уверен.
|
|
|
| 5 Сыскаев А.С. (Ch0W [MSU]), 11 ноября 2010 г. 13:17:39 | |
_Задача B. Квадрат.
_Задача на технику программирования, какой-то конкретной идеи в ней нет,
реализовывать можно различными способами. Один из них: определить координаты
углов "минимального" прямоугольника, который содержит все отмеченные точки множества,
это делается в один проход, во-время считывания данных. Затем нужно понять,
какие квадраты могли быть изначально, если немного повозиться с рисунком становится
очевидно, что это квадраты с углами в точках отстающих не более чем на единицу от
углов минимального прямоугольника. Всего этому условию может соответствовать 81=9*9
прямоугольник, среди них могут быть и квадраты, входные данные позволяют проверить
каждый из них, если какой-то подошел, то выводим "SQUARE", если таких нет, то "CIRCLE".
Теперь собствено о проверке, она делается прямо по условию, проверяется внутренняя часть
квадрата "без границы" (везде должны быть '*'), если все делать аккуратно, то этого будет
достаточно.
_Сложность задачи O(N^2).
|
|
|
| 6 Сыскаев А.С. (Ch0W [MSU]), 11 ноября 2010 г. 13:17:22 | |
_Задача A. Единицы.
_Это "Утешительная задача". Единицы в записи двоичного числа, можно посчитать
в лоб, постоянно деля исходное N на два и прибавляя к ответу 1, если остаток
от деления был равен единице, таким образом каждое деление избавляет нас от
правой цифры в записи числа, пока N не стало равно нулю (деление можно заменить
операцией двоичного сдвига, но здесь это не важно)
_Сложность задачи O(log(N)).
|
|
|
Чтобы оставить сообщение необходимо зарегистрироваться и авторизоваться!
| | | |
