Решаем сложные и олимпиадные задачи

[Lakers]

а.ну может.вторую решайте-)

Добавлено спустя 33 минуты 43 секунды:

проверил.в полсекунды уложылся:-)

[Lakers]

вах вах вах!че никаких идей чтоли?ну вы че ребята!

[toll]

Lakers

старая задача ... жизнь называлася ... я ее на тр7 когда то делал ...

Добавлено спустя 5 минут 44 секунды:

Вот вам задача

Есть некоторое количество точек на плоскости N с координатами х1 y1 ...xN yN

нада наити такую окружность минимального радиуса , которая будет содержать максимальное количество точек ... но не менее N -n где n некоторое количество точек которые можно откинуть...

ввод: координаты точек, n

вывод: коодинаты центра окружности, радиус , коодинаты откинутых точек ...

[Lakers]

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

[0xDEADBEEF]

toll

Сначала реши предыдущую, потом загадывай.

И как насчёт ограничений? без них любую задачу перебром решить можно)

Написал правила в первом посте

Lakers

Эти бактерии пока для меня загадка, сам-то решил?

[Lakers]

не не решил еще.

[L0K1]

Э бактерии - смех, один.

игра жизнь live + перебор комбинаций, засеивания клеток, и проверка похоже ли?

Классическая задача+перебор заполнения матрицы MxN.

[0xDEADBEEF]

Мой смех - ваша уверенность. Если это всё так просто - попробуйте сдать, тогда посмеёмся вместе)

[Lakers]

если она решается тупым перебором то действительно смешно.но както я сомневаюсь что она так проста. на acm.timus.ru её пробовали решить 9 человек а релил 1%, т.е. 1человек.скорее всего все валются на временном ограничении.или какаято хитрость в ней всёже есть.

[0xDEADBEEF]

+1 Перебор не подходит хотябы потому, что невозможно заключить можем ли мы получить исходную картину. Собственно мы либо её получаем, либо бесконечно "живём".

[Lakers]

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

[0xDEADBEEF]

Вобщем это гроб дубовый, из топа тимуса (а это мировые призёры и чемпионы) почти никто не решил.

Автор, предлагаю дать другую. Либо пробуем решить toll'a с ограничениями "перебор не проходит"

[triwire]

0xDEADBEEF что за топ тимуса?

а по мойму ее можно решить перебром с конца т.е.:

всего клетка может быть заселена 5 бактериями - одна собственная и 4 от соседних, следует

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

нужно искать единицы и расселять(1 ставить в ноль а соседнии уменьшать на один) эту клетку,

если попытка не удалась то обратно заселять и искать новую единичку

что значит попытка не удалась:

1.неосталось единичек, все перебрали или их нет вообще

2.получены две соседнии клетки с реальными единичками

3.получена клетка у которой количество бактерий больше чем количество заселенных соседних клеток +1 (например если нет заселенных соседних клеток то не может быть больше одной бактерии)

[Lakers]

ладно,думаю на эту задачу только времени уйдет больше.лучше чтонибудь не такое жёское=)

Шифровка

Ограничение времени: 1.0 секунды

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

Мюллер много раз пытался поймать Штирлица с поличным, но тот всё время выкручивался. Как-то раз Штирлиц просматривал электронную почту. В это время незаметно вошел Мюллер и увидел, как у него на экране появился бессмысленный набор символов. «Шифровка», — подумал Мюллер. «UTF-8», — подумал Штирлиц.

Известно, что Штирлиц шифрует текст следующим образом:

Убирает все пробелы и знаки препинания.

Заменяет все подряд идущие одинаковые буквы на одну такую букву.

Многократно вставляет в произвольное место текста две одинаковых буквы.

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

Исходные данные

В единственной строке записана шифровка Штирлица, состоящая из строчных латинских букв. Длина шифровки не превосходит 200000.

Результат

Выведите восстановленный текст.

Пример

исходные данные

wwstdaadierfflitzzz

результат

stierlitz

номер задачи: 1654.

Добавлено спустя 1 минуту 3 секунды:

заадча простая...

[toll]

0xDEADBEEF

В моей задаче перебор есть... вот только две точки будут лежать на окружности но не обязательно на диаметре, и не обязательно какая то из точек будет центром окружности (возьмем для примера 3 точки ) вот в чем вся первая изюминка этой задачи, вторая это условие как можно отбросить несколько точек

А про бактерии или я неправильно понял условие ... но если взять пример и последовательно сделать планы заселения то исходная картина не получается

[0xDEADBEEF]

triwire

http://acm.timus.ru/ranklist.aspx

Даю 99% что этот алгоритм не пройдёт.

Lakers

Собственно решение задачи описанно в условии. В реализации обойдёмся стэком, сравнивая каждый новый элемент с вершиной.

toll

Мнда, первая изюминка всё портит. Выходит преребираем все n точек, выкидываем их, из оставшихся ищем 2 наиболее удалённые (можно выпуклой оболочкой, можно качением), минимальная из всех и будет ответом.

я прав?

[X-tender]

перебор 20! вариантов это лихо даже если убрать зеркальные (20!/8), все равно кол-во никаким образом в заданное время не впишется

[toll]

0xDEADBEEF

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

1 предполагаем что распределение точек будет нормальным... если нет то откидываем точки со сликим большим отклонениями

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

3 центр окружности будет лежать на перпендикуляре к этому отрезку

4 ну и собсвенно на компьютере перебор окружностей .... перемещая центр и сжимая радиус ...

----------------------------------------------------

[X-tender]

Что-то у меня никак не получается получить холст из примера заполняя по ответу из примера

Пробовал два алгоритма:

1)

цикл

{

заселяется клетка,

увеличиваются на единицу соседи этой клетки, которые не равны 4 (справа,слева,сверху,снизу), если же ==4, то 1

}

2)

цикл

{

заселяется клетка,

увеличиваются на единицу все клетки, у которых заселены соседи

}

Я неверно понял задачу?

[toll]

X-tender

у меня тоже не получилось ...

Если > 4 то 1

и еще вопрос ... в "Жизни" клетки сами размножались ... а сдесь как то нет ...

[X-tender]

toll, я до инкремента проверяю равно ли 4, если равно, то 1, если нет то инкремент.

2-й вариант который я показал и есть с размножением, только все равно не сходится... может задание переведено не так? скиньте в оригинале

[Lakers]

оно и есть в оригенале!

[X-tender]

Lakers

в АСМ на английском же задания дают

[Lakers]

на топ кодер 70%на руском.

[X-tender]

Lakers, но текст задачи неоднозначен, непонятно как заполняется картина